永不输的Minmax井字棋算法
Minmax tic-tac-toe algorithm that never loses
我正在尝试为 Tic-Tac-Toe 构建一个永不输的最小-最大算法...
我尝试通过阅读一些来源来构建它：
- http://neverstopbuilding.com/minimax
- http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/（我构建了与这个非常相似的东西）。
代码如下：
class 树：
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
如果我的代码有问题请告诉我！
但是，我总能打败这个 - 我只需要做一个 "fork"
.e.g.: (我是x，算法是o)
xx-
xo-
-o-
我赢了...
有算法可以制作出可以挡住叉子的树吗？
你有三个错误。
1。在你的 minimax 方法中，符号被交换了一次太多
您在 else 块中交换符号——对于 myTurn 为 False 的情况——但您不应该这样做。您已经在每次递归调用中交换了符号。由于这个错误，在极小极大搜索过程中，您总是在棋盘上放置相同的符号，而不是相反的符号。显然你因此错过了对手的所有威胁。
所以改变：
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 中，您应该在调用 minimax
时交换移动
并且在find_best_move中也出现了类似的错误。当你走每一步时，你必须在新棋盘中调用 minimax 时交换符号，否则你让同一个玩家玩两次。
所以改变这个：
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。在 minimax 你不考虑 myTurn 的值时有 win
虽然您考虑 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 条件不应该永远为真，因为最近的移动是针对相反的符号，所以这永远不会导致 sign[ 获胜=88=].
但问题是：第二个 if 不查看 myTurn 来确定 return 值应该是负值还是正值。它应该这样做以保持一致。所以把上面的代码改成这样：
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，则上述方法有效，因为 find_best_move 最大化了结果，从 if (curr_move > 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 p运行ing 等...
我正在尝试为 Tic-Tac-Toe 构建一个永不输的最小-最大算法...
我尝试通过阅读一些来源来构建它：
- http://neverstopbuilding.com/minimax
- http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/（我构建了与这个非常相似的东西）。
代码如下： class 树：
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
如果我的代码有问题请告诉我！
但是，我总能打败这个 - 我只需要做一个 "fork"
.e.g.: (我是x，算法是o)
xx-
xo-
-o-
我赢了...
有算法可以制作出可以挡住叉子的树吗？
你有三个错误。
1。在你的 minimax 方法中，符号被交换了一次太多
您在 else 块中交换符号——对于 myTurn 为 False 的情况——但您不应该这样做。您已经在每次递归调用中交换了符号。由于这个错误，在极小极大搜索过程中，您总是在棋盘上放置相同的符号，而不是相反的符号。显然你因此错过了对手的所有威胁。
所以改变：
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 中，您应该在调用 minimax
时交换移动并且在find_best_move中也出现了类似的错误。当你走每一步时，你必须在新棋盘中调用 minimax 时交换符号，否则你让同一个玩家玩两次。
所以改变这个：
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。在 minimax 你不考虑 myTurn 的值时有 win
虽然您考虑 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 条件不应该永远为真，因为最近的移动是针对相反的符号，所以这永远不会导致 sign[ 获胜=88=].
但问题是：第二个 if 不查看 myTurn 来确定 return 值应该是负值还是正值。它应该这样做以保持一致。所以把上面的代码改成这样：
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，则上述方法有效，因为 find_best_move 最大化了结果，从 if (curr_move > 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 p运行ing 等...