Гипер Шары теперь умеют играть не только в Линии, но и в Шахматы. Всё началось с идеи - а могут ли шары своими физиономиями подсказывать как они ходят? Оказалось, что очень даже могут. Их мнемоничность позволяет быстро освоить правила игры, даже совсем новичкам в шахматах.
Но есть одно но - в шахматах есть несколько весьма специфичных правил, к которым приделали костыли, нюансы которых даже гроссмейстеры не всегда понимают полностью: первый прыжок пешки на 2 клетки и рокировка нетронутого короля с ладьей. Фактически, эти правила позволяют в специфических случаях чуть ускорить игру, сделав несколько (полу)ходов за один, а в качестве костыля - возможность противнику вмешаться в эти полуходы задним числом.
А самая жесть заключается в том, что правила ходов зависят из-за этих костылей не только от текущего состояния поля, но и от истории прошлых ходов. Не надо так. Выпиливаем это легаси. Оно всё равно на суть игры влияет не сильно.
Ну и по мелочи: пешке нет смысла превращаться во что-то отличное от ферзя, а шахи и маты не имеют смысла - для конца игры достаточно завалить короля противника. Не заметил вовремя угрозы - проиграл.
Можно было бы взять готовую мега оптимизированную реализацию шахматной логики типа stockfish, но оно весит как самолёт. Я же хотел с шариками поиграть, а не на индикатор загрузки любоваться. Не надо так. Закатываем рукава.
Вводим функцию оценки состояния доски: каждая фигура имеет свою ценность, белые складываем, чёрные вычитаем, получаем баланс по фигурам. При равном балансе, выгоднее та позиция, где ты можешь сделать больше ходов, а противник - меньше.
Если перебирать вглубь, то мы всё время убьём на анализ сценария, который никогда не случится, а то и вообще уйдём в бесконечный цикл. Если перебирать вширь, то очень быстро вся память улетит в трубу. Нужен компромисс, который бы позволил получить первичную оценку возможных ходов, а потом итеративно улучшать её, погружаясь всё глубже, но не выедая всю память мироздания.
Пусть все состояния доски у нас образуют дерево. Введём функцию "подумать", которая рекурсивно идёт от текущего состояния по этому дереву, выбирая на каждом шаге лучший ход. Дойдя до листа дерева, она перебирает все возможные ходы на +1 уровень. После этого оценки состояний поднимаются до корня по принципу минимакс: один игрок максимизирует оценку, а другой минимизирует. Следующий вызов "думания" может пойти уже по другой ветке дерева, а значит старую ветку можно удалить из памяти, оставив лишь её оценку. И пока игрок думает над своим ходом, бот тоже "думает" гоняя анализ в фоновом цикле.
В результате получаем, что в памяти держится лишь текущий самый оптимальный для всех игроков сценарий и оценки его ответвлений. Этот сценарий постоянно мутирует, выбирая для каждого игрока всё более оптимальные ходы. И всё это счастье весом суммарно всего 6кб со всеми зависимостями.
А играть с ним - одно удовольствие. Он очень быстро просекает всякие многоходовочки, не совершая глупых ходов. Но при этом, чем быстрее играет пользователь, тем меньше у бота времени для глубокого анализа, а значит больше шансов его перехитрить. Но это довольно сложно. У меня пока не получилось.
Есть ли у нас тут мастера шах-фу, которые покажут этому примитивному автоботу, кто тут настоящий интеллект?
