Есть ли идеальный алгоритм для шахмат?
Недавно я обсуждал с человеком, не занимающимся программированием, возможности шахматных компьютеров. Я плохо разбираюсь в теории, но думаю, что знаю достаточно.
Я утверждал, что не может существовать детерминированная машина Тьюринга, которая всегда побеждала в шахматах или заходила в тупик. Я думаю, что даже если вы исследуете все пространство всех комбинаций ходов player1 / 2, единственный ход, который компьютер выбирает на каждом шаге, основан на эвристике. Основываясь на эвристике, он не обязательно превосходит ВСЕ ходы, которые мог сделать оппонент.
Мой друг, напротив, думал, что компьютер всегда будет побеждать или иметь ничью, если он никогда не сделает «ошибочный» ход (как вы это определяете?). Однако, будучи программистом, принявшим CS, я знаю, что даже ваш правильный выбор - с учетом мудрого оппонента - может в конце концов заставить вас сделать «ошибочные» ходы. Даже если вы все знаете, ваш следующий шаг - это жадный поиск эвристики.
Большинство шахматных компьютеров пытаются сопоставить возможный конец игры с текущей игрой, что по сути является отслеживанием динамического программирования. Опять же, рассматриваемого эндшпиля можно избежать.
Обновлено: Хм ... похоже, я взъерошил здесь несколько перьев. Это хорошо.
Если подумать еще раз, кажется, что нет теоретической проблемы с решением такой конечной игры, как шахматы. Я бы сказал, что шахматы немного сложнее шашек в том смысле, что выигрыш не обязательно достигается численным исчерпанием фигур, а матом. Мое первоначальное утверждение, вероятно, неверно, но опять же, я думаю, что указал на то, что еще не доказано (формально) удовлетворительно.
Я предполагаю, что мой мысленный эксперимент заключался в том, что всякий раз, когда берется ветка в дереве, алгоритм (или запомненные пути) должен находить путь к партнеру (без объединения) для любой возможной ветви на ходах противника. После обсуждения я куплю, что, учитывая больше памяти, чем мы можем мечтать, все эти пути могут быть найдены.
«Думаете, я указал на то, что еще не доказано удовлетворительно»? На что вы указали, что не доказано формально?
да! как может быть 20 разных ответов на такой чёрно-белый вопрос! (не каламбур).
Меня тоже удивляет количество людей, которые публикуют свои умозрительные ответы, не зная, что ответ на самом деле был определен математически - ответ в том смысле, что доказано, что у шахмат есть решение - просто непрактично вычислять его.
Напоминает анекдот про компьютер Perfect Chess Playing. Играя белыми, он думает, думает, думает, а потом .... сдается!
Кстати, я заметил, что нашел нижнюю границу рейтинга идеального игрока - unclejerry9466728.wordpress.com/2018/12/20/172.
Ответы 27
Речь идет не о компьютерах, а только об игре в шахматы.
Вопрос в том, существует ли безотказная стратегия, чтобы никогда не проиграть игру? Если такая стратегия существует, то компьютер, который знает все, всегда может ее использовать, и это больше не эвристика.
Например, в крестики-нолики обычно играют на основе эвристики. Но существует безотказная стратегия. Что бы ни делал противник, вы всегда найдете способ не проиграть игру, если сделаете это с самого начала.
Так что вам нужно будет доказать, что такая стратегия существует или нет и для шахмат. Это в основном то же самое, только пространство возможных ходов намного больше.
Итак, у кого было желание проголосовать против моего ответа? Что в этом плохого? Хотите быть впереди?
@ypnos, я вообще не голосовал против вашего ответа. Я просто прокомментировал, чтобы не допустить, чтобы вас сбили случайные отрицательные голоса. Вы набрали 30 повторений и проиграли только 1. Кроме того, +1;)
Несколько причин против. 1) Известно, что существует алгоритм решения игры, просто алгоритм нецелесообразно рассчитывать по какой-либо мыслимой технологии. 2) Решение игры НЕ подразумевает наличие безотказной стратегии. Крестики-нолики решены, но для второго игрока нет стратегии, позволяющей избежать проигрыша.
«Речь идет не о компьютерах, а только об игре в шахматы». Ну, компьютерная наука на самом деле не о компьютерах. Они всего лишь инструмент. Информатика работает без компьютеров.
На самом деле это вопрос о компьютерах, поскольку вопрос в том, может ли существовать машина Тьюринга (= компьютер), которая решает шахматы.
Ваш конец аргументации подтверждается тем, как работают современные шахматные программы Теперь. Они работают так, потому что программировать шахматную программу для детерминированной работы слишком ресурсоемко. Они не обязательно так работают с всегда. Возможно, что когда-нибудь шахматы станут решено, и если это произойдет, скорее всего, это будет решено компьютером.
Для справки, есть компьютеры, которые могут выиграть или сыграть вничью на шашки. Я не уверен, можно ли сделать то же самое с шахматами. Количество ходов намного больше. Кроме того, все меняется, потому что фигуры могут двигаться в любом направлении, а не только вперед и назад. Я думаю, хотя я не уверен, что шахматы детерминированы, но что существует слишком много возможных ходов для компьютера, чтобы в настоящее время определять все ходы за разумный промежуток времени.
Это можно сделать, но можно ли это сделать на компьютере, который мы, вероятно, когда-нибудь увидим?
Наверное, не при нашей жизни. Все действительно интересные исследования в этой области проводятся в игре Go. :)
IIRC большинству 6-летних может быть любой компьютер в Go.
На подсчет 500 миллиардов позиций идеальных шашек ушло 18 лет. Прикольные штучки cs.ualberta.ca/~chinook
@BCS: Больше нет. Лучшие программы го сейчас обгоняют игроков дан (профессионального) уровня.
УХ ТЫ! Связь? а с каким железом?
@BCS: Вот и все, usgo.org/index.php?%23_id=4602
Как только шахматы будут решены, им придется работать над го. В го есть более простые правила, но это на много порядков более серьезная проблема, чем шахматы.
@Bill: Лучшие программы Го иногда могут побить игроков Дэна на досках 9х9 (для досуга). На обычных досках 19x19 компьютеры далеки от того, чтобы победить их - лучшее, что когда-либо делал компьютер против профессионала - это победа с гандикапом 9, самым большим типичным гандикапом.
@BlueRaja: Это было в 2008 году. Я не знаю, каков текущий рекорд, но MoGo побила профи с 6 и 7 камнями на 19x19. ireport.cnn.com/docs/DOC-214010
Я думаю, ты мертв. Такие машины, как Deep Blue и Deep Thought, запрограммированы с использованием ряда предопределенных игр и умных алгоритмов для разбора деревьев на концах этих игр. Это, конечно, резкое упрощение. Всегда есть шанс «обыграть» компьютер по ходу игры. Под этим я подразумеваю движение, которое заставляет компьютер делать ход, который не является оптимальным (каким бы он ни был). Если компьютер не может найти лучший путь до истечения срока, установленного для переезда, он вполне может совершить ошибку, выбрав один из менее желательных путей.
Есть еще один класс шахматных программ, в которых используется настоящее машинное обучение или алгоритмы генетического программирования / эволюции. Некоторые программы были разработаны и используют нейронные сети и др. Для принятия решений. В этом случае я мог бы предположить, что компьютер может делать «ошибки», но все же в конечном итоге одерживает победу.
Вы можете прочитать увлекательную книгу об этом типе GP под названием Блондинка24. Речь идет о шашках, но можно применить и к шахматам.
Вот как вы обыграли современные компьютеры в шахматах. Завтра будет лучше. Однако я согласен с вами в том, что Blondie24 очарователен.
Проголосовал снова. Этот пост не заслуживает отрицательной оценки.
К сожалению, проблема шахматной игры слишком велика, чтобы машинное обучение работало. Они никогда не смогли бы заставить обучающуюся шахматную программу даже новичку играть без промахов. Эвристика лучше. Но Грубая сила была даже лучше. Машинное обучение извлекло уроки только из неудач с шахматами.
Шахматные программы не допускают краткосрочных ошибок, а лучшие программы играют лучше, чем чемпионы мира. Я думаю, что последняя версия Rybka 64 bit имеет рейтинг 3200 ELO.
Некоторые игры действительно решены. Крестики-нолики - это очень простой способ создать ИИ, который всегда будет побеждать или иметь ничью. Недавно также была решена проблема Connect 4 (и было показано, что это несправедливо по отношению ко второму игроку, поскольку идеальная игра приведет к его поражению).
Однако шахматы так и не решены, и я не думаю, что есть какие-либо доказательства того, что это честная игра (т. Е. Приводит ли идеальная игра к ничьей). Однако, если говорить строго с теоретической точки зрения, у шахмат есть конечное число возможных конфигураций фигур. Следовательно, пространство поиска конечно (хотя и невероятно велико). Следовательно, детерминированная машина Тьюринга, которая могла бы идеально играть, действительно существует. А вот удастся ли его когда-нибудь построить - другой вопрос.
«Я утверждал, что не может существовать детерминированная машина Тьюринга, которая всегда побеждала в шахматах или заходила в тупик».
Вы не совсем правы. Может быть такая машина. Проблема заключается в огромных размерах пространства состояний, которое ему придется искать. Конечно, просто В САМОМ ДЕЛЕ большой.
Вот почему шахматы прибегают к эвристике - пространство состояний слишком велико (но конечно). Даже перечисление - не говоря уже о поиске каждого идеального хода по каждому ходу каждой возможной игры - было бы очень, очень большой проблемой поиска.
Дебюты составлены таким образом, чтобы вы попали в середину игры, которая дает вам «сильную» позицию. Неизвестный результат. Даже эндшпиль - когда фигур меньше - сложно перечислить, чтобы определить лучший следующий ход. Технически они конечны. Но альтернатив огромное количество. Даже 2 ладьи + король имеют примерно 22 возможных следующих хода. А если мат занимает 6 ходов, получается 12 855 002 631 049 216 ходов.
Посчитайте начальные ходы. Хотя в игре всего около 20 начальных ходов, есть примерно 30 или около того вторых ходов, поэтому к третьему ходу мы смотрим на 360 000 альтернативных состояний игры.
Но шахматы (технически) конечны. Огромный, но конечный. Есть идеальная информация. Определены начальное и конечное состояния. Нет подбрасывания монеты или броска костей.
Все эндшпили с 6 и менее фигурами были перечислены и решены. Смотрите здесь tablebase и bitbase: en.wikipedia.org/wiki/Tablebase. Например, есть эндшпиль KQNKRBN, где требуется 517 ходов, чтобы заставить мат! Но общее количество шахматных партий составляет около (10 ^ (10 ^ 50)).
Сценарий на победу - это одно. Другое дело - исчерпывающе перечислить. В любом случае информация идеальна - все известно - игра детерминирована по определению.
Погода также теоретически детерминирована, но это еще одна проблема, которую мы никогда не «решим» из-за большого количества переменных и ее нелинейности.
@RoadWarrior: не согласен. Случайное относится к погоде. Бог кидает кости. Случайность не применима к шахматам - по определению. В шахматах есть полная информация. Погода имеет квантовые эффекты - она не может быть полной.
Погоду сложно прогнозировать из-за хаотических нелинейных факторов, а не из-за каких-либо квантовых эффектов. При наличии достаточных вычислительных мощностей и знаний мы могли бы теоретически создать «правильный» прогноз погоды.
@RoadWarrior: В этом случае вся вселенная (а) детерминирована и (б) у меня нет свободной воли, мои ответы полностью определяются историей вселенной на сегодняшний день. Не уверен, что мне это нравится. Я предпочитаю случайный выбор.
Нет, этого не следует. Причина, по которой погоду теоретически можно предсказать на ближайшее будущее, заключается в том, что квантовые эффекты имеют низкую вероятность очень существенно повлиять на ваш прогноз в этом масштабе времени.
Чтобы было понятнее, nn-линейные хаотические эффекты гораздо более значимы (для вашего прогноза), чем квантовые эффекты.
Позвольте мне прояснить это. В шахматах есть конечные, известные, ограниченные правила. У погоды даже нет «правил». Лучшее, что вы можете сделать, - это теоретизировать и моделировать то, что вы наблюдаете. Шахматы по определению конечны и полны. Погода не конечна, за исключением того, что Вселенная «конечна».
Компьютеры сегодня лучше людей. Алгоритмы и процессоры теперь заставляют их разумно искать самые правильные линии и немного глубже, чем это делают лучшие гроссмейстеры. Их начальные книги и финальные игры почти идеальны, и они легко «видят» большинство ловушек.
@lkessler: вопрос не «глубже» - он «идеально». Есть ли идеальный вид на все возможные будущие позиции. Есть для крестиков-ноликов. Теоретически шахматы могут иметь полное и идеальное представление обо всех будущих позициях; практически это сложно сделать.
@ S.Lott: Теперь не знаю, почему я остановился на своем комментарии. Я подумал, что это было в ответ на другой комментарий. В любом случае проигнорируйте мой комментарий и вместо этого посмотрите мой ответ на свой вопрос.
@lkessler: (1) вы можете удалять комментарии - это лучше, чем извиняться или объяснять. (2) это не мой вопрос.
@ S.Lott: Я не уверен, как «Свободная воля» может находиться на вершине Случайной Вселенной лучше, чем в Детерминированной Вселенной [кто принимает решения?]. Если вы не читали «Свобода эволюционирует» Дэна Деннета, я бы порекомендовал ее - он использует фразу «исключимость»: он утверждает, что агент, живущий в детерминированной Вселенной, все еще может принимать решения, которые влияют на его будущее. Я не совсем понимаю, но это делает интересное чтение - он использует жизнь Дж. Конвея, чтобы проиллюстрировать это. [Также, если вы еще этого не сделали: «Тени разума», Р. Пенроуз - опять же, я не понимаю » я действительно понял :-), но интересно]
@monjohnny: возможно, интересно, но не для шахмат и этого вопроса. Шахматы конечно. Метафизические дебаты между детерминизмом и свободой воли неприменимы к тому факту, что пространство шахматной игры конечно.
@ S.Lott: Вы могли бы быть правы, но я не уверен, что это было доказано. Я согласен с тем, что существует фиксированное количество `` состояний '' - но есть последовательности ходов, которые могут поддерживать игру вечно - упрощенный Например, игрок A перемещает коня вперед и назад между двумя позициями - игрок B отвечает эквивалентным ходом: мы можем легко заметить это, поскольку состояние доски будет повторяться каждые 4 поколения. для завершения потребуется на порядки больше времени: в таком случае алгоритм должен будет знать и о них. Может быть, это бесконечные повторяющиеся (или почти повторяющиеся) шаблоны?
Кроме того, я не имею в виду, что алгоритм / игрок намеренно циклически повторяют ходы в бесконечном цикле. Я просто предполагаю, что если эти циклы действительно существуют, то игроки могут попасть в бесконечный цикл: если они не отслеживают все ходы в игре на текущий момент, что потребует бесконечной памяти. [алгоритм не мог знать, что шаблоны будут продолжать повторяться - он не может сделать вывод о следующем шаге игрока].
Я думаю то, что я пытаюсь сказать: шахматы конечны в пространстве, но, возможно, не во времени .... огоооооооаааааааааааааааааааааааааааааааааааааааааааааааааааааааа ...
@monojohnny: Правила запрещают повторение одной и той же позиции трижды. Шахматы просто конечны. Он большой, но конечный.
Не осознавал этого, но насчет правила вы правы. en.wikipedia.org/wiki/Threefold_repetition
@ С.Лотт: Более важным правилом здесь является то, что пятьдесят ходов без пешки или взятия - это ничья (и есть по крайней мере одно исключение из этого, но оно все еще ограничено).
Вам следует взглянуть на en.wikipedia.org/wiki/… и статью Шеннона, на которую он ссылается.
@monojohnny Шахматы НЕ ограничены во времени. Правило повторения трех ходов и правило 50 ходов объединяются, чтобы гарантировать, что оно всегда будет заканчиваться.
Я должен сказать, что шахматы не БЕСКОНЕЧНЫЕ во времени.
Чтобы быть педантичным, правила трехкратного повторения и 50 ходов говорят, что игрок май объявляет игру ничьей, а не должен. Если оба игрока упорно отказывается принять ничего, кроме победы, игра может продолжаться до бесконечности.
Для игра в шашки было доказано, что программа всегда может выиграть или сделать ничью. То есть не существует выбора ходов, которые может сделать один игрок, которые заставят другого игрока проиграть.
The researchers spent almost two decades going through the 500 billion billion possible checkers positions, which is still an infinitesimally small fraction of the number of chess positions, by the way. The checkers effort included top players, who helped the research team program checkers rules of thumb into software that categorized moves as successful or unsuccessful. Then the researchers let the program run, on an average of 50 computers daily. Some days, the program ran on 200 machines. While the researchers monitored progress and tweaked the program accordingly. In fact, Chinook beat humans to win the checkers world championship back in 1994.
Да, вы можете решать шахматы, нет, не скоро.
Это действительно круто. Я не знал, что шашки тоже решены.
«[Ты] ты не скоро» - это немного мягко сказано. Помимо предела ожидаемой продолжительности Вселенной, у вас есть проблема с хранением - количество состояний в Chess намного превышает 500 миллиардов миллиардов шашек; фактически, это превышает количество частиц во Вселенной.
Верно. Можно решать только игры с очень низким коэффициентом ветвления (шашки, коннект4). Даже шахматы низки по сравнению с сёги, которое, в свою очередь, бледнеет по сравнению с го, которое бледнеет по сравнению с аримаа. Затем есть Тай-Кёку-сёги; images.google.co.uk/images?&q=Tai+kyoku+shogi
«[...] на самом деле, это превышает количество частиц во Вселенной.». Пока оно не превышает количество состояний частиц во Вселенной, надежда еще есть ;-)
Когда вы начинаете говорить о таких больших числах, вы более или менее игнорируете все, кроме экспоненты, поэтому, когда кто-то говорит, что в шахматах больше состояний, чем частиц во Вселенной, можно с уверенностью сказать, что их на несколько порядков больше.
Число частиц во Вселенной неизвестно, но оно должно быть огромным ... Оно включает фотоны, электроны и т. д. Число их возможных состояний еще больше. Обычно утверждается, что нижняя граница числа атомов в наблюдаемой Вселенной составляет 10 ^ 80. (10 ^ 80-1), поскольку число с основанием 10 занимает ровно одну командную строку MS-DOS. (10 ^ 80-1) ^ 25 умещается на одном экране.
что происходит, когда программа, которая всегда заставляет оппонента проигрывать, играет против самого себя ????
@JohnDemetriou: Во всех пошаговых играх движение первого или второго игрока может помешать другому игроку выиграть. Оба игрока не могут заставить другого игрока проиграть.
@BCS хм, а что, если есть прогноз, в котором, если я играю вторым игроком, а другой использует ту же эвристику, что и я, то действительно следуйте этой эвристике, чтобы выиграть, и если у первого игрока есть аналогичная эвристика ???? ?
@JohnDemetriou: все, что вы показали, - это то, что (если вы определяете идеал как «всегда побеждает») не может быть идеальной стратегии для обоих игроков (или стратегии, идеальной для обоих игроков). Это не мешает стратегии, которая идеально подходит для того или иного игрока (например, соединение 4 позволяет первому игроку принудительно выиграть, en.wikipedia.org/wiki/Solved_game).
Я говорю, что если есть идеальный алгоритм и он есть у обоих игроков, будет неопределенное количество вероятностей, что алгоритм может изменить, чтобы он был идеальным.
@JohnDemetriou: Вам не нужна эвристика. Вы можете просто просчитать вариант игры до конца и узнать ее исход - не догадываясь! Это займет почти бесконечное время, но его завершение за конечное время ...
@all: если вы просто используете простой рекурсивный алгоритм с поиском в глубину, вам не нужно много оперативной памяти, так как вам нужно только сохранить текущее состояние поиска по текущему поисковому пути. Просто просчитайте все варианты ходов до конца и на каждом шаге рекурсии сделайте один из лучших ходов (выигрыш, ничья, проигрыш) и рекурсивно верните результат как результат игры. Это можно было сделать даже на старом компьютере 1990-х годов. Этот алгоритм не очень эффективен, но сработает. Единственная проблема: время! Нынешний компьютер, использующий этот алгоритм, не завершит вычисления в течение любого срока жизни.
@StefanK. IIRC это даже не закончится за время жизни нашего солнца.
@BCS. Что ж, это напоминает мне «Автостопом по Галактике». Результат - 42, но никто не знает ответа ... Может быть, вопрос просто забыли ... и я действительно решил проблему: в 1800-х годах люди записывали шахматные координаты как номер поля (от 1 до 64). Может быть, 42 - это просто ответ на вопрос «Какой первый оптимальный ход в шахматах?». И ответ - после долгих долгих вычислений - был: 42 ... "цифра [пешка] до 42" или в сокращенной алгебраической нотации: b3 (= поле # 42).
if you search the entire space of all combinations of player1/2 moves, the single move that the computer decides upon at each step is based on a heuristic.
Здесь есть две конкурирующие идеи. Во-первых, вы просматриваете все возможные ходы, а во-вторых, вы принимаете решение на основе эвристики. Эвристика - это система для правильного предположения. Если вы перебираете все возможные ходы, вы больше не гадаете.
Собственно, цитата верна. Программы просматривают все возможные ходы для обеих сторон в позиции ток и используют эвристику, чтобы найти хороший ход, чтобы вести игру в направлении, благоприятном для компьютера.
Нет, они не рассматривают все возможные ходы. Они используют эвристику нулевого хода для обрезки дерева.
С точки зрения теории игр, о которой идет речь, ответ - да. В шахматы можно играть отлично. Игровое пространство известно / предсказуемо, и да, если бы у вас были квантовые компьютеры внука, вы, вероятно, могли бы исключить все эвристики.
Сегодня вы можете написать идеальную машину для игры в крестики-нолики на любом языке сценариев, и она будет отлично работать в реальном времени.
Отелло - еще одна игра, в которую современные компьютеры могут легко играть отлично, но памяти и процессору машины потребуется небольшая помощь.
Шахматы теоретически возможны, но практически невозможны (в 2008 году)
i-Go сложен, его пространство возможностей выходит за рамки количества атомов во Вселенной, поэтому нам может потребоваться некоторое время, чтобы создать идеальную машину i-Go.
Это неттеория игры
Технически это комбинаторная теория игр.
Шахматы - это пример матричной игры, которая по определению имеет оптимальный результат (подумайте о равновесии по Нэшу). Если каждый из игроков 1 и 2 будет делать оптимальные ходы, ВСЕГДА будет достигнут определенный результат (будет ли это выигрыш-ничья-поражение, пока неизвестно).
Это может быть решаемо, но меня что-то беспокоит: Даже если бы можно было пройти по всему дереву, все равно невозможно предсказать следующий ход оппонента. Мы всегда должны основывать свой следующий ход на состоянии оппонента и делать «лучший» доступный ход. Затем, исходя из следующего состояния, мы делаем это снова. Итак, наш оптимальный ход может быть оптимальным, если противник будет двигаться определенным образом. Для некоторых ходов оппонента наш последний ход мог оказаться неоптимальным.
Я просто не понимаю, как на каждом шагу может быть «идеальный» ход.
Для этого для каждого состояния [в текущей игре] должен быть путь в дереве, ведущий к победе, независимо от следующего хода оппонента (как в крестики-нолики), и у меня есть сложный время понять это.
Идеальный ход определяется стратегией «минимакс»: это ход, который максимизирует ваш минимально возможный счет (с учетом всех возможных ходов, которые может сделать оппонент). Или, другими словами, предполагается, что противник также играет отлично.
Однако это интересный момент. Может ли возникнуть ситуация, когда ответ на лучший из возможных ходов поставит вас в невыгодное положение, если ваш противник не сделает лучший из возможных ходов? Какие последствия это имеет?
Я не математик и не очень хороший шахматист; Я также предположил, что теоретически (если будет известно все дерево игры), что ответ на этот вопрос - «да». Однако теперь, когда вы упомянули об этой проблеме [выбор другого игрока], означает ли это, что система потенциально непредсказуема? Есть ли в игре середина, когда другой игрок может поставить в невыгодное положение? Это немного похоже на то, что персептрон (нейронная сеть) может выучить «ИЛИ» и «И», но никогда не сможет уловить «XOR»? Шахматы - пример «хаотической» системы? FWIW, ИМХО, я думаю, что на данный момент ответ кажется «не знаю».
@Nona По определению, этот ход был бы лучшим ходом. Нет никаких предположений.
@piccolbo: Лучше - один из лучших ходов. В шахматах есть позиции, в которых несколько ходов приводят к одному и тому же результату (выигрыш, ничья или поражение за одно и то же количество ходов).
Я подхожу к этой теме очень поздно, и что вы уже поняли некоторые проблемы. Но как бывший мастер и бывший профессиональный шахматный программист, я подумал, что могу добавить несколько полезных фактов и цифр. Есть несколько способов измерения сложность шахмат:
- Общее количество партий примерно 10 ^ (10 ^ 50). Это число невообразимо велико.
- Количество шахматных партий на 40 и менее ходов составляет около 10 ^ 40. Это все еще невероятно большое количество.
- Количество возможных шахматных позиций составляет порядка 10 ^ 46.
- Полное дерево поиска шахмат (число Шеннона) составляет около 10 ^ 123, исходя из среднего коэффициента ветвления 35 и средней продолжительности игры 80.
- Для сравнения, количество атомов в наблюдаемой Вселенной обычно оценивается примерно в 10 ^ 80.
- Все эндшпили из 6 или менее фигур были сопоставлен и решен.
Мой вывод: хотя шахматы теоретически решаемы, у нас никогда не будет денег, мотивации, вычислительной мощности или хранилища, чтобы когда-либо это делать.
Да брось. Вы должны по-другому взглянуть на проблему. Не думайте о количестве игр, потому что транспозиции, алгоритмы альфа-бета и тому подобное значительно сокращают это количество. Подумайте о позициях на доске (10 ^ 60) или комбинациях шахматных фигур (100 миллионов). С квантовыми вычислениями это тривиально.
Альфа-бета в этом контексте (решение шахмат) потребует совершенной функции оценки. То же самое с позициями на доске и комбинациями фигур. У нас нет идеальной оценочной функции, поэтому квантовые вычисления нам не помогают.
Каждый раз, когда я думаю, что что-то «тривиально», и я уверен, что никто этого еще не сделал, я также уверен, что ошибался хотя бы раз.
Хороший комментарий, одна придирка: сложность игрового дерева, то есть насколько велико дерево поиска для шахмат, является лучшей мерой сложности шахмат, которая является числом Шеннона, в порядке 10 ^ 120.
@RoadWarrior: Как подсчитать общее количество игр? Я полагаю, вы игнорируете случаи циклов? Кроме того, есть ли у вас общие ссылки на ресурсы по шахматному программированию? Я заинтригован...
@lkessler: Позиции в совете директоров не говорят всей истории. По крайней мере, некоторая история игры необходима для рокировки или взятия на проходе или ничьей из-за отсутствия взятия или хода пешки, и вся история для ничьей путем повторения. Более того, поскольку в последнее время это был заметный результат исследования для квантового компьютера - фактор 15, я бы сказал, что сейчас нет ничего тривиального в квантовых вычислениях.
Для сравнения: если вы можете сгенерировать все возможные шахматные позиции, вы можете тривиально перебрать любой шифр со 128-битным ключом, так как 10 ^ 46 примерно равно 2 ^ 152 или 2 ^ 153. Есть веские причины думать, что это невозможно до тепловой смерти Вселенной.
@RoadWarrior: Обрезка альфа-бета также применима при расчете игры до финальной победы / проигрыша / ничьей. Другими словами: если у черных будет один способ добиться победы, если белые сделают ход x, то белые не выберут этот ход (или должны будут сделать это и всегда проиграют). Поэтому нам не нужно больше анализировать этот вариант. Таким образом, отсечение альфа-бета также применимо, если вы не «угадываете», но «знаете» некоторые результаты дерева поиска.
Как шахматный программист 1970-х годов у меня определенно есть мнение по этому поводу. То, что я написал около 10 лет назад, в основном верно и сегодня:
«Незавершенная работа и вызовы шахматным программистам»
Тогда я думал, что мы сможем решить шахматы обычным способом, если все сделаем правильно.
Шашки были решены недавно (Ура, Университет Альберты, Канада !!!), но это было эффективно сделано грубой силой. Чтобы заниматься шахматами традиционным способом, нужно быть умнее.
Если, конечно, Квантовые вычисления не станет реальностью. Если так, то шахматы решаются так же легко, как крестики-нолики.
В начале 1970-х годов в журнале Scientific American была короткая пародия, которая привлекла мое внимание. Это было объявление о том, что шахматную партию решает русский шахматный компьютер. Он определил, что есть один идеальный ход для белых, который обеспечит победу при безупречной игре обеих сторон, и этот ход: 1. a4!
Я почти ничего не знаю о том, что на самом деле было открыто в шахматах. Но как математик я рассуждаю так:
Во-первых, мы должны помнить, что белые идут первыми, и, возможно, это дает им преимущество; может быть, это дает черным преимущество.
Теперь предположим, что у черных есть нет идеальной стратегии, которое позволяет им всегда выигрывать / пат. Это означает, что независимо от того, что делают черные, белые могут следовать своей стратегии для победы. Погодите - это означает, что является - идеальная стратегия для белых!
Это говорит нам о том, что по крайней мере один из двух игроков делает имеет идеальную стратегию, которая позволяет этому игроку всегда выигрывать или рисовать.
Тогда есть только три возможности:
- Белые всегда могут выиграть, если сыграют идеально.
- Черные всегда могут выиграть, если сыграют идеально.
- Один игрок может выиграть или сыграть вничью, если он будет играть идеально (и если оба игрока играют отлично, они всегда в патовой ситуации).
Но что из этого на самом деле верно, мы, возможно, никогда не узнаем.
Ответ на вопрос - да: должен быть идеальный алгоритм для шахмат, по крайней мере, для одного из двух игроков.
+1, это действительно отличный способ объяснить это. Не могу поверить, что никогда не думал об этом!
Почему отсутствие идеальной стратегии у черных означает, что у белых действительно идеальная стратегия? А как насчет того, чтобы у обоих игроков не было идеальной стратегии? Если бы ваше предположение было правдой, разве это не было бы верно для каждой игры для двоих, то есть в каждой игре есть идеальная стратегия?
@john: Поскольку в шахматах есть точная информация и нет случайных элементов (в отличие от многих, многих других игр для двух игроков), единственный способ, при котором не может существовать идеальная стратегия для черных, - это если белые могут добиться победы, несмотря на любую попытку черный - другими словами, если есть идеальная стратегия для белых.
@ Дэйв Шерохман: поправьте меня, если я ошибаюсь, но если то, что вы сказали, правда, разве эта тема не так проста, как «Идеальная информация и отсутствие случайности, следовательно, существует идеальная стратегия»? Если это правда, почему здесь так много дискуссий?
@john: В значительной степени. Я опубликовал этот ответ, потому что другие на самом деле не объяснили, почему это правда.
Собственно это логика не всегда держится, но так ли это в данном случае.
@john "почему здесь столько обсуждения" - потому что некоторые люди не знают ответа, но все равно публикуют здесь сообщения.
исправление: "в данном случае является истинно", извините, я никогда не замечал, что раньше у меня были неправильно упорядоченные слова
Конечно На доске всего 10 из пятидесяти возможных комбинаций фигур. Имея это в виду, чтобы сыграть в каждую комбинацию, вам нужно будет сделать менее 10 в степени пятидесяти ходов (включая повторения, умножающие это число на 3). Итак, в шахматах меньше десяти в мощности ста ходов. Просто выберите те, которые приводят к мату, и все готово.
Меня только на 99,9% убеждает утверждение о том, что размер пространства состояний не позволяет надеяться на решение.
Конечно, 10 ^ 50 - невероятно большое число. Назовем размер пространства состояний n.
Какое ограничение на количество ходов в самой продолжительной игре? Поскольку все игры заканчиваются конечным числом ходов, такая граница существует, назовем ее m.
Начиная с начального состояния, не можете ли вы перечислить все n ходов в пространстве O (m)? Конечно, это занимает O (n) времени, но аргументы размера вселенной напрямую не касаются этого. O (m) места может быть даже не очень много. Для пространства O (m) не могли бы вы также отслеживать во время этого обхода, приводит ли продолжение какого-либо состояния на пути, по которому вы проходите, к EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin или BlackMayWinOrForceDraw? (В зависимости от того, чья очередь, есть решетка, аннотируйте каждое состояние в истории вашего обхода с помощью решетки.)
Если я чего-то не упускаю, это алгоритм O (n) времени / O (m) пространства для определения, в какую из возможных категорий попадают шахматы. Википедия приводит оценку возраста Вселенной примерно в 10-60 планковских времен. Не вдаваясь в аргументы космологии, давайте предположим, что до жары / холода / любой смерти Вселенной осталось примерно столько же времени. Это оставляет нам необходимость оценивать один ход каждые 10 ^ 10-го планковского времени или каждые 10 ^ -34 секунды. Это невероятно короткий промежуток времени (примерно на 16 порядков меньше самого короткого времени, которое когда-либо наблюдалось). Давайте с оптимизмом скажем, что с супер-пупер-хорошей реализацией, работающей на вершине линии технологии настоящего или будущего неквантового P-is-a-правильного-подмножества-NP, мы могли бы надеяться оценить (возьмите на один шаг вперед, классифицируйте результирующее состояние как промежуточное состояние или одно из трех конечных состояний) с частотой 100 МГц (каждые 10 ^ -8 секунд). Поскольку этот алгоритм очень распараллеливается, нам потребуется 10 ^ 26-е таких компьютеров, или примерно по одному на каждый атом в моем теле, а также возможность собирать их результаты.
Я полагаю, что всегда есть надежда на решение проблемы с помощью грубой силы. Нам может повезти, и, исследуя только один из возможных начальных ходов белых, оба выберут один с разветвлением намного ниже среднего и тот, в котором белые всегда выигрывают или побеждают-или-ничьи.
Мы могли бы также надеяться несколько сократить определение шахмат и убедить всех, что это все еще морально та же игра. Неужели нам действительно нужно требовать, чтобы позиции повторялись 3 раза перед розыгрышем? Неужели нам действительно нужно заставить убегающую партию продемонстрировать способность убежать за 50 ходов? Кто-нибудь вообще понимает, что за фигня с правилом мимоходом? ;) Если серьезно, действительно ли нам нужно заставлять игрока двигаться (в отличие от рисования или проигрыша), когда его или ее единственный ход, чтобы избежать проверки или пат - это захват мимоходом? Можно ли ограничить выбор фигур, на которые может быть продвинута пешка, если желаемое превращение без ферзя не приводит к немедленному шаху или мату?
Я также не уверен в том, насколько разрешение каждого компьютера на основе хэша доступа к большой базе данных о поздних игровых состояниях и их возможных результатах (которые могут быть относительно осуществимы на существующем оборудовании и с существующими конечными базами данных) могло бы помочь в сокращении поиска на более раннем этапе. Очевидно, вы не можете запоминать всю функцию без хранения O (n), но вы можете выбрать большое целое число и запомнить, что многие конечные игры перечисляются в обратном порядке от каждого возможного (или даже не легко доказуемо невозможного, я полагаю) конечного состояния.
Ваше m = 5898. Правила шахмат ФИДЕ определяют, что вы должны передвигать пешку или брать фигуру (что-то, что необратимо меняет игру), по крайней мере, каждые 50 ходов (так называемое правило 50 ходов), или один из игроков может требовать ничью. Было подсчитано, что самая длинная возможная игра составляет 5898 ходов, если оба игрока будут сотрудничать и как можно скорее заявить о ничьей. Нет смысла продолжать игру, если оба игрока могут претендовать на ничью. Если игрок замечает, что проигрывает, он может потребовать ничью с тем же результатом. См .: Chess.com/blog/kurtgodden/the-longest-possible-chess-game
Примечание: m = 5898 - количество «ходов». Максимальное количество полуходов (118-3) * 100 + 3 * 99 = 11797. Вы можете найти доказательство здесь (на немецком!): de.wikipedia.org/wiki/50-Z%C3%BCge-Regel#Schachmathematik
"Is there a perfect algorithm for chess?"
Да, есть. Может, белые всегда побеждают. Может, черные всегда побеждают. Может быть, для обоих, по крайней мере, всегда одинаково. Мы не знаем, какие именно, и никогда не узнаем, но они, безусловно, существуют.
Смотрите также
Будучи довольно приличным шахматистом и тщательно изучив проблему на протяжении многих лет, я на 99,9% уверен, что стратегия префекта в шахматах для обоих игроков приведет к ничьей (так же, как это было доказано с шашками). Также есть свидетельства того, что с увеличением силы игрока увеличивается и процент ничьих.
Я знаю, что это немного неприятно, но я должен вложить сюда свои 5 центов. Компьютер или человек может закончить каждую шахматную партию, в которой он / она / она участвует, либо в выигрыше, либо в тупике.
Однако, чтобы достичь этого, вы должны точно знать все возможные движения, реакции и так далее, вплоть до каждого возможного исхода игры, и, чтобы визуализировать это или сделать простой способ анализа этой информации, подумайте о это как карта разума, которая постоянно разветвляется.
Центральный узел будет началом игры. Каждая ветвь, выходящая из каждого узла, будет символизировать ход, каждое из которых отличается от ходов своих собратьев. Представить его в этой усадьбе потребовало бы много средств, особенно если бы вы делали это на бумаге. На компьютере это, возможно, заняло бы сотни террабайт данных, так как у вас будет очень много репедативных ходов, если вы не вернете ветви.
Однако запомнить такие данные было бы неправдоподобно, если вообще возможно. Чтобы компьютер распознал наиболее оптимальный ход из (максимум) 8 мгновенно возможных ходов, было бы возможно, но не правдоподобно ... поскольку этот компьютер должен был бы иметь возможность обрабатывать все ветви, прошедшие этот ход, На всем пути к заключению подсчитайте все выводы, которые приводят к выигрышу или патовой ситуации, затем действуйте в соответствии с этим количеством выигрышных заключений против проигрышных заключений, и для этого потребуется ОЗУ, способное обрабатывать данные в террабайтах, или больше! А с современными технологиями для такого компьютера потребовалось бы больше, чем банковский баланс 5 самых богатых мужчин и / или женщин в мире!
Итак, после всех этих размышлений, это можно было сделать, однако никто не мог этого сделать. Для выполнения такой задачи потребовалось бы 30 самых ярких умов, живущих сегодня, не только в шахматах, но и в науке и компьютерных технологиях, и такая задача могла быть выполнена только (давайте полностью рассмотрим ее) ... в высшей степени гипер супер-пупер компьютер ... который не мог существовать по крайней мере столетие. Это будет сделано! Только не в этой жизни.
К 2040 году средний настольный компьютер за 1000 долларов сможет решать шашки всего за 5 секунд (5x10 ^ 20 вычислений).
Даже при такой скорости 100 таких компьютеров все равно потребуется примерно 6.34 x 10 ^ 19 годы, чтобы решить шахматы. По-прежнему неосуществимо. Даже не близко.
Примерно к 2080 году наши средние настольные компьютеры будут производить примерно 10 ^ 45 вычислений в секунду. Один компьютер будет иметь вычислительную мощность, чтобы решить шахматы примерно за 27,7 часа. Это определенно будет сделано к 2080 году, если вычислительные мощности будут продолжать расти, как это было в последние 30 лет.
К 2090 году на настольном компьютере за 1000 долларов будет достаточно вычислительной мощности, чтобы решить шахматы примерно за 1 секунду ... так что к тому времени это будет совершенно тривиально.
Учитывая, что шашки были решены в 2007 году, а вычислительная мощность для их решения за 1 секунду будет отставать примерно на 33-35 лет, мы, вероятно, можем оценить грубо, что шахматы будут решены где-то между 2055-2057 годами. Вероятно, раньше, когда станет доступно больше вычислительных мощностей (что будет через 45 лет), больше можно будет посвятить таким проектам, как этот. Однако я бы сказал, что не раньше 2050 года, а не позднее 2060 года.
В 2060 году для решения шахмат потребуется 100 среднестатистических рабочих столов 3,17 x 10 ^ 10 лет. Поймите, я использую компьютер за 1000 долларов в качестве эталона, тогда как более крупные системы и суперкомпьютеры, вероятно, будут доступны, поскольку их соотношение цена / производительность также улучшается. Кроме того, их вычислительная мощность на порядок увеличивается более быстрыми темпами. Представьте, что суперкомпьютер теперь может выполнять 2,33 x 10 ^ 15 вычислений в секунду, а компьютер за 1000 долларов - около 2 x 10 ^ 9. Для сравнения, 10 лет назад разница составляла 10 ^ 5 вместо 10 ^ 6. К 2060 году разница на порядок, вероятно, составит 10 ^ 12, и даже она может увеличиваться быстрее, чем предполагалось.
Во многом это зависит от того, есть ли у нас, людей, тяга к разгадыванию шахмат, но вычислительные мощности сделают это возможным примерно в это время (при условии, что мы продолжаем двигаться в таком темпе).
С другой стороны, игра в крестики-нолики, которая намного, намного проще, имеет 2 653 002 возможных вычисления (с открытой доской). Вычислительная мощность, позволяющая решать крестики-нолики примерно за 2,5 (1 миллион вычислений в секунду) секунд, была достигнута в 1990 году.
Возвращаясь назад, в 1955 году компьютер мог решить крестики-нолики примерно за 1 месяц (1 вычисление в секунду). Опять же, это основано на том, что вы могли бы получить за 1000 долларов, если бы вы могли упаковать его в компьютер (настольный компьютер за 1000 долларов, очевидно, не существовал в 1955 году), и этот компьютер был бы посвящен решению крестиков-ноликов .... В 1955 году этого не было. Вычисления были дорогими и не использовались бы для этой цели, хотя я не верю, что есть дата, когда крестики-нолики считались "решенными" компьютером, но я конечно, он отстает от реальной вычислительной мощности.
Кроме того, примите во внимание, что 1000 долларов через 45 лет будут стоить примерно в 4 раза меньше, чем сейчас, поэтому гораздо больше денег может быть вложено в такие проекты, как этот, в то время как вычислительная мощность будет продолжать дешеветь.
«Знаете ли вы, что продажи диско-пластинок выросли на 400% за год, закончившийся в 1976 году? Если эти тенденции сохранятся ... - Дискотека Стю
Закон Мура - вычислительная мощность удваивается каждые 18 месяцев - скорее всего, потерпит неудачу примерно в 2015 году. В противном случае придется кардинально изменить дизайн процессора компьютера. Так что 2080 год - нереальная цель.
@Philip: Тактовая частота процессоров настольных компьютеров с 2003 года увеличилась лишь незначительно, и с тех пор улучшения в основном касались увеличения кэш-памяти и нескольких ядер. Поскольку процессор с тактовой частотой 3 ГГц имеет один тактовый цикл за время, необходимое свету для перемещения на 4 дюйма / 10 см, нельзя ожидать, что тактовая частота будет увеличиваться бесконечно. Более того, параллелизм обычно затруднен. Прогнозирование экспоненциального роста в течение пятидесяти лет, когда он начал ломаться семь лет назад, не кажется безопасной ставкой.
@ Дэвид - это все правда. Но упускает из виду главное. Если вы уменьшите размер компонентов микросхемы вдвое, электроны будут работать вдвое больше при той же тактовой частоте. Это то, что подпитывает закон Мура.
@Philip: Разумеется, сокращение вдвое не может продолжаться вечно. Атом кремния составляет около четверти нанометра в поперечнике, а производство микросхем сокращается до десятков нанометров. Более того, на квантовых уровнях частицы подчиняются статистическим правилам, а не абсолютным правилам, поэтому необходимо перемещать достаточно электронов за раз, чтобы вызвать закон больших чисел. До сих пор закон Мура был чем-то средним между законом и самоисполняющимся пророчеством, но когда-нибудь это закончится довольно скоро.
@ Дэвид Я считаю, что это была моя первоначальная точка зрения. 2015 год - это ожидаемая дата, когда фотолитография перестанет справляться с малыми размерами.
@ PhilipSmith & David: Думаю, у вас просто будет больше ядер на одном компьютере за 1000 долларов. Шахматы неплохо распараллеливаются, так что это не проблема.
Я нашел этот статья Джона Маккуорри, который ссылается на работу «отца теории игр» Эрнст Фридрих Фердинанд Цермело. Делается следующий вывод:
In chess either white can force a win, or black can force a win, or both sides can force at least a draw.
Логика мне кажется разумной.
Фактически возможно для обоих игроков, чтобы иметь выигрышные стратегии в бесконечных играх без четкого упорядочивания; однако в шахматах порядок. Фактически, из-за Правило 50 ходов существует верхний предел количества ходов, которые может иметь игра, и, таким образом, существует только конечное число возможных шахматных партий (которые можно перечислить, чтобы решить точно .. теоретически, по крайней мере :)
Технически правило пятидесяти ходов, такое как повторение трех ходов (которое также ограничивает вещи - существует конечное количество возможных позиций, поэтому умножение этого числа на три дает нам верхний предел) не является ничьей причина. Скорее, это дает любому игроку возможность выиграть требовать вничью. Обычно это делает проигравший игрок, но это не обязательно. Следовательно, следующая игра является полностью законной: 1. Nc3 Nc6 2. Nb1 Nb8 3. Nc3 Nc6 4. Nb1 Nb8, повторяющееся до бесконечности. И если я не ошибаюсь, никто не опровергает, что это не результат двух идеальных алгоритмов, играющих белое и черное.
64-битная математика (= шахматная доска) и побитовые операторы (= следующие возможные ходы) - это все, что Вам нужно. Так просто. Грубая сила обычно найдет самый лучший способ. Конечно, не существует универсального алгоритма для всех позиций. В реальной жизни расчет также ограничен по времени, его остановит тайм-аут. Хорошая шахматная программа подразумевает тяжелый код (пасы, сдвоенные пешки и т. д.). Небольшой код не может быть очень сильным. Базы данных открытия и финала просто экономят время обработки, это своего рода предварительно обработанные данные. Устройство, я имею в виду - ОС, возможности потоковой передачи, среда, оборудование определяют требования. Язык программирования важен. Во всяком случае, процесс разработки интересный.
Многие ответы здесь указывают на важные теоретико-игровые моменты:
- Шахматы - это конечная, детерминированная игра с полной информацией о состоянии игры.
- Вы можете решить конечную игру и найти идеальную стратегию
- Однако шахматы настолько велики, что вы не сможете решить их полностью методом грубой силы.
Однако в этих наблюдениях упускается важный практический момент: не обязательно проходить всю игру идеально, чтобы создать непревзойденную машину.
На самом деле вполне вероятно, что вы могли бы создать непобедимую шахматную машину (то есть никогда не проиграет и всегда будет приводить к выигрышу или ничьей), не исследуя даже крошечную часть возможного пространства состояний.
Например, следующие методы значительно сокращают необходимое пространство для поиска:
- Техники обрезки деревьев, такие как Alpha / Beta или МПД-ф, уже значительно сокращают пространство поиска
- Доказуемая выигрышная позиция. Многие концовки попадают в эту категорию: вам не нужно искать, например, KR vs K, это доказанная победа. Приложив немного усилий, можно доказать еще много гарантированных побед.
- Почти гарантированные победы - для "достаточно хорошей" игры без каких-либо глупых ошибок (скажем, об ELO 2200+?) Многие шахматные позиции почти наверняка выигрывают, например, приличное материальное преимущество (например, лишний конь) без компенсирующего позиционного преимущества. Если ваша программа может форсировать такую позицию и имеет достаточно хорошую эвристику для определения позиционного преимущества, она может с уверенностью предположить, что выиграет или, по крайней мере, сыграет со 100% вероятностью.
- Эвристика поиска по дереву - при достаточно хорошем распознавании образов вы можете быстро сосредоточиться на соответствующем подмножестве «интересных» ходов. Так играют человеческие гроссмейстеры, так что это явно неплохая стратегия ... и наши алгоритмы распознавания образов постоянно улучшаются.
- Оценка риска - лучшая концепция «рискованности» позиции сделает поиск гораздо более эффективным, сосредоточив вычислительные мощности на ситуациях, в которых результат более неопределенный (это естественное расширение Поиск покоя)
При правильном сочетании вышеперечисленных приемов я с уверенностью могу утверждать, что можно создать «непревзойденную» машину для игры в шахматы. Вероятно, мы не так уж далеки от современных технологий.
Обратите внимание, что доказывать почти наверняка сложнее, чем эту машину невозможно обыграть. Вероятно, это было бы что-то вроде гипотезы Реймана - мы были бы почти уверены, что она работает идеально и имели бы эмпирические результаты, показывающие, что она никогда не проигрывала (включая несколько миллиардов стрит-дро против самой себя), но на самом деле у нас не было бы возможности Докажите это.
Дополнительное примечание относительно «совершенства»:
Я стараюсь не описывать машину как «идеальную» в теоретико-игровом смысле, потому что это подразумевает необычно сильные дополнительные условия, такие как:
- Всегда выигрывать в любой ситуации, когда можно добиться выигрыша, независимо от того, насколько сложной может быть выигрышная комбинация. На границе между победой и ничьей могут возникать ситуации, когда это чрезвычайно трудно точно рассчитать.
- Использование всей доступной информации о потенциальных недостатках в игре вашего оппонента, например, вывод о том, что ваш оппонент может быть слишком жадным, и преднамеренное использование немного более слабой линии, чем обычно, на том основании, что она имеет больший потенциал склонить вашего оппонента к ошибке. Против несовершенных оппонентов на самом деле может быть оптимальным сделать проигрыш, если вы считаете, что ваш оппонент, вероятно, не заметит принудительный выигрыш, и это дает вам более высокую вероятность выиграть самому.
Совершенство (особенно с учетом несовершенных и неизвестных противников) - это много более сложная проблема, чем просто быть непобедимым.
Наличие несовершенных противников - не настоящая проблема. Это просто позволяет идеальному игроку выигрывать / ничьей (каким бы ни был идеальный результат) за меньшее количество ходов. Оптимальный ход в каждой позиции всегда лучше или равен другим возможным ходам (по определению). Таким образом, неоптимальные ходы позволяют вашему противнику достичь оптимального конечного состояния (победа / ничья) раньше или даже позволяют добиться лучшего результата. Например, если черные всегда будут проигрывать, если белые будут играть идеально, возможно, что черные выиграют, если белые сделают только один неоптимальный ход. Но да, это должно немного усложнить анализ.
@Stefan - несовершенные противники - огромная проблема, если вам небезразлична игра оптимальный. В частности, вы можете представить себе ситуации, когда на самом деле предпочтительнее сделать ход проигрыш (то есть ход, в котором идеальный противник определенно победит вас), если вы знаете, что вероятность того, что ваш оппонент совершит ошибку, достаточно высока.
Игра оптимальный, на мой взгляд, означает достижение наилучшего результата с нулевым риском. Ваш оппонент, вероятно, «слаб», но когда вы разыгрываете этот проигрышный ход, он / она, к сожалению, может случайно сделать хороший ход. Забота о неоптимальных оппонентах актуальна только в том случае, если есть только выбор между проигрышными ходами, когда один из них имеет более высокие шансы на ошибку (неоптимальная игра) оппонента, которая фактически приведет к ничьей или победе.
Это необычное определение оптимума в теории игр. Оптимальный обычно означает максимизацию результата ожидал. В этом случае оптимальный игрок пойдет на некоторый риск, если получит лучший результат в среднем.
В таком случае вы совершенно правы!
В вашем мысленном эксперименте есть две ошибки:
Если ваша машина Тьюринга не «ограничена» (в памяти, скорости и т. д.), Вам не нужно использовать эвристику, но вы можете вычислить и оценить конечные состояния (выигрыш, проигрыш, ничья). Чтобы найти идеальную игру, вам просто нужно использовать алгоритм Minimax (см. http://en.wikipedia.org/wiki/Minimax) для вычисления оптимальных ходов для каждого игрока, что приведет к одной или нескольким оптимальным играм.
Также нет ограничений по сложности используемой эвристики. Если вы можете рассчитать идеальную игру, есть также способ вычислить на ее основе идеальную эвристику. Если нужно, это просто функция, которая отображает шахматные позиции следующим образом: «Если я нахожусь в этой ситуации S, мой лучший ход - M».
Как уже указывали другие, это закончится тремя возможными результатами: белые могут форсировать победу, черные могут форсировать победу, один из них может форсировать ничью.
Результат идеальной игры в шашки уже «вычислен». Если человечество не уничтожит себя раньше, когда-нибудь появятся и расчеты для шахмат, когда компьютеры разовьются достаточно, чтобы иметь достаточно памяти и скорости. Или у нас есть какие-то квантовые компьютеры ... Или пока кто-нибудь (исследователь, шахматный эксперт, гений) не найдет какие-то алгоритмы, значительно снижающие сложность игры. Приведем пример: какова сумма всех чисел от 1 до 1000? Вы можете вычислить 1 + 2 + 3 + 4 + 5 ... + 999 + 1000 или просто вычислить: N * (N + 1) / 2 с N = 1000; result = 500500. А теперь представьте, что вы не знаете об этой формуле, вы не знаете о математической индукции, вы даже не знаете, как умножать или складывать числа ... Итак, возможно, что в настоящее время существует неизвестный алгоритм, который в конечном итоге снижает сложность этой игры, и для расчета лучшего хода на текущем компьютере потребуется всего 5 минут. Может быть, можно было бы даже оценить его как человека с ручкой и бумагой или даже мысленно, если бы потратить немного больше времени.
Итак, быстрый ответ: если человечество выживет достаточно долго, это всего лишь вопрос времени!
Это прекрасно решаемо.
Всего 10 ^ 50 нечетных позиций. Для каждой позиции, по моим подсчетам, требуется как минимум 64 круглых байта для хранения (каждый квадрат имеет: 2 бита принадлежности, 3 бита). Как только они сопоставлены, позиции, которые являются матами, могут быть идентифицированы, и позиции могут быть сравнены, чтобы сформировать взаимосвязь, показывающую, какие позиции ведут к другим позициям в большом дереве результатов.
Затем программе нужно найти только самые низкие корни матов только с одной стороны, если такая вещь существует. В любом случае шахматы были решены довольно просто в конце первого абзаца.
Математически шахматы были решены с помощью Минимаксный алгоритм, восходящего к 1920-м годам (найденного Борелем или фон Нейманом). Таким образом, машина Тьюринга действительно может играть в идеальные шахматы.
Однако вычислительная сложность шахмат делает это практически невозможным. Текущие движки используют несколько улучшений и эвристик. Лучшие движки сегодня превзошли лучших людей с точки зрения игровой силы, но из-за эвристики, которую они используют, они могут не работать идеально, если задано бесконечное время (например, хеш-коллизии могут привести к неверным результатам).
Ближайшим из имеющихся у нас с точки зрения идеальной игры является финальные столы. Типичный метод их создания называется ретроградный анализ. В настоящее время решены все позиции до шести фигур.
да, в математике шахматы классифицируются как определенная игра, что означает, что у них есть идеальный алгоритм для каждого первого игрока, это доказано даже для бесконечной шахматной доски, поэтому однажды, вероятно, квантовый ИИ найдет идеальную стратегию, и игра ушла
Подробнее об этом в этом видео: https://thewikihow.com/video_PN-I6u-AxMg
Есть также квантовые шахматы, где нет математического доказательства того, что это определенная игра http://store.steampowered.com/app/453870/Quantum_Chess/
а вот подробное видео про квантовые шахматы https://chess24.com/en/read/news/quantum-chess
За него проголосовали против, потому что люди думают, что когда вы говорите «квантовый», это поверхностное воображаемое знание, но на самом деле я упомянул это в качестве примечания, после чего ответил на вопрос.
+1: отличная тема. Тем не менее, я думаю, что это должно быть вики-фидом, о чем свидетельствует разнообразие и объем ответов.