Какой алгоритм игры в крестики-нолики я могу использовать, чтобы определить «лучший ход» для ИИ?

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

Метод грубой силы, генерирующий каждую возможную доску и оценивающий ее на основе досок, которые он позже создает дальше по дереву, не требует много памяти, особенно если вы понимаете, что повороты платы на 90 градусов избыточны, как и перевороты по вертикали, горизонтальная и диагональная ось.

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

-Адам

Поскольку вы имеете дело только с матрицей возможных местоположений 3x3, было бы довольно легко просто написать поиск по всем возможностям, не обременяя вашу вычислительную мощность. Для каждого открытого пространства вычислите все возможные результаты после того, как отметьте это пространство (я бы сказал, рекурсивно), а затем используйте ход с наибольшими шансами на победу.

На самом деле, оптимизация была бы пустой тратой усилий. Хотя некоторые из простых могут быть:

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

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

Стратегия из Википедии для идеальной игры (каждый раз выигрыш или ничья) кажется простым псевдокодом:

Quote from Wikipedia (Tic Tac Toe#Strategy)

A player can play a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon's 1972 tic-tac-toe program.[6]

1. Win: If you have two in a row, play the third to get three in a row.

2. Block: If the opponent has two in a row, play the third to block them.

3. Fork: Create an opportunity where you can win in two ways.

4. Block Opponent's Fork:

   Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)

   Option 2: If there is a configuration where the opponent can fork, block that fork.

5. Center: Play the center.

6. Opposite Corner: If the opponent is in the corner, play the opposite corner.

7. Empty Corner: Play an empty corner.

8. Empty Side: Play an empty side.

Распознавание того, как выглядит ситуация «вилки», может быть выполнено методом грубой силы, как предлагается.

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

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

Вкратце, вы хотите не искать ход, который имеет для вас наилучший из возможных исходов, а скорее искать ход, при котором наихудший из возможных исходов максимально хорош. Если вы предполагаете, что ваш оппонент играет оптимально, вы должны предположить, что он сделает худший для вас ход, и поэтому вы должны сделать ход, который минимизирует их МАКСИМАЛЬНЫЙ выигрыш.

Попытка без использования игрового поля.

1. чтобы выиграть (ваш дубль)
2. в противном случае не проиграть (дубль соперника)
3. если нет, у вас уже есть вилка (есть дабл дабл)
4. если нет, то если у соперника есть вилка
   
   1. поиск в блокирующих точках возможного дабла и форка (окончательный выигрыш)
   2. если не искать вилки в блокировочных точках (что дает противнику наиболее проигрышные возможности)
   3. если бы не только блокирующие баллы (чтобы не потерять)
5. если не искать дабл и форк (окончательная победа)
6. если не искать только вилки, которые дают противнику самые проигрышные возможности
7. если не искать только двойного
8. если не тупик, то галстук, рандом.
9. если нет (это означает ваш первый ход)
   
   1. если это первый ход игры;
      
      1. дать противнику наибольшую вероятность проигрыша (алгоритм дает только угловые, что дает противнику 7 проигрышных очков)
      2. или для того, чтобы разбить скуку просто случайным образом.
   2. если это второй ход игры;
      
      1. найти только не теряющие очки (дает еще немного вариантов)
      2. или найдите в этом списке те точки, которые имеют наибольшие шансы на победу (это может быть скучно, потому что результатом будут только все углы или смежные углы или центр)

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

Типичный алгоритм игры в крестики-нолики должен выглядеть так:

Доска: вектор из девяти элементов, представляющий доску. Мы храним 2 (с указанием Пробел), 3 (обозначает X) или 5 (обозначает O). Ход: целое число, указывающее, какой ход игры будет сделан. Первый ход будет обозначен цифрой 1, последний - 9.

Алгоритм

Основной алгоритм использует три функции.

Make2: возвращает 5, если центральный квадрат платы пуст, т.е. если board[5]=2. В противном случае эта функция возвращает любой неугловой квадрат (2, 4, 6 or 8).

