Заставь компьютер никогда не проигрывать в крестики-нолики

Подход к такого рода проблемам заключается в изучении возможных вариантов будущего. Обычно (для шахматного или шашечного ИИ) вы бы рассматривали фьючерсы на определенное количество ходов вперед, но поскольку игры в крестики-нолики такие короткие, вы можете исследовать их до конца игры.

Концептуальная реализация

Таким образом, вы создаете разветвленную структуру:

• ИИ воображает, что делает все законные действия
• ИИ воображает, что пользователь делает каждый легальный ход, который он может сделать после каждого его легального хода.
• Затем ИИ представляет каждый из своих следующих легальных ходов.
• и т.п.

Затем, идя от самого разветвленного конца (самого дальнего вперед во времени), игрок, чей сейчас ход (ИИ или пользователь), выбирает, какое будущее для него лучше (победа, поражение или ничья) в каждой точке разветвления. Затем он передается игроку выше по дереву (ближе к настоящему); каждый раз выбирая наилучшее будущее для игрока, чей воображаемый ход сейчас, пока, наконец, вы не окажетесь в первой точке ветвления, где ИИ может видеть варианты будущего, в которых он проигрывает, рисует и выигрывает. Он выбирает будущее, в котором он выигрывает (или, если он недоступен, рисует).

Фактическая реализация

Обратите внимание, что концептуально это то, что происходит, но нет необходимости создавать все дерево, а затем судить об этом таким образом. Вы можете так же легко работать с деревом, добираясь до самых дальних точек во времени и выбирая их.

Здесь этот подход хорошо работает с рекурсивной функцией. Каждый уровень функции опрашивает все свои ветви; передавая им возможное будущее и возвращая -1,0,+1; выбор лучшего результата для текущего игрока в каждой точке. Верхний уровень выбирает ход, фактически не зная, как складывается каждое будущее, насколько хорошо они срабатывают.

Псевдокод

В этом псевдокоде я предполагаю, что +1 — выигрыш ИИ, 0 — рисование, -1 — проигрыш пользователя.

determineNextMove(currentStateOfBoard)
    currentBestMove= null
    currentBestScore= - veryLargeNumber

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI’sMove)
        if score>currentBestScore
            currentBestMove=legalMove
            currentBestScore=score
        end
    end

    make currentBestMove

end

getFutureScoreOfMove(stateOfBoard, playersTurn)

    if no LegalMoves
       return 1 if AI wins, 0 if draw, -1 if user wins
    end


    if playersTurn=AI’sTurn
        currentBestScore= - veryLargeNumber //this is the worst case for AI
    else
        currentBestScore= + veryLargeNumber //this is the worst case for Player
    end

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn)
        if playersTurn ==AI’sTurn AND score>currentBestScore //AI wants positive score
           currentBestScore=score
        end
        if playersTurn ==Users’sTurn AND score<currentBestScore //user wants negative score
           currentBestScore=score
        end

     end

     return currentBestScore
end

Этот псевдокод не заботится о начальной доске (вы вызываете эту функцию при каждом движении ИИ на текущей доске) и не возвращает путь, по которому пойдет будущее (мы не можем знать, будет ли пользователь играть оптимально, поэтому это информация бесполезна), но он всегда будет выбирать путь, ведущий к оптимальному будущему для ИИ.

Рекомендации по более крупным проблемам

В этом случае, когда вы исследуете игру до конца, очевидно, какое будущее будет наилучшим (победа, поражение или ничья), но если вы собираетесь (например) только на пять ходов в будущее, вы бы нужно найти какой-то способ определить это; в шахматах или шашках оценка фигуры - самый простой способ сделать это, а положение фигуры является полезным улучшением.

Я занимался такой штукой лет 5 назад. Я провел исследование. В tic tac toe это не займет много времени, нужно просто подготовить паттерны для первых двух-трех ходов.

Вам нужно проверить, как играть:

1. Компьютер запускается первым.
2. Игрок начинает первым.

Есть 9 различных стартовых позиций:

Но на самом деле только 3 из них разные (остальные повернуты). Итак, после этого вы увидите, что нужно делать после некоторых конкретных ходов, я думаю, вам не нужны никакие алгоритмы в этом случае, потому что tic tac toe окончание определяется первыми ходами. Так что в этом случае вам понадобятся несколько операторов if-else или switch и генератор random.

tic tac toe относятся к группе игр, которые не пропадут, если уметь играть, поэтому для таких игр не нужно использовать деревья и модифицированные алгоритмы сортировки. Для написания такого алгоритма вам понадобится всего несколько функций:

1. CanIWin() чтобы проверить, есть ли у компьютера 2 подряд и можно ли выиграть.
2. ShouldIBlock() чтобы проверить, нет ли у игрока 2-х подряд и нужно ли его заблокировать.

Эти две функции должны вызываться в таком порядке, если она возвращает true, вам нужно либо выиграть, либо не позволить игроку выиграть.

После этого вам нужно сделать другие расчеты для перемещения.

Одна исключительная ситуация - это когда компьютер запускает игру. Вам нужно выбрать клетку, которая принадлежит наибольшему количеству различных направлений (их 8 - 3 по горизонтали, вертикали и 2 по диагонали). В таком алгоритме компьютер всегда будет выбирать центр, потому что он имеет 4 направления, вам следует добавить небольшую возможность выбора второго лучшего варианта, чтобы сделать игру немного более привлекательной.

Поэтому, когда вы достигаете ситуации, когда некоторые выбранные части доски и компьютер должны двигаться, вам нужно оценить каждую свободную ячейку. (Если первая или вторая функция вернули true, вы должны выполнить действие, прежде чем доберетесь до этого места!!!). Таким образом, чтобы оценить ячейку, вам нужно подсчитать, сколько открытых направлений осталось в каждой ячейке, а также вам нужно заблокировать хотя бы одно направление противника.

После этого у вас будет несколько возможных ячеек, чтобы поставить свою отметку. Поэтому вам нужно проверить необходимую последовательность ходов, потому что у вас будет несколько вариантов, и может случиться так, что один из них приведет вас к проигрышу. Итак, после этого у вас будет набор, и вы можете выбрать ход случайным образом или выбрать тот, у которого больше всего очков.

Я должен сказать нечто подобное, как сказано в начале поста. В более крупных играх нет идеальной стратегии, и, скажем, шахматы во многом основаны на шаблонах, но также и на дальновидной стратегии (для такой вещи используется Патриция Трие). Подводя итог, вам не нужны сложные алгоритмы, достаточно нескольких функций для подсчета того, сколько вы выигрываете, а оппонент теряет при ходе.

Сделайте вспомогательную программу для предсказания случаев, в которых пользователь может выиграть. Затем вы можете сказать своему ИИ, чтобы он делал то, что пользователь должен делать для победы.