Найти возможные шаги для минимаксного алгоритма Tic Tac Toe

Question

Я решил создать игру Tic Tac Toe с платой 11x11, условие выигрыша - 5 соток X или O в строке (по вертикали, по горизонтали или по диагонали) или когда доска заполнена , т. е. невозможно двигаться влево.

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

function alphabeta(node, depth, α, β, maximizingPlayer) 
    if the game ends: 
     return the heuristic value of the current state 
    if maximizingPlayer 
     v := -∞ 
     for each possible move in board // notice this 
      v := max(v, alphabeta(child, depth – 1, α, β, FALSE)) 
      α := max(α, v) 
      if β ≤ α 
       break (* β cut-off *) 
     return v 
    else 
    .... 

Первоначально размер Tic-Tac-Toe борту только 3х3, что означает, что нет много пустой ячейки цикличным минимакса. Но с платой 11x11 есть 121 ячеек!

Например, если первый поворот X, то O имеет 120 возможных ходов. O попробует каждый ход, чтобы найти лучшее значение для воспроизведения, и поэтому время работы функции факториально равно 120.

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

Answer 1

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