Posswin(p): возвращает 0, если игрок p не может выиграть следующим ходом; в противном случае он возвращает номер клетки, составляющей выигрышный ход. Эта функция позволит программе как побеждать, так и блокировать победу оппонентов. Эта функция работает, проверяя каждую из строк, столбцов и диагоналей. Умножая значения каждого квадрата на всю строку (столбец или диагональ), можно проверить возможность выигрыша. Если продукт 18 (3 x 3 x 2), то X может выиграть. Если продукт 50 (5 x 5 x 2), то O может выиграть. Если выигрышная строка (столбец или диагональ) найдена, можно определить пустой квадрат в ней, и эта функция вернет номер этого квадрата.

Go (n): делает ход в квадрате n. эта процедура устанавливает для платы [n] значение 3, если Терн нечетный, или 5, если Терн четный. Он также увеличивает ход на единицу.

Алгоритм имеет встроенную стратегию для каждого хода. Это делает нечетные номера ход, если он играет X, четный ход, если он играет O.

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

Я использовал это. Дайте мне знать, что вы чувствуете.

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

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

Если P2 делает правильно блокирует в центре, P1 должен играть в противоположном углу, потому что опять же, по какой-то психологической причине, P2 предпочтет симметрию игры в углу, что снова приведет к проигрышной доске для них.

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

Эмпирически (точнее, анекдотически) лучшими стартовыми ходами P1 кажутся первый угол, второй центр и последнее ребро.

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

Я знаю, что мне очень весело на вечеринках.

Адаптация крестиков-ноликов к алгоритму min max

let gameBoard: [
    [null, null, null],
    [null, null, null],
    [null, null, null]
]

const SYMBOLS = {
    X:'X',
    O:'O'
}

const RESULT = {
    INCOMPLETE: "incomplete",
    PLAYER_X_WON: SYMBOLS.x,
    PLAYER_O_WON: SYMBOLS.o,
    tie: "tie"
}

Нам понадобится функция, которая может проверять результат. Функция проверит последовательность символов. Каким бы ни было состояние доски, результатом может быть один из 4 вариантов: либо «Неполно», игрок X выиграл, игрок O выиграл или ничья.

function checkSuccession (line){
    if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
    if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
    return false 
}

function getResult(board){

    let result = RESULT.incomplete
    if (moveCount(board)<5){
        return result
    }

    let lines

    //first we check row, then column, then diagonal
    for (var i = 0 ; i<3 ; i++){
        lines.push(board[i].join(''))
    }

    for (var j=0 ; j<3; j++){
        const column = [board[0][j],board[1][j],board[2][j]]
        lines.push(column.join(''))
    }

    const diag1 = [board[0][0],board[1][1],board[2][2]]
    lines.push(diag1.join(''))
    const diag2 = [board[0][2],board[1][1],board[2][0]]
    lines.push(diag2.join(''))
    
    for (i=0 ; i<lines.length ; i++){
        const succession = checkSuccesion(lines[i])
        if (succession){
            return succession
        }
    }

    //Check for tie
    if (moveCount(board)==9){
        return RESULT.tie
    }

    return result
}

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

const copyBoard = (board) => board.map( 
    row => row.map( square => square  ) 
)

function getAvailableMoves (board) {
  let availableMoves = []
  for (let row = 0 ; row<3 ; row++){
    for (let column = 0 ; column<3 ; column++){
      if (board[row][column]===null){
        availableMoves.push({row, column})
      }
    }
  }
  return availableMoves
}

function applyMove(board,move, symbol) {
  board[move.row][move.column]= symbol
  return board
}
 
function getBestMove (board, symbol){

    let availableMoves = getAvailableMoves(board)

    let availableMovesAndScores = []

    for (var i=0 ; i<availableMoves.length ; i++){
      let move = availableMoves[i]
      let newBoard = copyBoard(board)
      newBoard = applyMove(newBoard,move, symbol)
      result = getResult(newBoard,symbol).result
      let score
      if (result == RESULT.tie) {score = 0}
      else if (result == symbol) {
        score = 1
      }
      else {
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
        nextMove = getBestMove(newBoard, otherSymbol)
        score = - (nextMove.score)
      }
      if (score === 1)  // Performance optimization
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

    availableMovesAndScores.sort((moveA, moveB )=>{
        return moveB.score - moveA.score
      })
    return availableMovesAndScores[0]
  }

Алгоритм в действии, Github, Объясняя процесс более подробно