import copy
import math
# import sys # 导入sys模块
# sys.setrecursionlimit(3000000) # 将默认的递归深度修改为3000
import random
X = "X"
O = "O"
EMPTY = None
def Counter(board):
CounterX = 0
CounterO = 0
CounterE = 0
ConuterList = []
# if terminal(board):
# return 1
for i in range(0, 3):
for j in range(0, 3):
if board[i][j] == X:
CounterX += 1
elif board[i][j] == O:
CounterO += 1
else:
CounterE += 1
ConuterList.append(CounterX)
ConuterList.append(CounterO)
ConuterList.append(CounterE)
return ConuterList
def initial_state():
"""
Returns starting state of the board.
"""
return [[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY]]
def player(board):
"""
Returns player who has the next turn on a board.
"""
CounterX = 0
CounterO = 0
CounterE = 0
if terminal(board):
return 1
for i in range(0,3):
for j in range(0, 3):
if board[i][j] == X:
CounterX += 1
elif board[i][j] == O:
CounterO += 1
else:CounterE += 1
if CounterE == 9:
return X
elif CounterX > CounterO:
return O
elif CounterX == CounterX:
return X
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
if terminal(board):
return 0
ActionList=[]
for i in range(0,3):
for j in range(0, 3):
if board[i][j] == EMPTY:
ActionList.append((i,j))
return ActionList
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
Newboard = copy.deepcopy(board)
if player(Newboard) == X:
Newboard[action[0]][action[1]] = X
return Newboard
elif player(Newboard) == O:
Newboard[action[0]][action[1]] = O
return Newboard
else:
raise Exception
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
if terminal(board):
counterList = Counter(board)
for i in range(0, 3):
if board[0][0] == board[1][1] == board[2][2] != EMPTY:
if board[0][0] == X:
winner = 'X'
else:
winner = 'O'
return winner
elif board[0][2] == board[1][1] == board[2][0] != EMPTY:
if board[0][2] == X:
winner = 'X'
else:
winner = 'O'
return winner
elif board[i][0] == board[i][1] == board[i][2] != EMPTY:
if board[i][0] == X:
winner = 'X'
else:
winner = 'O'
return winner
elif board[0][i] == board[1][i] == board[2][i] != EMPTY:
if board[1][i] == X:
winner = 'X'
else:
winner = 'O'
return winner
if counterList[2] == 0:
winner = None
return winner
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
if board[0][0] == board[1][1] == board[2][2] and board[0][0] != EMPTY:
return True
elif board[0][2] == board[1][1] == board[2][0] and board[0][2] != EMPTY:
return True
for i in range(0,3):
if board[i][0] == board[i][1] == board[i][2]!= EMPTY:
return True
elif board[0][i] == board[1][i] == board[2][i]!= EMPTY:
return True
elif Counter(board)[2] == 0:
return True
return False
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
if terminal(board):
win = winner(board)
if win == 'X':
return 1
elif win == 'O':
return -1
else:
return 0
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
if terminal(board):
return None
#X
if player(board) == X:
actionlist = actions(board)
bestmove = [None]*9
index = 0
bestValue = -2
for i in range(0,len(actionlist)):
Newboard = copy.deepcopy(board)
Newboard[actionlist[i][0]][actionlist[i][1]] = X
value = Min(Newboard)
if value > bestValue:
bestValue = value
index = 0
bestmove[0] = actionlist[i]
elif value == bestValue:
index += 1
bestmove[index] = (actionlist[i])
if index > 1:
index = random.randint(0,index)
return bestmove[index]
if player(board) == O:
actionlist = actions(board)
bestmove = [None]*9
index = 0
bestValue = 2
for i in range(0, len(actionlist)):
Newboard = copy.deepcopy(board)
Newboard[actionlist[i][0]][actionlist[i][1]] = O
value = Max(Newboard)
if value < bestValue:
bestValue = value
index = 0
#bestmove.append(actionlist[i])
bestmove[0] = actionlist[i]
elif value == bestValue:
index += 1
#bestmove.append(actionlist[i])
bestmove[index] = (actionlist[i])
if index > 0:
index = random.randint(0, index)
print(bestmove[index])
return bestmove[index]
def Max(board):
"""
Returns the optimal action for the current player on the board.
"""
if terminal(board):
return utility(board)
INF=-2
actionList = actions(board)
for i in actionList:
Newboard = result(board,i)
val = Min(Newboard)
if val > INF:
INF = val
return INF
def Min(board):
"""
Returns the optimal action for the current player on the board.
"""
if terminal(board):
return utility(board)
INF = 2
actionList = actions(board)
for i in actionList:
Newboard = result(board, i)
val = Max(Newboard)
if val < INF:
INF = val
return INF
