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

Question

В реализации «крестики-нолики» я предполагаю, что сложной задачей является определение наилучшего хода, выполняемого машиной.

Какие алгоритмы можно использовать? Я смотрю на реализации от простого к сложному. Как бы я занялся решением этой части проблемы?

Answer 1

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

Цитата из Википедия (Tic Tac Toe # Стратегия)

Игрок может сыграть в идеальную игру в крестики-нолики (чтобы выиграть или, по крайней мере, сыграть в ничью), если он выберет первый доступный ход из следующего списка, каждый ход, как это используется в тикете Ньюэлла и Саймона 1972 года. программа Tac-Toe. [6]

1. Победа: если у вас есть два подряд, сыграйте третьего, чтобы получить три подряд.

2. Блок: Если у противника есть два подряд, сыграйте третьего, чтобы заблокировать их.

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

4. Блок противника Вилка:

   Вариант 1. Создайте две строки подряд противник в обороне, как долго поскольку это не приводит к их созданию вилка или победа. Например, если "X" имеет угол, «О» имеет центр, и «Х» имеет противоположный угол, «О» не должен играть угол, чтобы выиграть. (Играя угол в этом Сценарий создает форк для "X" победа.)

   Вариант 2: если есть конфигурация где противник может раскошелиться, заблокировать эта вилка.

5. Центр: играть в центр.

6. Противоположный угол: если противник в углу, играйте противоположным угол.

7. Пустой угол: играть в пустой угол.

8. Пустая сторона: играть пустую сторону.

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

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

Answer 2

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

Короче говоря, вы хотите не искать движение, которое имеет для вас наилучший возможный результат, а скорее движение, где наихудший из возможных результатов максимально хорош. Если вы полагаете, что ваш оппонент играет оптимально, вы должны предположить, что он сделает худший для вас ход, и, следовательно, вы должны предпринять ход, который минимизирует его максимальный выигрыш.

Answer 3

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

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

-Adam

Answer 4

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

Доска: вектор из девяти элементов, представляющий доску. Мы храним 2 (с указанием Пусто), 3 (указывает на X) или 5 (указывает на O). Поворот: целое число, указывающее, какой ход игры собирается сыграть. 1-й ход будет обозначен 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.

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

нам понадобится структура данных, представляющая плату. Представим доску с двумерным массивом. Внешний массив представляет всю доску, а внутренний массив представляет строку. Вот состояние пустой доски.

_gameBoard: [
    [“”, “”, “”],
    [“”, “”, “”],
    [“”, “”, “”]
]

Мы будем заполнять доску символами 'x' и 'o'.

Далее нам понадобится функция, которая может проверить результат. Функция проверит последовательность символов. Каково бы ни было состояние доски, результатом является один из 4 вариантов: либо незавершенный, либо игрок Х выиграл, игрок О выиграл или ничья. Функция должна возвращать состояние платы.

const SYMBOLS = {
  x:'X',
  o:'O'
}
const RESULT = {
  incomplete: 0,
  playerXWon: SYMBOLS.x,
  playerOWon: SYMBOLS.o,
  tie: 3
}
  function getResult(board){
      // returns an object with the result

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

      function succession (line){
        return (line === symbol.repeat(3))
      }

      let line

      //first we check row, then column, then diagonal
      for (var i = 0 ; i<3 ; i++){
        line = board[i].join('')
        if(succession(line)){
          result = symbol;
          return {result};
        }
      }

      for (var j=0 ; j<3; j++){
        let column = [board[0][j],board[1][j],board[2][j]]
        line = column.join('')
        if(succession(line)){
          result = symbol
          return {result};
        }
      }

      let diag1 = [board[0][0],board[1][1],board[2][2]]
      line = diag1.join('')
      if(succession(line)){
        result = symbol
        return {result};
      }

      let diag2 = [board[0][2],board[1][1],board[2][0]]
      line = diag2.join('')
      if(succession(line)){
        result = symbol
        return {result};
      }

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

      return {result}
    }

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

  function getBestMove (board, symbol){

    function copyBoard(board) {
      let copy = []
       for (let row = 0 ; row<3 ; row++){
        copy.push([])
        for (let column = 0 ; column<3 ; column++){
          copy[row][column] = board[row][column]
        }
      }
      return copy
    }

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

    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)
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

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

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

Answer 9

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

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

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

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

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

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

Мне очень весело на вечеринках, я знаю.

Answer 10

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