tic tac toe minimax
1.0.0
Minimax AI 算法在 Tic-Tac-Toe（或圈与叉）游戏中的实现。尝试一下：井字游戏 - Minimax
为了使用人工智能解决游戏，我们将引入博弈树的概念，然后引入极小极大算法。游戏的不同状态由游戏树中的节点表示，与上面的规划问题非常相似。这个想法只是略有不同。在游戏树中，节点按与游戏中每个玩家的回合相对应的级别排列，因此树的“根”节点（通常在图的顶部描绘）是游戏中的开始位置。在井字游戏中，这将是尚未玩过 X 或 Os 的空网格。在根下的第二层，第一个玩家的移动可能会产生一些可能的状态，无论是 X 还是 O。我们将这些节点称为根节点的“子节点”。
第二层上的每个节点还将进一步将对方玩家的移动可以从其到达的状态作为其子节点。如此下去，一层一层地进行，直到达到游戏结束的状态。在井字棋中，这意味着要么其中一个玩家获得三并获胜，要么棋盘已满并且游戏以平局结束。
Minimax 是一种应用于两人游戏的人工智能，例如井字棋、西洋跳棋、国际象棋和围棋。这种游戏被称为零和游戏，因为在数学表示中：一个玩家获胜（+1），另一个玩家失败（-1）或任何一方都没有获胜（0）。
该算法递归地搜索导致Max玩家获胜或不输（平局）的最佳走法。它考虑游戏的当前状态以及该状态下的可用动作，然后对于它所玩的每个有效动作（交替min和max ），直到找到最终状态（获胜、平局或失败）。
Algorithms in a Nutshell（George Heineman；Gary Pollice；Stanley Selkow，2009）一书对该算法进行了研究。伪代码（改编）：
minimax(state, depth, player)
if (player = max) then
best = [null, -infinity]
else
best = [null, +infinity]
if (depth = 0 or gameover) then
score = evaluate this state for player
return [null, score]
for each valid move m for player in state s do
execute move m on s
[move, score] = minimax(s, depth - 1, -player)
undo move m on s
if (player = max) then
if score > best.score then best = [move, score]
else
if score < best.score then best = [move, score]
return best
end
现在我们将通过 Python 实现来了解该伪代码的每个部分。 Python 实现可在此存储库中找到。首先，考虑一下：
棋盘 = [ [0, 0, 0], [0, 0, 0], [0, 0, 0] ]
最大值=+1
最小值=-1
MAX 可以是 X 或 O，MIN 可以是 O 或 X，无论如何。棋盘尺寸为 3x3。
def minimax ( state , depth , player ): if player == MAX :
return [ - 1 , - 1 , - infinity ]
else :
return [ - 1 , - 1 , + infinity ]两位玩家都以你的最差成绩开始。如果玩家是 MAX，则其得分为 -无穷大。否则，如果玩家是 MIN，则其得分为+无穷大。注意：无穷大是 inf 的别名（来自 Python 中的数学模块）。
棋盘上的最佳棋步是 [-1, -1]（行和列）。
if depth == 0 or game_over ( state ):
score = evaluate ( state )
return score如果深度为零，则棋盘上没有新的空单元格可供玩。或者，如果玩家获胜，则游戏以 MAX 或 MIN 结束。因此将返回该状态的分数。
现在我们将看到包含递归的代码的主要部分。
for cell in empty_cells ( state ):
x , y = cell [ 0 ], cell [ 1 ]
state [ x ][ y ] = player
score = minimax ( state , depth - 1 , - player )
state [ x ][ y ] = 0
score [ 0 ], score [ 1 ] = x , y对于每个有效的移动（空单元格）：
棋盘上的移动（+1 或 -1）被撤销，行、列被收集。
下一步是将分数与最佳分数进行比较。
if player == MAX :
if score [ 2 ] > best [ 2 ]:
best = score
else :
if score [ 2 ] < best [ 2 ]:
best = score对于MAX玩家，将获得更大的分数。对于 MIN 玩家，将获得较低的分数。最后，返回最好的棋步。最终算法：
def minimax ( state , depth , player ):
if player == MAX :
best = [ - 1 , - 1 , - infinity ]
else :
best = [ - 1 , - 1 , + infinity ]
if depth == 0 or game_over ( state ):
score = evaluate ( state )
return [ - 1 , - 1 , score ]
for cell in empty_cells ( state ):
x , y = cell [ 0 ], cell [ 1 ]
state [ x ][ y ] = player
score = minimax ( state , depth - 1 , - player )
state [ x ][ y ] = 0
score [ 0 ], score [ 1 ] = x , y
if player == MAX :
if score [ 2 ] > best [ 2 ]:
best = score
else :
if score [ 2 ] < best [ 2 ]:
best = score
return best 下面，最佳移动位于中间，因为最大值位于左侧第二个节点。
看一下深度是否等于棋盘上的有效移动。完整的代码可以在py_version/中找到。
简化的博弈树：
该树有 11 个节点。完整的博弈树有 549.946 个节点！您可以测试它，在程序中放置一个静态全局变量，并为每轮的每个 minimax 函数调用递增它。
在更复杂的游戏中，例如国际象棋，很难搜索整个游戏树。然而，Alpha-beta剪枝是极小极大算法的一种优化方法，它允许我们忽略搜索树中的一些分支，因为他在搜索中剪掉了不相关的节点（子树）。有关更多信息，请参阅：
