我正在尝试为井字游戏构建一个永远不会丢失的最小-最大算法......
我尝试通过阅读几个来源来构建它：
- http://neverstopbuilding.com/minimax
- http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/(我构建了一些与此非常相似的东西)。
这是代码： 类树：
def find_best_move(self,board,depth,myTurn,sign):
"""
:param board:
:return:
"""
if (board.empty==[]): return None
best_move=-(2**(board.s**2))
m=board.empty[0]
for move in board.empty:
b=copy.deepcopy(board)
b.ins(move,sign)
if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
return move
curr_move=self.minimax(b,depth,myTurn,sign)
if (curr_move > best_move):
best_move = curr_move
m=move
print(curr_move,best_move,m)
return m #This should be the right move to do....
# *****************************************************************************************************#
def minimax(self,board,depth,myTurn,sign):
"""
:param depth:
:param myTurn:
:return:
"""
#print(depth,end='n')
if (self.is_win(board,sign)):
#print("I win!")
return (board.s**2+1) - depth
elif (self.is_win(board,xo.opp_sign(sign))):
#print("You win!")
return -(board.s**2+1) + depth
elif (board.is_full()):
return 0
if (myTurn):
bestVal=-(2**700)
for move in board.empty: #empty - the empty squares at the board
b = copy.deepcopy(board)
b.ins(move, sign)
value=self.minimax(b,depth+1,not myTurn, xo.opp_sign(sign))
#xo.opp_sign(sign) - if function for the opposite sign: x=>o and o=>x
bestVal = max([bestVal,value])
return bestVal
else:
bestVal = (2**700)
for move in board.empty:
b = copy.deepcopy(board)
b.ins(move, xo.opp_sign(sign))
value = self.minimax(b, depth + 1, not myTurn, xo.opp_sign(sign))
#print("opp val: ",value)
bestVal = min([bestVal, value])
return bestVal
# *****************************************************************************************************#
def is_win(self,board, sign):
"""
The function gets a board and a sign.
:param board: The board.
:param sign: The sign (There are only two options: x/o).
:return: True if sign "wins" the board, i.e. some row or col or diag are all with then sing. Else return False.
"""
temp=board.s
wins = [] # The options to win at the game.
for i in range(1, temp + 1):
wins.append(board.get_col(i))
wins.append(board.get_row(i))
wins.append(board.get_diag1())
wins.append(board.get_diag2())
for i in wins:
if (self.is_same(i, sign)):
return True
return False
# *****************************************************************************************************#
def is_same(self, l, sign):
"""
The function get a list l and returns if ALL the list have the same sign.
:param l: The list.
:param sign: The sign.
:return: True or false
"""
for i in l:
if (i != sign):
return False
return True
如果我的代码有问题，请告诉我！
但是，我总是可以击败它 - 我只需要做一个"叉子">
.e.g.(我是x，算法是o)
xx-
xo-
-o-
我赢了...
有算法可以制作可以阻止分叉的树吗？
您有三个错误。
1.在您的最小最大值方法中，符号交换一次太多
你交换else块中的符号 - 对于myTurnFalse的情况 - 但你不应该。您已经将符号与每个递归调用交换。由于这个错误，在最小最大值搜索期间，你总是在板上放置相同的标志，而不是相反的标志。显然，您因此错过了对手的所有威胁。
所以改变：
else:
bestVal = (2**700)
for move in board.empty:
b = copy.deepcopy(board)
b.ins(move, error xo.opp_sign(sign)) # <-- bug
自：
else:
bestVal = (2**700)
for move in board.empty:
b = copy.deepcopy(board)
b.ins(move, sign) # <-- corrected
2.在find_best_move你应该交换移动，因为你称之为最小最大值
类似的错误也发生在find_best_move。当你完成每一个动作时，你必须在新棋盘中调用最小最大值时交换符号，否则你让同一个玩家玩两次。
所以改变这个：
for move in board.empty:
b=copy.deepcopy(board)
b.ins(move,sign)
if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
return move
curr_move=self.minimax(b,depth,myTurn,sign) # <-- bug
自：
for move in board.empty:
b=copy.deepcopy(board)
b.ins(move,sign)
if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
return move
curr_move=self.minimax(b,depth,not myTurn,xo.opp_sign(sign)) # <-- corrected
请注意，第二个条件不是必需的：如果你是刚刚移动的人，那么另一个应该处于获胜位置是不合逻辑的。
3. 在最小最大值中，当有胜利时，你不考虑myTurn的价值
尽管您考虑myTurn的值来确定是最小化还是最大化，但在检查获胜时不会执行此操作。
您目前有这个：
if (self.is_win(board,sign)):
#print("I win!")
return (board.s**2+1) - depth
elif (self.is_win(board,xo.opp_sign(sign))):
#print("You win!")
return -(board.s**2+1) + depth
elif (board.is_full()):
return 0
首先，第一个if条件不应该永远为真，因为最近的举动是针对相反的标志，所以这永远不会导致标志的胜利。
但问题是：第二个if不会通过myTurn来确定返回值应该是负值还是正值。它应该这样做以保持一致。因此，将上面的代码更改为：
if self.is_win(board,xo.opp_sign(sign)):
if myTurn:
return -(board.s**2+1) + depth
else:
return (board.s**2+1) - depth
elif board.is_full():
return 0
如何拨打find_best_move
最后，如果您始终使用myTurn参数调用 find_best_move 作为True，则上述方法有效，因为从if (curr_move > best_move)可以看出find_best_move最大化结果。因此，为了避免您用False调用它，您最好删除此参数并将False传递给minimax。所以：
def find_best_move(self,board,depth,sign): # <-- myTurn removed as argument
# ... etc ...
curr_move=self.minimax(b,depth,False,xo.opp_sign(sign)) # pass False
这样，参数myTurn指示回合是否与调用find_best_move的玩家相同。
工作解决方案
通过添加最少的代码来使其工作(添加了Board和XO类)，可以看到该程序在 repl.it 上运行。
请注意，此算法不是最佳的。这只是蛮力。您可以考虑存储以前评估的位置的结果，进行 alpha-beta 修剪等......