И, кстати, как вы вообще сравниваете игры - не занимайтесь ерундой - в крестиках оптимальная стратегия приводит к победе одной из сторон, в шахматах к ничьей. Разные игры - разные исходы. Иногда оптимальные стратегии выигрывают, иногда проигрывают, иногда - приводят к ничьей, вот и всё.
И, кстати, как вы вообще сравниваете игры - не занимайтесь ерундой - в крестиках оптимальная стратегия приводит к победе одной из сторон, в шахматах к ничьей. Разные игры - разные исходы. Иногда оптимальные стратегии выигрывают, иногда проигрывают, иногда - приводят к ничьей, вот и всё.
С уважением, Дмитрий
откуда, все-таки, такая уверенность, что в шахматах оптимальная стратегия приводит к ничьей? Вы это доказали?
Таким образом число различных партий никак не может быть больше, чем 321**12700=10**31832,6139115418753922455281125=10**(10**4,5028723018553476741847908561807). Согласитесь, что четыре с половиной сильно не дотягивает до звания четырёхзначная цифра?
У вас я даже не возьмусь сосчитать эти знаки :)
Здесь явная ошибка в расчётах: вы возвели в степень количество возможных ходов, но ведь каждый из них ещё и приводит к различным позициям. Без пресловутых 10^120 здесь не обойтись. Разница как раз на три порядка, так что... И сдаётся мне, расчёт должен быть куда более сложным, т. к. позиции ещё и повторяются: различными путями можно придти к одной позиции, но это будут разные партии.
А вообще - обратились бы вы с этим к Е. Гику, если он ещё жив. Мастер и кандидат наук... Он, помню, специализировался на околошахматной математике и компьютерных шахматах. Мигом всё растолкует.
P. S. В книге Пушкина приводилось только количество позиций, упоминание о количестве партий я встречал в другом источнике.
Дед_в_очках "Скорость света ограничивает время передачи информации не только внутри одного процессора, но и между процессорами. Быстрее определённого потолка система из многих процессоров в любом случае работать не будет."
Ну это уже демагогия пошла, неинтересно. Вы, вероятно, не представляете, что такое распределенная система - там, собственно говоря, от скорости передачи данных зависит только время отклика системы, но никак не время расчета вариантов. Причем здесь скорость света при передаче данных вообще не понял. Намешали все в кучу, и строите на этом выводы.
Согласен, я здесь дилетант. Просто у меня есть подозрение, что пока клиент не "откликнется", сервер (управляющий модуль) не будет знать, посчитан вариант или нет, и кто должен заниматься расчётом следующего. Вопросов здесь масса, но вы специалист, вам и карты в руки. Только помните, что я говорил насчёт увеличения скорости даже в секстиллион раз
Кстати, мне интересно, насколько авторы статей разбираются в компьютерах и компьютерных алгоритмах, кто из авторов РЕАЛЬНО реализовывал математические алгоритмы на РЕАЛЬНОМ языке программирования. Практически все шахматисты говорят о компьютерных вычислениях в шахматах, но кто из них знает как это реализуется на практике, или этому стали учить в институте физкультуры? Я, к примеру, алгоритмы небольшой сложности, вроде численных методов в мат. моделировании, смог реализовать только после нескольких лет учебы. И оставьте разговоры про скорость света и прочую ерунду! Я уже приводил пример со скринсейвером - и подобные опюты уже есть, и они сработали (в медицине). И самое главное - АЛГОРИТМ СУЖАЕТ ОДЗ ЦЕЛЕВОЙ ФУНКЦИИ. В этом его смысл. И не говорите об отсутствии алгоритма - это бред, любая программа алгоритмична. И, даже, если нет точного аналитического решения, ввиду сложности постановки задачи, то, по крайней мере, размерность задачи и количество вариантов перебора можно сократить. И к слову о позициях. Как вы думаете каков будет процент позиций в которых есть смысл что - то считать? И вообще, считать следует не позиции, а варианты развития игры - такой подход предполагает очевидную алгоритмичность задачи, а не прямой перебор вариантов.
С уважением, Дмитрий
()
Кстати, мне интересно, насколько авторы статей разбираются в компьютерах и компьютерных алгоритмах, кто из авторов РЕАЛЬНО реализовывал математические алгоритмы на РЕАЛЬНОМ языке программирования. Практически все шахматисты говорят о компьютерных вычислениях в шахматах, но кто из них знает как это реализуется на практике, или этому стали учить в институте физкультуры?
Не знаю, как сейчас, но в наше время - нет, не учили :) Но я довольно хорошо знаком с шахматным программированием, во всяком случае с теоретической частью. Доводилось читать и работы специалистов, начиная с Ботвинника и заканчивая Плаатом, и даже исходные тексты программ.
()
И самое главное - АЛГОРИТМ СУЖАЕТ ОДЗ ЦЕЛЕВОЙ ФУНКЦИИ. В этом его смысл. И не говорите об отсутствии алгоритма - это бред, любая программа алгоритмична. И, даже, если нет точного аналитического решения, ввиду сложности постановки задачи, то, по крайней мере, размерность задачи и количество вариантов перебора можно сократить.
Я не говорил об отсутствии алгоритма (?), а только о его приближённости. И раз вы признаёте, что нет точного решения, то и спорить не о чем :) Конечно, количество вариантов сокращают, и делают это весьма успешно. Особенно впечатляет пример "Рыбки", когда в программу закладывается максимум знаний и это делает ненужным перебор большинства вариантов... А полный перебор (brute force) уже давно не используется.
Как вы думаете каков будет процент позиций в которых есть смысл что - то считать? И вообще, считать следует не позиции, а варианты развития игры - такой подход предполагает очевидную алгоритмичность задачи, а не прямой перебор вариантов.
На сегодняшний день точно просчитаны все пятифигурные эндшпили. То есть, например, загоняем в машину позицию скажем ладья и пешка против ладьи (ну и два короля) и находим в базе данных уже без расчетов готовые оптимальные решения и результат. Применительно к пятифигурным эндшпилям все посчитано полным перебором и ошибка исключена. Но уже шестифигурные эндшпили не будут посчитаны не только при нашей жизни, но по прикидкам, до конца жизни Солнечной системы.
А вообще - обратились бы вы с этим к Е. Гику, если он ещё жив. Мастер и кандидат наук... Он, помню, специализировался на околошахматной математике и компьютерных шахматах. Мигом всё растолкует.
Входим: . Вводим: максимальное число шахматных позиций. Смотрим первую ссылку: .
Позволю дать пространную цитату оттуда.
Е.Гик ()
Поскольку число всех позиций на доске является конечным, шахматная партия не может продолжаться бесконечно. Обозначим через A число различных позиций на шахматной доске. Очевидно, через 3A ходов хотя бы одна из позиций повторится трижды (мы считаем, что при этом партия заканчивается вничью автоматически, на самом деле по шахматному кодексу соответствующая сторона должна потребовать ничью до совершения своего хода, приводящего к троекратному повторению). Таким образом, самая длинная шахматная партия не может длиться более 3A ходов. К сожалению, ответить на вопрос, чему равно A, практически невозможно. Ведь недостаточно подсчитать число различных расположений фигур на доске, надо еще выяснить о каждом из них, может ли оно получиться в реальной партии. Точное число ходов в самой длинной партии будет получено ниже на основании другого ничейного правила.
Любопытно, что еще полвека назад вместо правила о троекратном повторении позиции действовало правило о троекратном повторении серии ходов. Как будто, это правило не отличается от современного - в том смысле, что и оно не позволяет "сыграть" бесконечную партию. Об этом, в частности, писал М. Эйве в одном математическом журнале. Однако, как ни странно, справедливо следующее утверждение.
Существует бесконечная шахматная партия, в которой ни одна как угодно длинная серия ходов не повторяется три раза подряд.
Оказывается, что "до бесконечности" по доске могут перемещаться одни короли; более того, каждому из них достаточно иметь в распоряжении всего три поля! Пусть, например, белый король ходит по полям a1, a2, b1, а черный по полям g8, h8, h7 (других фигур на доске нет). Обозначим ход королей по часовой стрелке через 1, а против часовой,стрелки через 2. Если начальное положение фиксировано, то всякому передвижению королей соответствует определенная последовательность из единиц и двоек. Верно и обратное: любая последовательность из единиц и двоек задает некоторое передвижение королей. Пусть короли стоят на угловых полях доски (белый - на a1, черный - на h8), тогда последовательности 12 21 21 12 21 12 соответствуют такие ходы: 1. Крa2 (первый член последовательности 1 - белый король идёт по часовой стрелке) 1...Крg8 (второй член 2 - черный король идет против часовой стрелки) 2. Крa1 Крh8 3. Крb1 Крh7 4. Крa1 Крh8 5. Крb1 Крh7 6. Крa1 Крh8.
Итак, нам осталось выяснить, существует ли бесконечная последовательность цифр 1 и 2, в которой нет трех одинаковых, рядом стоящих групп цифр. Решение этой чисто математической задачи можно найти в книге А.М. Яглома, И.М. Яглома (см. стр. 174). Доказано, что искомая последовательность существует и, следовательно, возможна бесконечная партия, в которой ни одна серия ходов не повторяется три раза подряд. Таким образом, правило о троекратном повторении позиции является более "точным", чем о троекратном повторении серии ходов.
Последний вид ничьей (кроме, разумеется, самого простого, когда один из противников предлагает мир, а другой соглашается) связан с правилом 50 ходов, которое заключается в следующем. Если пятьдесят ходов подряд не была разменена ни одна фигура и ни одна пешка не продвинулась вперед, партия автоматически заканчивается вничью (на самом деле вновь ничью необходимо потребовать). Это правило позволяет оценить число ходов в самой длинной шахматной партии.
Проведем необходимые расчеты.
Шестнадцать пешек в процессе игры могут сделать максимум 16•6=96 ходов. Пусть все эти ходы сделаны - тогда пешки взяли по крайней мере восемь фигур (если пешки, стоящие на одной вертикали, проходят "сквозь друг друга", то осуществляется хотя бы одно взятие). Если было произведено ровно восемь взятий, то еще могут быть взяты 2•78=6 оставшихся фигур и 2•8=16 превращенных фигур, итого 6+16=22. Таким образом, общее число взятий и движений пешек не более 96+22=118. Очевидно, если число движений меньше 96, то общее число ходов пешек и взятий может только уменьшиться. Поскольку между каждыми двумя продвижениями пешек или взятиями может быть сделано не более 50 ходов (точнее говоря, на 50-м ходу какая-нибудь пешка должна продвинуться или какая-нибудь фигура должна быть взята), а после последнего взятия партия сразу прекращается (ла доске остались одни короли), то ее общая продолжительность не более 50•118=5900 ходов. Более тонкий, чисто шахматный анализ показывает, что самая длинная партия тянется на два хода меньше - 5898.
Поищем что-то подобное на английском.
Находим ссылку:
()
Subject: number of legal chess positions
From the Encyclopedia of Integer Sequences:
%I A007545 M5100 %S A007545 1,20,400,8902,197742,4897256,120921506,3284294545,88867026005 %N A007545 Number of chess games with $n$ moves. %R A007545 ken. thompson %K A007545 fini %O A007545 0,2 %A A007545 njas - - - - - - - - - - - - - - - - - - - - - - - The following game position estimates are well-known:
Chess: 10^43 The estimate 64!/(32!*8!^2*2!^6) ~= 10^43 is given by Shannon in his seminal paper "Programming a Computer for Playing Chess", Phil. Mag. 41 (1950) 256-275 ( also in D. Levy's "Computer Chess Compendium" ). As most everyone knows, we are far from solving the game of chess.
Checkers: 10^18 For checkers, Jon Schaeffer estimates 5*10^20 plausible positions with 10^18 reachable under the rules of the game. But solving may require only the square root of the number of positions in the search space i.e. 10^9. The trick is finding which 10^9 positions to use. His World champion program Chinook has access to all 8 piece databases (444 billion positions). [source: rec.games.chess.computer 7/17/95]. Thus there is hope that some day checkers may be solved.
Merrils: 10^10 Merrils (Nine Men's Morris) has been solved, see the URL below.
As might be expected, the number of positions (size of the state space) is thought to be a good measure of the complexity of these games. For further details see the following excellent survey on exhaustive search: ALL THE NEEDLES IN A HAYSTACK: CAN EXHAUSTIVE SEARCH OVERCOME COMBINATORIAL CHAOS? Location:
Here's a relevant excerpt:
Although a direct comparison of different enumeration problems is not easy, due to their state spaces of different structure and varying connectivity, it is striking that at present, the size of state spaces of various solved problems, including Merrils, is of the order of 10^10 positions. The empirical fact that the raw size of the state space is the dominant parameter that affects complexity might be explained by the observation that the structure of all these spaces shows no regularity - they appear to be random graphs. Without predictable regularity to exploit, all exhaustive searches look like random walks in a random graph. Thus, the most telling indicator of complexity is the size of the space, and its connectivity is second.
Finally I'll leave you with this excerpt:
Exhaustive search is truly a creation of the computer era. Although the history of mathematics records amazing feats of paper-and-pencil computation, as a human activity, exhaustive search is boring, error-prone, exhausting, and never gets very far anyway. As a cautionary note, if any is needed, Ludolph van Ceulen died of exhaustion in 1610 after using regular polygons of 2^62 sides to obtain 35 decimal digits of Pi - they are engraved on his tombstone.
-Bill Dubuque, 15. Aug. 1996
Еще одна ссылка:
()
И, наконец:
()
Это сообщение отредактировал zenker - 6/12/2006, 21:58
