python - 井字游戏的极小极大算法通过用相同的符号填充每个空 space 来更新棋盘
python - minimax algorithm for tic tac toe updating the board by filling every empty space with the same symbol
我一直在尝试通过编写小游戏（例如井字游戏）来提高对 python 的理解。我从头开始创建了游戏副本，但随后开始寻找为游戏创建合理 AI 的方法。我决定使用 minimax 来实现这个目标。我找到了该算法的教程并尝试为游戏塑造它。
然而，当代码为 运行 时，在 ai 的第一个回合。棋盘上剩下的每个空 space 都用相同的符号填充，迫使获胜，使游戏无法玩。
由于我对算法不熟悉且缺乏经验，所以我从 youtube 教程中获取代码并对其进行编辑，使其适用于游戏。
这是代码
import random
import time
import sys
from sys import maxsize
#converts numbers from the board to X O and "" for printing out the board
def numToSymbol(board):
visual = board
for i in range(0, 9):
if visual[i] == -1:
visual[i]= "X"
elif visual[i] == 1:
visual[i] = "O"
elif visual[i] == 0:
visual[i] = " "
return visual
def symbolToNum(visual):
board = visual
for i in range(0, 9):
if board[i] == "X":
board[i] = -1
elif board[i] == "O":
board[i] = 1
elif board[i] == " ":
board[i] = 0
return board
# prints the board, first coverting numbers throught numtoSymbol
def drawBoard():
visual = numToSymbol(board)
print(
"|"+ str(visual[0]) + "|" + str(visual[1]) + "|" + str(visual[2]) + "| \n"
"-------\n"
"|"+ str(visual[3]) + "|" + str(visual[4]) + "|" + str(visual[5]) + "| \n"
"-------\n"
"|"+ str(visual[6]) + "|" + str(visual[7]) + "|" + str(visual[8]) + "| \n"
"-------")
symbolToNum(visual)
# checks the possible options for 3 in a row and if any are all held by one side returns true
def checkWin(board, winConditions, ai):
if ai == True:
win = 3
if ai == False:
win = -3
for row in winConditions:
checkA = board[row[0]]
checkB = board[row[1]]
checkC = board[row[2]]
if checkA + checkB + checkC == int(win):
return True
return False
def checkDraw(board):
emptyTile = 9
for tile in board:
if tile != 0:
emptyTile -= 1
if emptyTile == 0:
completion(2)
def availableMoves(board, bonus):
availableSlots = []
for position in range(0,9):
if board[position] == 0:
availableSlots.append(position + bonus)
return availableSlots
def playerTurn(board, remainingTurns):
board = board
checkDraw(board)
visual =drawBoard()
print("pick one of the available slots \n")
availableSlots = availableMoves(board, 1)
print(availableSlots)
choice = int(input('Select a tile from those shown above:\n')) -1
while True:
if 0 <= choice <= 8:
if board[choice] == 0:
board[choice] = -1
break
else:
choice = int(input('Select a tile from those shown above which has not already been selected:\n')) -1
else:
choice = int(input('Select a tile from those shown above:\n')) -1
visual = drawBoard()
if checkWin(board, winConditions, False) == True:
completion(0)
else:
aiTurn(board, remainingTurns - 1)
class Node(object):
def __init__(self, remainingTurns, playerNum, board, value = 0):
self.depth = remainingTurns
self.playerNum = playerNum
self.board = board
self.value = value
self.moves = availableMoves(self.board, 0)
self.children = []
self.createChildren()
def availableMoves(self, board):
self.availableSlots = []
for position in range(0,9):
if board[position] == 0:
availableSlots.append(position)
return self.availableSlots
def winCheck(self, state, playerNum):
self.winConditions = [[0, 1, 2],[3, 4, 5],[6, 7, 8],[0, 3, 6],[1, 4, 7],[2, 5, 8],[0, 4, 8],[2, 4, 6]]
self.win = 3
for row in self.winConditions:
self.checkA = self.state[row[0]]
self.checkB = self.state[row[1]]
self.checkC = self.state[row[2]]
if self.checkA + self.checkB + self.checkC == int(self.win * self.playerNum):
return True
return False
def createChildren(self):
if self.depth > 0:
for i in self.moves:
self.state = self.board
self.state[i] = self.playerNum
print(board)
self.children.append(Node(self.depth - 1, self.playerNum * -1, self.state, self.realVal(self.state, self.playerNum) ))
def realVal(self, value, playerNum):
value = self.winCheck(self.state, self.playerNum)
if value == True:
return maxsize * self.playerNum
else:
return 0
def minimax(node, depth, playerNum):
if depth == 0 or abs(node.value) == maxsize:
return node.value
bestValue = maxsize * -playerNum
for i in range(len(node.children)):
child = node.children[i]
val = minimax(child, depth - 1, -playerNum)
if (abs(maxsize * playerNum - val) < abs(maxsize * playerNum - bestValue)):
bestValue = val
return bestValue
def aiTurn(board, remainingTurns):
checkDraw(board)
print('Waiting for ai')
time.sleep(2)
board = board
state = board
currentPlayer = 1
tree = Node(remainingTurns, currentPlayer, state)
bestChoice = -100
bestValue = maxsize * -1
for i in range(len(tree.children)):
n_child = tree.children[i]
i_val = minimax(n_child, remainingTurns, -currentPlayer,)
if (abs(currentPlayer * maxsize - i_val) <= abs(currentPlayer * maxsize - bestValue)):
bestValue = i_val
bestChoice = i
print(bestChoice)
print(board)
#choice = minimax(tree, remainingTurns, 1)
board[bestChoice] = 1
print(board)
if checkWin(board, winConditions, True) == True:
completion(1)
else:
playerTurn(board, remainingTurns - 1)
def completion(state):
if state == 1:
print('The computer has won this game.')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
if state == 0:
print('you win!')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
if state == 2:
print('you drew')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
def playGame():
global board
board = [0,0,0,0,0,0,0,0,0]
global winConditions
winConditions = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6]
]
global remainingTurns
remainingTurns = 9
playerFirst = random.choice([True, False])
if playerFirst == True:
playerTurn(board, remainingTurns)
else:
aiTurn(board, remainingTurns)
if __name__ == '__main__':
playGame()
这是上面代码的输出
[1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, -1, 0, 0, 0, 0, 0, 0, 0]
[1, -1, 1, 0, 0, 0, 0, 0, 0]
[1, -1, 1, -1, 0, 0, 0, 0, 0]
[1, -1, 1, -1, 1, 0, 0, 0, 0]
[1, -1, 1, -1, 1, -1, 0, 0, 0]
[1, -1, 1, -1, 1, -1, 1, 0, 0]
[1, -1, 1, -1, 1, -1, 1, -1, 0]
[1, -1, 1, -1, 1, -1, 1, -1, 1]
[1, -1, 1, -1, 1, -1, 1, -1, -1]
[1, -1, 1, -1, 1, -1, 1, 1, -1]
[1, -1, 1, -1, 1, -1, 1, 1, 1]
[1, -1, 1, -1, 1, -1, -1, 1, 1]
[1, -1, 1, -1, 1, -1, -1, -1, 1]
[1, -1, 1, -1, 1, -1, -1, -1, -1
[1, -1, 1, -1, 1, 1, -1, -1, -1]
[1, -1, 1, -1, 1, 1, 1, -1, -1]
[1, -1, 1, -1, 1, 1, 1, 1, -1]
[1, -1, 1, -1, 1, 1, 1, 1, 1]
[1, -1, 1, -1, -1, 1, 1, 1, 1]
[1, -1, 1, -1, -1, -1, 1, 1, 1]
[1, -1, 1, -1, -1, -1, -1, 1, 1]
[1, -1, 1, -1, -1, -1, -1, -1, 1
[1, -1, 1, -1, -1, -1, -1, -1, -
[1, -1, 1, 1, -1, -1, -1, -1, -1
[1, -1, 1, 1, 1, -1, -1, -1, -1]
[1, -1, 1, 1, 1, 1, -1, -1, -1]
[1, -1, 1, 1, 1, 1, 1, -1, -1]
[1, -1, 1, 1, 1, 1, 1, 1, -1]
[1, -1, 1, 1, 1, 1, 1, 1, 1]
[1, -1, -1, 1, 1, 1, 1, 1, 1]
[1, -1, -1, -1, 1, 1, 1, 1, 1]
[1, -1, -1, -1, -1, 1, 1, 1, 1]
[1, -1, -1, -1, -1, -1, 1, 1, 1]
[1, -1, -1, -1, -1, -1, -1, 1, 1
[1, -1, -1, -1, -1, -1, -1, -1,
[1, -1, -1, -1, -1, -1, -1, -1,
[1, 1, -1, -1, -1, -1, -1, -1, -
[1, 1, 1, -1, -1, -1, -1, -1, -1
[1, 1, 1, 1, -1, -1, -1, -1, -1]
[1, 1, 1, 1, 1, -1, -1, -1, -1]
[1, 1, 1, 1, 1, 1, -1, -1, -1]
[1, 1, 1, 1, 1, 1, 1, -1, -1]
[1, 1, 1, 1, 1, 1, 1, 1, -1]
[1, 1, 1, 1, 1, 1, 1, 1, 1]
8
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1]
The computer has won this game.
有什么建议吗？
问题出在你初始化你的节点时，你只是复制 board:
的引用
self.board = board
而您应该复制这些值
self.board = board[::]
否则您所有的节点对象都引用同一个板：全局板。
我一直在尝试通过编写小游戏（例如井字游戏）来提高对 python 的理解。我从头开始创建了游戏副本，但随后开始寻找为游戏创建合理 AI 的方法。我决定使用 minimax 来实现这个目标。我找到了该算法的教程并尝试为游戏塑造它。
然而，当代码为 运行 时，在 ai 的第一个回合。棋盘上剩下的每个空 space 都用相同的符号填充，迫使获胜，使游戏无法玩。
由于我对算法不熟悉且缺乏经验，所以我从 youtube 教程中获取代码并对其进行编辑，使其适用于游戏。
这是代码
import random
import time
import sys
from sys import maxsize
#converts numbers from the board to X O and "" for printing out the board
def numToSymbol(board):
visual = board
for i in range(0, 9):
if visual[i] == -1:
visual[i]= "X"
elif visual[i] == 1:
visual[i] = "O"
elif visual[i] == 0:
visual[i] = " "
return visual
def symbolToNum(visual):
board = visual
for i in range(0, 9):
if board[i] == "X":
board[i] = -1
elif board[i] == "O":
board[i] = 1
elif board[i] == " ":
board[i] = 0
return board
# prints the board, first coverting numbers throught numtoSymbol
def drawBoard():
visual = numToSymbol(board)
print(
"|"+ str(visual[0]) + "|" + str(visual[1]) + "|" + str(visual[2]) + "| \n"
"-------\n"
"|"+ str(visual[3]) + "|" + str(visual[4]) + "|" + str(visual[5]) + "| \n"
"-------\n"
"|"+ str(visual[6]) + "|" + str(visual[7]) + "|" + str(visual[8]) + "| \n"
"-------")
symbolToNum(visual)
# checks the possible options for 3 in a row and if any are all held by one side returns true
def checkWin(board, winConditions, ai):
if ai == True:
win = 3
if ai == False:
win = -3
for row in winConditions:
checkA = board[row[0]]
checkB = board[row[1]]
checkC = board[row[2]]
if checkA + checkB + checkC == int(win):
return True
return False
def checkDraw(board):
emptyTile = 9
for tile in board:
if tile != 0:
emptyTile -= 1
if emptyTile == 0:
completion(2)
def availableMoves(board, bonus):
availableSlots = []
for position in range(0,9):
if board[position] == 0:
availableSlots.append(position + bonus)
return availableSlots
def playerTurn(board, remainingTurns):
board = board
checkDraw(board)
visual =drawBoard()
print("pick one of the available slots \n")
availableSlots = availableMoves(board, 1)
print(availableSlots)
choice = int(input('Select a tile from those shown above:\n')) -1
while True:
if 0 <= choice <= 8:
if board[choice] == 0:
board[choice] = -1
break
else:
choice = int(input('Select a tile from those shown above which has not already been selected:\n')) -1
else:
choice = int(input('Select a tile from those shown above:\n')) -1
visual = drawBoard()
if checkWin(board, winConditions, False) == True:
completion(0)
else:
aiTurn(board, remainingTurns - 1)
class Node(object):
def __init__(self, remainingTurns, playerNum, board, value = 0):
self.depth = remainingTurns
self.playerNum = playerNum
self.board = board
self.value = value
self.moves = availableMoves(self.board, 0)
self.children = []
self.createChildren()
def availableMoves(self, board):
self.availableSlots = []
for position in range(0,9):
if board[position] == 0:
availableSlots.append(position)
return self.availableSlots
def winCheck(self, state, playerNum):
self.winConditions = [[0, 1, 2],[3, 4, 5],[6, 7, 8],[0, 3, 6],[1, 4, 7],[2, 5, 8],[0, 4, 8],[2, 4, 6]]
self.win = 3
for row in self.winConditions:
self.checkA = self.state[row[0]]
self.checkB = self.state[row[1]]
self.checkC = self.state[row[2]]
if self.checkA + self.checkB + self.checkC == int(self.win * self.playerNum):
return True
return False
def createChildren(self):
if self.depth > 0:
for i in self.moves:
self.state = self.board
self.state[i] = self.playerNum
print(board)
self.children.append(Node(self.depth - 1, self.playerNum * -1, self.state, self.realVal(self.state, self.playerNum) ))
def realVal(self, value, playerNum):
value = self.winCheck(self.state, self.playerNum)
if value == True:
return maxsize * self.playerNum
else:
return 0
def minimax(node, depth, playerNum):
if depth == 0 or abs(node.value) == maxsize:
return node.value
bestValue = maxsize * -playerNum
for i in range(len(node.children)):
child = node.children[i]
val = minimax(child, depth - 1, -playerNum)
if (abs(maxsize * playerNum - val) < abs(maxsize * playerNum - bestValue)):
bestValue = val
return bestValue
def aiTurn(board, remainingTurns):
checkDraw(board)
print('Waiting for ai')
time.sleep(2)
board = board
state = board
currentPlayer = 1
tree = Node(remainingTurns, currentPlayer, state)
bestChoice = -100
bestValue = maxsize * -1
for i in range(len(tree.children)):
n_child = tree.children[i]
i_val = minimax(n_child, remainingTurns, -currentPlayer,)
if (abs(currentPlayer * maxsize - i_val) <= abs(currentPlayer * maxsize - bestValue)):
bestValue = i_val
bestChoice = i
print(bestChoice)
print(board)
#choice = minimax(tree, remainingTurns, 1)
board[bestChoice] = 1
print(board)
if checkWin(board, winConditions, True) == True:
completion(1)
else:
playerTurn(board, remainingTurns - 1)
def completion(state):
if state == 1:
print('The computer has won this game.')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
if state == 0:
print('you win!')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
if state == 2:
print('you drew')
choice = str(input('press y if you would like to play another game; Press n if you would not \n'))
if choice == 'y' or choice == 'Y':
playGame()
else:
sys.exit()
def playGame():
global board
board = [0,0,0,0,0,0,0,0,0]
global winConditions
winConditions = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6]
]
global remainingTurns
remainingTurns = 9
playerFirst = random.choice([True, False])
if playerFirst == True:
playerTurn(board, remainingTurns)
else:
aiTurn(board, remainingTurns)
if __name__ == '__main__':
playGame()
这是上面代码的输出
[1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, -1, 0, 0, 0, 0, 0, 0, 0]
[1, -1, 1, 0, 0, 0, 0, 0, 0]
[1, -1, 1, -1, 0, 0, 0, 0, 0]
[1, -1, 1, -1, 1, 0, 0, 0, 0]
[1, -1, 1, -1, 1, -1, 0, 0, 0]
[1, -1, 1, -1, 1, -1, 1, 0, 0]
[1, -1, 1, -1, 1, -1, 1, -1, 0]
[1, -1, 1, -1, 1, -1, 1, -1, 1]
[1, -1, 1, -1, 1, -1, 1, -1, -1]
[1, -1, 1, -1, 1, -1, 1, 1, -1]
[1, -1, 1, -1, 1, -1, 1, 1, 1]
[1, -1, 1, -1, 1, -1, -1, 1, 1]
[1, -1, 1, -1, 1, -1, -1, -1, 1]
[1, -1, 1, -1, 1, -1, -1, -1, -1
[1, -1, 1, -1, 1, 1, -1, -1, -1]
[1, -1, 1, -1, 1, 1, 1, -1, -1]
[1, -1, 1, -1, 1, 1, 1, 1, -1]
[1, -1, 1, -1, 1, 1, 1, 1, 1]
[1, -1, 1, -1, -1, 1, 1, 1, 1]
[1, -1, 1, -1, -1, -1, 1, 1, 1]
[1, -1, 1, -1, -1, -1, -1, 1, 1]
[1, -1, 1, -1, -1, -1, -1, -1, 1
[1, -1, 1, -1, -1, -1, -1, -1, -
[1, -1, 1, 1, -1, -1, -1, -1, -1
[1, -1, 1, 1, 1, -1, -1, -1, -1]
[1, -1, 1, 1, 1, 1, -1, -1, -1]
[1, -1, 1, 1, 1, 1, 1, -1, -1]
[1, -1, 1, 1, 1, 1, 1, 1, -1]
[1, -1, 1, 1, 1, 1, 1, 1, 1]
[1, -1, -1, 1, 1, 1, 1, 1, 1]
[1, -1, -1, -1, 1, 1, 1, 1, 1]
[1, -1, -1, -1, -1, 1, 1, 1, 1]
[1, -1, -1, -1, -1, -1, 1, 1, 1]
[1, -1, -1, -1, -1, -1, -1, 1, 1
[1, -1, -1, -1, -1, -1, -1, -1,
[1, -1, -1, -1, -1, -1, -1, -1,
[1, 1, -1, -1, -1, -1, -1, -1, -
[1, 1, 1, -1, -1, -1, -1, -1, -1
[1, 1, 1, 1, -1, -1, -1, -1, -1]
[1, 1, 1, 1, 1, -1, -1, -1, -1]
[1, 1, 1, 1, 1, 1, -1, -1, -1]
[1, 1, 1, 1, 1, 1, 1, -1, -1]
[1, 1, 1, 1, 1, 1, 1, 1, -1]
[1, 1, 1, 1, 1, 1, 1, 1, 1]
8
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1]
The computer has won this game.
有什么建议吗？
问题出在你初始化你的节点时，你只是复制 board:
self.board = board
而您应该复制这些值
self.board = board[::]
否则您所有的节点对象都引用同一个板：全局板。