Comments 71
Хорошо что я не знал что для крестиков-ноликов нужно столько узлов, и давным-давно, еще в школе, сделал крестики-нолики заложив все варианты ходов (как я считал), получилось около 1000 строк на бэйсике.
Большая часть узлов представляют собой повороты и отражения друг друга. Если их считать эквивалентными, остается и правда очень мало.
1000!!!
На мк 61 оптимальная программа умещалась в отведенные 115 инструкций.
Калькулятор выигрывал в 8 из 9 вариантов первого хода человека. Если же первый ход был на середину поля — игра заканчивалась в ничью.
На мк 61 оптимальная программа умещалась в отведенные 115 инструкций.
Калькулятор выигрывал в 8 из 9 вариантов первого хода человека. Если же первый ход был на середину поля — игра заканчивалась в ничью.
Про шашки — класс, что уже сейчас компьютеры все просчитали :-) Интересно, что если такой компьютер натравить на такой же компьютер? :-)
И никогда не задумывался над тем, что и в шахматах ТЕОРЕТИЧЕСКИ можно перебрать все партии и играть безпроигрышно
И никогда не задумывался над тем, что и в шахматах ТЕОРЕТИЧЕСКИ можно перебрать все партии и играть безпроигрышно
>> Про шашки — класс, что уже сейчас компьютеры все просчитали :-) Интересно, что если такой компьютер натравить на такой же компьютер? :-)
Будет ничья.
>> И никогда не задумывался над тем, что и в шахматах ТЕОРЕТИЧЕСКИ можно перебрать все партии и играть безпроигрышно.
Практически во всех таких играх будет ничья, за исключением го (потому что там есть дробное коми) и некоторых других. Есть интересная статья: en.wikipedia.org/wiki/Solved_game (посмотрите, как часто встречается draw, т.е. ничья).
Будет ничья.
>> И никогда не задумывался над тем, что и в шахматах ТЕОРЕТИЧЕСКИ можно перебрать все партии и играть безпроигрышно.
Практически во всех таких играх будет ничья, за исключением го (потому что там есть дробное коми) и некоторых других. Есть интересная статья: en.wikipedia.org/wiki/Solved_game (посмотрите, как часто встречается draw, т.е. ничья).
Не, а откуда известно, что ничья? Ходы производятся не синхронно. Выбор, сначала, идет за белыми, это небольшое преимущество. Может быть у белых есть ходы, которые ведут к выигрышам, как бы не ходили черные?
1. Для любого первого хода белых существует первый ход черных такой что для любого второго хода белых существует второй ход черных такой что… для любого… существует… игра заканчивается вничью.
2. Существует первый ход белых такой что для любого первого хода черных… игра заканчивается вничью.
Это и значит, что при идеальной игре будет ничья.
А истинность утверждений 1 и 2 установлена с помощью перебора)
2. Существует первый ход белых такой что для любого первого хода черных… игра заканчивается вничью.
Это и значит, что при идеальной игре будет ничья.
А истинность утверждений 1 и 2 установлена с помощью перебора)
а может быть для шахмат истинность этих утверждений перебором не доказать :-) Тогда было бы круто, получилось бы, что шахматы — игра с известным исходом :-)
вспомнилось тут число ДО*УЯ (число Грэма), которое, если записывать в виде 3^3^3^3......^3, то не хватит вещества во вселенной, даже если все его пустить в чернила, не говоря уже об обычной десятичной записи :-)
вспомнилось тут число ДО*УЯ (число Грэма), которое, если записывать в виде 3^3^3^3......^3, то не хватит вещества во вселенной, даже если все его пустить в чернила, не говоря уже об обычной десятичной записи :-)
Доказать, конечно. Если у нас есть достаточно производительный компьютер или достаточное количество времени.
Для любой игры с конечным числом позиций можно найти оптимальную стратегию и определить результат, если противники играют одинаково.
Для каждой позиции, в которой ходит игрок А, будем хранить 2 бита: «А может выиграть», «И А и В могут добиться ничьей» (позиция с ненулевым первым битом приведет к выигрышу А, с нулевым первым но единичным вторым — к ничье, с обеими нулевыми — к проигрышу А). Аналогично для B.
Для позиций после хода, в которых следующий игрок выиграл/получил ничью/проиграл инициализируем эти биты очевидным образом.
Если из позиции Х, где ходит А, есть ход в позицию Y с нулевым первым битом, то инициализируем второй бит X единицей. Если из нее есть даже ход в позицию с обоими нулевыми битами, то инициализируем и первый бит единицей.
Таким образом мы доберемся до стартовой позиции.
Формально, мы можем зациклиться. Это решается разными способами. Для теоретического исследования подойдет такой. Пусть N — число всевозможных позиций. Тогда зададим новую игру, в которой позиция есть пара (позиция старой игры, i), где i — число уже сделанных ходов. Объявим, что при i = 10*N все позиции ничейные, а при меньших будем оценивать выигрыш/проигрыш/ничью по правилам старой игры. Можно показать, что исход новой игры совпадает с исходом старой.
Для любой игры с конечным числом позиций можно найти оптимальную стратегию и определить результат, если противники играют одинаково.
Для каждой позиции, в которой ходит игрок А, будем хранить 2 бита: «А может выиграть», «И А и В могут добиться ничьей» (позиция с ненулевым первым битом приведет к выигрышу А, с нулевым первым но единичным вторым — к ничье, с обеими нулевыми — к проигрышу А). Аналогично для B.
Для позиций после хода, в которых следующий игрок выиграл/получил ничью/проиграл инициализируем эти биты очевидным образом.
Если из позиции Х, где ходит А, есть ход в позицию Y с нулевым первым битом, то инициализируем второй бит X единицей. Если из нее есть даже ход в позицию с обоими нулевыми битами, то инициализируем и первый бит единицей.
Таким образом мы доберемся до стартовой позиции.
Формально, мы можем зациклиться. Это решается разными способами. Для теоретического исследования подойдет такой. Пусть N — число всевозможных позиций. Тогда зададим новую игру, в которой позиция есть пара (позиция старой игры, i), где i — число уже сделанных ходов. Объявим, что при i = 10*N все позиции ничейные, а при меньших будем оценивать выигрыш/проигрыш/ничью по правилам старой игры. Можно показать, что исход новой игры совпадает с исходом старой.
>>Для любой игры с конечным числом позиций можно найти оптимальную стратегию и определить результат, если противники играют одинаково.
Мне кажется это не совсем так, легко придумать ПОШАГОВУЮ игру с конечным числом позиций, коей являются шахматы, где даже при идеальной игре с обеих сторон выигрывает та сторона, которая ходит первой, или наоборот второй.
Простейший пример — пешечный бой, только с 1 пешкой у каждого игрока, причем белая пешка стоит на A2, а черная на B7. Ясно, что как бы белая пешка не сделала свой первый ход, черная может пойти так, что на следующий ход сожрет белую. А что буде если по две пешки у каждого игрока? А что будет если они располагаются по разному? Это все далеко не очевидные вещи.
Мне кажется это не совсем так, легко придумать ПОШАГОВУЮ игру с конечным числом позиций, коей являются шахматы, где даже при идеальной игре с обеих сторон выигрывает та сторона, которая ходит первой, или наоборот второй.
Простейший пример — пешечный бой, только с 1 пешкой у каждого игрока, причем белая пешка стоит на A2, а черная на B7. Ясно, что как бы белая пешка не сделала свой первый ход, черная может пойти так, что на следующий ход сожрет белую. А что буде если по две пешки у каждого игрока? А что будет если они располагаются по разному? Это все далеко не очевидные вещи.
Безусловно, существуют игры, в которых при оптимальной игре тот, кто начинает, может выиграть независимо от игры соперника. Существуют игры, в которых всегда может выиграть второй игрок. Существуют игры, где при оптимальной игре всегда получится ничья.
Что не так?
Что не так?
Может я не совсем точно выразился.
Я про то, что может и шахматы из числа тех, что черные могут выиграть всегда, или наоборот белые могут выиграть всегда, если будут играть идеально.
Ваше доказательство того, что шахматы при идеальной игре с обеих сторон приведут к ничье, я не совсем понял. По идее, мой пример с боем пешек, должен вписываться в вашу модель c позициями, но мой пример, при идеальной игре с обеих сторон приводит к выигрышу черных. Или вы говорили о чем-то другом и я не вкупил? :-)
Я про то, что может и шахматы из числа тех, что черные могут выиграть всегда, или наоборот белые могут выиграть всегда, если будут играть идеально.
Ваше доказательство того, что шахматы при идеальной игре с обеих сторон приведут к ничье, я не совсем понял. По идее, мой пример с боем пешек, должен вписываться в вашу модель c позициями, но мой пример, при идеальной игре с обеих сторон приводит к выигрышу черных. Или вы говорили о чем-то другом и я не вкупил? :-)
Не, ну за что минусовать то? :-) Число Грэма — крутая штука ведь! Сволочи! Они убили Кенни!
Весьма интересное утверждение, что перебрать можно все партии. На самом деле, это не совсем так: и в шахматы, и в сёги легко можно сыграть бесконечную партию. Правда, такие бесконечные партии запрещены строгими правилами турниров.
А вот перебор всех разрешённых партий возможен, правда, чем сложнее игра, тем более немыслимое количество времени на это потребуется.
А вот перебор всех разрешённых партий возможен, правда, чем сложнее игра, тем более немыслимое количество времени на это потребуется.
Согласно большинству версий правил шахмат, при повторении позиции обьявляется ничья (обычно это происходит при вечном шахе). Так как число комбинаций фигур на доске конечно, продолжительность любой игры так же будет конечна.
Представьте партию король против короля и ладьи. Если второй игрок не будет атаковать, то партия может длиться практически бесконечно.
А ситуации с повтором игровых ситуаций с учетом поворотов и симметрии не запрещены? Было бы логично, чтобы они запрещались, как в Го.
UFO just landed and posted this here
В шахматах есть так называемое правило 50-ти ходов, которое гласит, что если в течении 50 ходов ни одна фигура на доске не была убита и ни одна из пешек не сделала ход, то партия признается ничьей.
Кроме того партия признается ничьей в случае троекратного повторения на доске одной и той же позиции.
Кроме того партия признается ничьей в случае троекратного повторения на доске одной и той же позиции.
Про шашки — не класс. Речь идёт о чекерс — сильно упрощённой разновидности шашек (нельзя не только ходить в обратную сторону, но и брать шашки противника, а дамки отличаются от обычных шашек только тем, что им таки можно бить в обе стороны). Ни русские ни, тем более, «международные» стоклеточные даже близко не просчитаны.
Не буду говорить, что точно знаю, так как знаю только со слов лектора по ИИ. Там ведь в 2007, когда всё просчитали, получилось, шашки подобны крестикам-ноликам — это справедливая игра и в идеале всегда ничья (к сожалению не знаю русского термина). То есть вообще никто не может выиграть, можно только проиграть, сделав ошибку.
Честно говоря, очень поверхностное рассмотрение алгоритма, для реализации на чем-либо для новичка надо бы поглубже, с примерами. Однако, спасибо за статью, просмотрел.
Добавлю свои пять копеек:
На практике часто возникает ситуация, когда нужно не заставить компьютер играть настолько сильно, насколько возможно, а сделать ограничение по уровню игры. Далеко за примером ходить не буду — давненько уже вот в этом посте я описывал свою игру, основанную на механике Ataxx, которая тоже играется на доске за ограниченное число ходов. ИИ с помощью дерева состояний и минимаксного поиска работал отлично, но возникла одна проблема. Даже если просчитывать дерево ходов только на шаг вперед, компьютер играл весьма агрессивно, и на режим игры «Easy» (особенно для новичка) это не тянуло. Чтобы выиграть у компьютера с просчетом двух уровней требовалась уже солидная тренировка, а у трехуровневого просчета я и сам не мог выиграть (хотя пока писал игру, наигрался до жути). Получалось что компьютер надо явно ослабить, и на эту задачу я потратил больше половины времени, затраченного на программирование всей логики ИИ. Решил ее путем выбора не самого сильного хода, но у этого решения масса нюансов и подводных камней при реализации. Лучшее решение так и осталось открытым вопросом.
Начинал даже писать пост об этом, но не довел его до состояния, в котором можно было бы показать Хабру)
Добавлю свои пять копеек:
На практике часто возникает ситуация, когда нужно не заставить компьютер играть настолько сильно, насколько возможно, а сделать ограничение по уровню игры. Далеко за примером ходить не буду — давненько уже вот в этом посте я описывал свою игру, основанную на механике Ataxx, которая тоже играется на доске за ограниченное число ходов. ИИ с помощью дерева состояний и минимаксного поиска работал отлично, но возникла одна проблема. Даже если просчитывать дерево ходов только на шаг вперед, компьютер играл весьма агрессивно, и на режим игры «Easy» (особенно для новичка) это не тянуло. Чтобы выиграть у компьютера с просчетом двух уровней требовалась уже солидная тренировка, а у трехуровневого просчета я и сам не мог выиграть (хотя пока писал игру, наигрался до жути). Получалось что компьютер надо явно ослабить, и на эту задачу я потратил больше половины времени, затраченного на программирование всей логики ИИ. Решил ее путем выбора не самого сильного хода, но у этого решения масса нюансов и подводных камней при реализации. Лучшее решение так и осталось открытым вопросом.
Начинал даже писать пост об этом, но не довел его до состояния, в котором можно было бы показать Хабру)
Эта проблема всегда актуальна, когда возможен идеал игры со стороны компьютера.
Например, когда изучал создание ботов для стрелялок, быстро выяснилось, что сделать ботов, с любого расстояния убивающих игрока первым выстрелом, очень легко, а вот сделать их так, чтобы с ними было интересно и одновременно тяжело играть — огромная проблема.
Например, когда изучал создание ботов для стрелялок, быстро выяснилось, что сделать ботов, с любого расстояния убивающих игрока первым выстрелом, очень легко, а вот сделать их так, чтобы с ними было интересно и одновременно тяжело играть — огромная проблема.
Я в своё время разрабатывал направление (оно и сейчас есть, просто времени на него мало) применения machine learning в данной задаче.
Скажем, бота для CS можно натренировать на примерах поведения игроков разной степени мастерства. Этим убиваются сразу два зайца: получаем AI разного уровня и ещё и с высоким believability factor'ом, то есть по поведению похожего на человека, а не на робота.
Скажем, бота для CS можно натренировать на примерах поведения игроков разной степени мастерства. Этим убиваются сразу два зайца: получаем AI разного уровня и ещё и с высоким believability factor'ом, то есть по поведению похожего на человека, а не на робота.
не подскажите как такое реализовать?
если при этом еще и вейпойнты обрабатывать надо.
Ну, здесь как и везде магии нет — есть миллион тонкостей, зависящих от конкретной игры.
Мы фактически строили конечный автомат. Существовало описание «игровой ситуации» и «действия», переводящего игру из ситуации А в ситуацию Б.
Когда человек играет в игру, система записывала игровые ситуации, и действия между ними. Получался направленный граф. А потом, во время действия ИИ, система пыталась найти наиболее подходящую ситуацию в данном контексте и применить наиболее подходящее действие.
У меня в профиле есть домашний сайт, посмотрите там статьи на эту тему.
Справедливости ради скажу, что FPS игры мы собирались изучать, но пока руки не дошли. В основном экспериментировали с боксом и футболом. И в любом случае это довольно трудоёмкая работа; я думаю, за таким подходом будущее (т.к. общий реализм в играх растёт, а реалистичность поведения ИИ не очень, поскольку его объективно трудно программировать руками, значит, придётся так или иначе применять обучающие алгоритмы).
Мы фактически строили конечный автомат. Существовало описание «игровой ситуации» и «действия», переводящего игру из ситуации А в ситуацию Б.
Когда человек играет в игру, система записывала игровые ситуации, и действия между ними. Получался направленный граф. А потом, во время действия ИИ, система пыталась найти наиболее подходящую ситуацию в данном контексте и применить наиболее подходящее действие.
У меня в профиле есть домашний сайт, посмотрите там статьи на эту тему.
Справедливости ради скажу, что FPS игры мы собирались изучать, но пока руки не дошли. В основном экспериментировали с боксом и футболом. И в любом случае это довольно трудоёмкая работа; я думаю, за таким подходом будущее (т.к. общий реализм в играх растёт, а реалистичность поведения ИИ не очень, поскольку его объективно трудно программировать руками, значит, придётся так или иначе применять обучающие алгоритмы).
Мне тоже кажется, что самое сложное это создать ИИ с которым всё время интересно играть. Главная сложность, по-моему, заключается в том, что все люди разные да и настроение бывает разное. Мне, например, обычно нравится играть с ИИ, который превосходит меня и побеждает в 90% случаев. Тогда победа ценнее. Некоторым наоборот нравится всегда побеждать и только изредка проигрывать. Поэтому ИИ должен иметь обратную связь (уметь определять насколько игрок доволен отдельной партией), чтобы играть, максимизируя «удовольствие» игрока. Что-то похожее на секс :)
Правда ещё очень важна эмоциональная связь, которой никогда не будет у ИИ. То есть, ты должен чувствовать по поведению противника: начинает нервничать, издевается над тобой, на грани срыва… Это конечно можно программировать, но осознание того что на том конце бездушная программа, превращает всё это в иммитацию эмоций. Это как секс с резиновой бабой.
Правда ещё очень важна эмоциональная связь, которой никогда не будет у ИИ. То есть, ты должен чувствовать по поведению противника: начинает нервничать, издевается над тобой, на грани срыва… Это конечно можно программировать, но осознание того что на том конце бездушная программа, превращает всё это в иммитацию эмоций. Это как секс с резиновой бабой.
Кстати, для крестиков-ноликов есть наглядная карта ходов — static.vizworld.com/wp-content/uploads/2010/12/tic_tac_toe.png
про counter-strike как-то интересно сразу стало. Что-то я не при помню вообще исследований/шоу-матчей 5*5 против ботов.
да и starcraft тоже интересно. крайне хочется посмотреть на битву корейца с ботом
UFO just landed and posted this here
Кореец выиграет. Вообще, при битве со старкрафтовыми ботами достаточно знать слабое место, тогда выиграет практически любой игрок, у которого есть достаточно опыта.
На тытрубке есть видео боёв ботов с ботами с конкурсов, некоторые довольно интересны. Например, есть зверский бот, который весь упор делает на муталисков. Муталиски в руках бота становятся очень суровым противником: они подлетают, атакуют, отлетают; сбегают и ищут новую дыру в защите, если противник подвёл юнитов; всегда держатся друг от друга на идеальном расстоянии, чтобы не попадать под аое; знают с точностью до пикселя безопасное расстояние до всех юнитов. И так — каждый муталиск по отдельности и все вместе взятые. По всей карте. Одновременно.
Конечно, если знаешь, что бот делает упор на муталисков, то сможешь отбиться. Но такой бой ужасно измотает.
На тытрубке есть видео боёв ботов с ботами с конкурсов, некоторые довольно интересны. Например, есть зверский бот, который весь упор делает на муталисков. Муталиски в руках бота становятся очень суровым противником: они подлетают, атакуют, отлетают; сбегают и ищут новую дыру в защите, если противник подвёл юнитов; всегда держатся друг от друга на идеальном расстоянии, чтобы не попадать под аое; знают с точностью до пикселя безопасное расстояние до всех юнитов. И так — каждый муталиск по отдельности и все вместе взятые. По всей карте. Одновременно.
Конечно, если знаешь, что бот делает упор на муталисков, то сможешь отбиться. Но такой бой ужасно измотает.
А не можете ссылок подкинуть? И вообще на сами соревнования. Раньше считал, что старкрафтовское ботовое апи закрыто.
Видео победителя 2010-го года в Starcraft AI Competition — битве ботов в SC:BW (подробнее о боте на странице The Berkeley Overmind Project).
Сайт соревнования Starcraft AI Competition (ссылки на прошлые соревнования и BWAPI — в меню слева).
В Starcraft 2 с помощью модов, которые полностью поддерживаются редактором уровней, можно вытворять совершенно безумные вещи (шутер делали, например). В том числе можно изменять AI. На слуху мод Green Tea AI. Можно гуглить.
(Насчёт муталисков, возможно, где-то приукрасил — давно интересовался, деталей не помню. :) )
Сайт соревнования Starcraft AI Competition (ссылки на прошлые соревнования и BWAPI — в меню слева).
В Starcraft 2 с помощью модов, которые полностью поддерживаются редактором уровней, можно вытворять совершенно безумные вещи (шутер делали, например). В том числе можно изменять AI. На слуху мод Green Tea AI. Можно гуглить.
(Насчёт муталисков, возможно, где-то приукрасил — давно интересовался, деталей не помню. :) )
Не знаю как там сейчас у корейцев и с StarCraft2, но во времена SC1 я видел как личности, сутками просиживающие в локальном battle.net, выигрывали у 3х ботов. Сам я матч 1:1 с компьютером так ни разу и не выиграл.
В SC2 есть достижения (самые сложные в Custom Game):
Insane FFA
Win a Free-For-All Multiplayer Custom Game against 7 Insane A.I. opponents.
Insane Blitz
Win a 1v1 Multiplayer Custom Game against an Insane A.I. opponent in under 5 minutes.
Outmatched: 2 Insane AI
Win a 1 vs 2 Multiplayer Custom Game with no Allies against 2 Insane A.I. opponents.
Outmatched: 4 Very Hard AI
Win a 1 vs 4 Multiplayer Custom Game with no Allies against 4 Very Hard A.I. opponents.
На тытрубке есть видео 1v4 Insane.
(Insane — самый сложный AI. У него юниты то ли стоят дешевле, то ли строятся быстрее, то ли и то, и другое. И он этим активно пользуется, применяя невозможные для обычного игрока стратегии.)
Как можно видеть по ачивам, от игрока ожидается превосходство даже с такими читами у компьютерного противника. Правда это стандартные AI, и в них Blizzard, если честно, не очень фантазию проявлял.
Insane FFA
Win a Free-For-All Multiplayer Custom Game against 7 Insane A.I. opponents.
Insane Blitz
Win a 1v1 Multiplayer Custom Game against an Insane A.I. opponent in under 5 minutes.
Outmatched: 2 Insane AI
Win a 1 vs 2 Multiplayer Custom Game with no Allies against 2 Insane A.I. opponents.
Outmatched: 4 Very Hard AI
Win a 1 vs 4 Multiplayer Custom Game with no Allies against 4 Very Hard A.I. opponents.
На тытрубке есть видео 1v4 Insane.
(Insane — самый сложный AI. У него юниты то ли стоят дешевле, то ли строятся быстрее, то ли и то, и другое. И он этим активно пользуется, применяя невозможные для обычного игрока стратегии.)
Как можно видеть по ачивам, от игрока ожидается превосходство даже с такими читами у компьютерного противника. Правда это стандартные AI, и в них Blizzard, если честно, не очень фантазию проявлял.
Спасибо, за статью, но она получалась слишком поверхностной, и в ней описываются в общем то хорошо освещенные вещи. Dimmerg опередил меня, но вставлю и свои 5 копеек :)
Что касается минимакса: Рассказали бы хотя бы про алгоритмыAlpha-Beta (ну ладно, тоже избит), Negascout, MTD(f). Потом известно, что в любом игровом дереве часто случаются коллизии и некоторые последовательности ходов можно повторно не просчитывать. Для этого обычно используется Zobrist-хеширование вместе с таблицами перестановок. Было бы интересно услышать и про параллельную реализацию алгоритмов поиска в дереве. Ведь эффективное использование всех потоков тоже не тривиально (алгоритмы PVS, DTS). Про использование хеширования вместе с этими алгоритмами (с критическими секциями и без).
Про шаблоны почти ничего не написано, однако было бы интересно узнать о техниках быстрого сопоставления или распознавания шаблонов. Например в GnuGo используется DFA. Ну и вообще как эти шаблоны использовать и составлять (можно вручную и автоматически).
Замечания по поводу методов Монте-Карло:
Хотелось бы более подробного описания алгоритма UCT, вместе с формулами.
И вы не совсем правильно написали:
«По этой статистике программа решает, что такой-то ход приведёт к выигрышу с вероятностью в 5%, такой-то — 3% и так далее. Далее программа просто выбирает ход с наибольшей вероятностью выигрыша и повторяет алгоритм. В итоге программа делает ход, который с наибольшей вероятностью ведёт к победе.»
А как же остальные ходы с меньшей вероятностью? Они на самом деле тоже рассматриваются и то, как часто они рассматриваются, зависит от коэффициента в алгортиме UCT, количества посещений данных узлов и количестве побед из данных узлов.
Впрочем, я и сам собираюсь писать потом статьи на данную тематику, т.к. русскоязычного материала практически нет.
Что касается минимакса: Рассказали бы хотя бы про алгоритмы
Про шаблоны почти ничего не написано, однако было бы интересно узнать о техниках быстрого сопоставления или распознавания шаблонов. Например в GnuGo используется DFA. Ну и вообще как эти шаблоны использовать и составлять (можно вручную и автоматически).
Замечания по поводу методов Монте-Карло:
Хотелось бы более подробного описания алгоритма UCT, вместе с формулами.
И вы не совсем правильно написали:
«По этой статистике программа решает, что такой-то ход приведёт к выигрышу с вероятностью в 5%, такой-то — 3% и так далее. Далее программа просто выбирает ход с наибольшей вероятностью выигрыша и повторяет алгоритм. В итоге программа делает ход, который с наибольшей вероятностью ведёт к победе.»
А как же остальные ходы с меньшей вероятностью? Они на самом деле тоже рассматриваются и то, как часто они рассматриваются, зависит от коэффициента в алгортиме UCT, количества посещений данных узлов и количестве побед из данных узлов.
Впрочем, я и сам собираюсь писать потом статьи на данную тематику, т.к. русскоязычного материала практически нет.
Огорчает то, что компьютер в играх все еще пытаются использовать для полного перебора.
Статья больше вводная получилась, но все равно интересно почитать. Про шашки например не знал.
В оценках кол-ва узлов в дереве для игры в крестики нолики у вас путаница некоторая. Там если не отсекать вообще будет 1!+2!+3!+...+9! узлов всего. Это чуть больше 400к, а не более полу миллиона. После отсечения будет сильно меньше чем четверть миллиона. Ну и там где вы указываете «7!=5040 ветвей», там все такие не ветвей а листьев.
В оценках кол-ва узлов в дереве для игры в крестики нолики у вас путаница некоторая. Там если не отсекать вообще будет 1!+2!+3!+...+9! узлов всего. Это чуть больше 400к, а не более полу миллиона. После отсечения будет сильно меньше чем четверть миллиона. Ну и там где вы указываете «7!=5040 ветвей», там все такие не ветвей а листьев.
Оу, 9! листьев в Крестики-Нолики? С учетом, что общее число расположений X и O на поле в 9 клеток(включая некорректные варианты) есть 2^9 или 512? У нас же состояния очень часто пересекаются, можно и кешировать.
а почему 2^9, а не 3^9? или вы только конечные состояния рассматриваете?
Ну так мы же о листьях говорим? А из листьев нет ребер. Из любого со стояния, где есть пустая клетка есть переход в новое. Поэтому у каждой клетки есть только два варианта.
Да, все верно, уникальных листьев 2^9. Только вот попасть в одно и тоже состояние можно по-разному, и соответственно кроме самого состояния для листа важен путь, которым он был достигнут.
Другое дело, что кеширование тут ни кто не отменял, и конечно же одинаковые варианты пересчитывать несколько раз незачем.
Другое дело, что кеширование тут ни кто не отменял, и конечно же одинаковые варианты пересчитывать несколько раз незачем.
Прочитал список и пошел искать, что такое Seven Minutes in Heaven, сложно в такую игру победить :))
Картинка взята с xkcd, а вся соль про Seven Minutes in Heaven — в подписи к этому комиксу.
«В бутылочку» компьютер вряд ли выиграет у человека, примерно так можно перевести Ж)
«о победе над сильнейшими игроками, как и в сёгах пока нет и речи»
а как же это?
www.membrana.ru/particle/3314
а как же это?
www.membrana.ru/particle/3314
Очень кстати, как раз пишу вариацию на тему крестиков-ноликов :)
>Программа перебирают случайным образом несколько миллионов игр, которые могут быть сыграны из текущего положения. Причём каждая игру проигрывается до конца,
Что-то вот здесь не очень ясно. Как можно просчитать партию до конца? Допустим на каждом ходу есть 30 вариантов хода. Допустим, партия длится 40 ходов. Общее числ вариантов — 30^40. Это понятно. Теперь, допустим что первый ход мы делаем не любой, а лишь из случайно отобранных 5 ходов. Значит число вариантов уже не 30^40 а 5*30^39 то есть примерно 30^39. Но это число не намного лучше исходного. Фактически случайный выбор первого хода ничего не дает. Полный перебор пяти партий по 30^39 вариантов в каждой по прежнему невозможен.
Значит имеется ввиду, что случано будут отбираться ходы не только на первом ходу, но и на всех ходах. Тогда мы получим значительное сокращение числа варинатов: 5^40. Это конечно тоже дофига, но все таки получше. Но тут возникает проблема. При таком подходе точность очень сильно зависит от выбора этих самых 5 ходов. Если их выбирать случайным образом то исходы будут совершенно отфонарные. Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Автор, можете прояснить этот момент?
Что-то вот здесь не очень ясно. Как можно просчитать партию до конца? Допустим на каждом ходу есть 30 вариантов хода. Допустим, партия длится 40 ходов. Общее числ вариантов — 30^40. Это понятно. Теперь, допустим что первый ход мы делаем не любой, а лишь из случайно отобранных 5 ходов. Значит число вариантов уже не 30^40 а 5*30^39 то есть примерно 30^39. Но это число не намного лучше исходного. Фактически случайный выбор первого хода ничего не дает. Полный перебор пяти партий по 30^39 вариантов в каждой по прежнему невозможен.
Значит имеется ввиду, что случано будут отбираться ходы не только на первом ходу, но и на всех ходах. Тогда мы получим значительное сокращение числа варинатов: 5^40. Это конечно тоже дофига, но все таки получше. Но тут возникает проблема. При таком подходе точность очень сильно зависит от выбора этих самых 5 ходов. Если их выбирать случайным образом то исходы будут совершенно отфонарные. Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Автор, можете прояснить этот момент?
Насколько я понимаю метод Монте-Карло, тут все немного не так. Вы сначала выбираете все возможные ходы, которые вы можете сейчас сделать. А затем для каждого такого хода проигрываете несколько партий до конца, со случайными ходами. Т.е. выбрав ход, дальше вы делаете еще один случайных ход, потом еще один и так далее, пока не завершите партию (ход не совсем случайный, он конечно подвергается некоторой эвристике). Здесь нету полного перебора, тут перебирается только одно возможное развитие события за раз. И так проверяется несколько сотен или тысяч вариантов. В итоге вы получаете, что сделав ход А, вы выигрываете 100 из 1000 партий, а сделав ход Б — 900 из 1000. По этому и выбирают наиболее оптимальный ход.
Лучше всего алгоритм UCT объясняет вот этот листинг да джаве. Обратите внимание, что только узел, в который зашли n раз в дальнейшем вносится в дерево ходов.
Также там есть параметр UCTK, который влияет на то, как глубоко будем считать. Чем больше у него значение, тем более тактический поиск у нас будет (на большую глубину от конкретных узлов). Чем меньше значения, тем более стратегический поиск будет (на меньшую глубину от всех узлов).
>> Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Да, такая проблема есть. И она усугубляется при увеличении размера доски. Поэтому данный метод используется вместе с другими техниками, а именно не совсем случайный выбор ходов на каждой итерации, а в соответствии с шаблоном, просчет не всей партии, а только локальных случаев (ну и другие, о которых я не знаю) А в точках данный метод вообще неприменим без модификаций.
Подробнее об этом вы можете почитать здесь и, возможно, здесь.
Также есть документ в виде презентации.
Также там есть параметр UCTK, который влияет на то, как глубоко будем считать. Чем больше у него значение, тем более тактический поиск у нас будет (на большую глубину от конкретных узлов). Чем меньше значения, тем более стратегический поиск будет (на меньшую глубину от всех узлов).
>> Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Да, такая проблема есть. И она усугубляется при увеличении размера доски. Поэтому данный метод используется вместе с другими техниками, а именно не совсем случайный выбор ходов на каждой итерации, а в соответствии с шаблоном, просчет не всей партии, а только локальных случаев (ну и другие, о которых я не знаю) А в точках данный метод вообще неприменим без модификаций.
Подробнее об этом вы можете почитать здесь и, возможно, здесь.
Также есть документ в виде презентации.
Sign up to leave a comment.
Об ИИ в интеллектуальных играх