代碼參考自中國大學mooc上人工智能與信息社會陳斌老師的算法，我在原來的基礎上增加了玩家輸入的異常捕獲 AlphaBeta剪枝算法是對Minimax方法的優化，能夠極大提高搜索樹的效率，如果對這個算法感興趣的可以去參考相關資料。 當正確理解AlphaBeta剪枝算法后，還可以將它應用在象棋、圍棋等一些高級游戲的算法搜索上，使得電腦尋找最優勝率的速度加快
python代碼實現
#coding:utf-8
'''井字棋(Tic tac toe)Python3語言實現, 帶有Alpha-Beta剪枝的Minimax算法.
代碼參考自中國大學mooc 人工智能與信息社會(陳斌)'''
import random
# 用如下的9個數字來表示棋盤的位置:
# 0? 1? 2
# 3? 4? 5
# 6? 7? 8
# 設定獲勝的組合方式(橫、豎、斜)
WINNING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8),
(0, 3, 6), (1, 4, 7),(2, 5, 8),
(0, 4, 8), (2, 4, 6))
# 設定棋盤按一行三個打印
PRINTING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8))
# 用一維列表表示棋盤:
SLOTS = (0, 1, 2, 3, 4, 5, 6, 7, 8)
# -1表示X玩家 0表示空位 1表示O玩家.
X_token = -1
Open_token = 0
O_token = 1
MARKERS = ['_', 'O', 'X']
END_PHRASE = ('平局', '勝利', '失敗')
def alpha_beta_valuation(board, player, next_player, alpha, beta):
"""運用AlphaBeta剪枝來計算當前局面的分值
因為搜索層數少，總能搜索到最終局面，估值結果為[-1,0,1]
"""
wnnr = winner(board)
if wnnr != Open_token:
# 有玩家獲勝
return wnnr
elif not legal_move_left(board):
# 沒有空位,平局
return 0
# 檢查當前玩家"player"的所有可落子點
for move in SLOTS:
if board[move] == Open_token:
board[move] = player
# 落子之后交換玩家，繼續檢驗
val = alpha_beta_valuation(board, next_player, player, alpha, beta)
board[move] = Open_token
if player == O_token:? # 當前玩家是O,是Max玩家(記號是1)
if val > alpha:
alpha = val
if alpha >= beta:
return beta? # 直接返回當前的最大可能取值beta, 進行剪枝
else:? # 當前玩家是X,是Min玩家(記號是-1)
if val < beta:
beta = val
if beta <= alpha:
return alpha? # 直接返回當前的最小可能取值alpha, 進行剪枝
if player == O_token:
retval = alpha
else:
retval = beta
return retval
def print_board(board):
"""打印當前棋盤"""
for row in PRINTING_TRIADS:
r = ' '
for hole in row:
r += MARKERS[board[hole]] + ' '
print(r)
def legal_move_left(board):
""" 判斷棋盤上是否還有空位 """
for slot in SLOTS:
if board[slot] == Open_token:
return True
return False
def winner(board):
""" 判斷局面的勝者,返回值-1表示X獲勝,1表示O獲勝,0表示平局或者未結束"""
for triad in WINNING_TRIADS:
triad_sum = board[triad[0]] + board[triad[1]] + board[triad[2]]
if triad_sum == 3 or triad_sum == -3:
return board[triad[0]]? # 表示棋子的數值恰好也是-1:X,1:O
return 0
def determine_move(board):
"""決定電腦(玩家O)的下一步棋,若估值相同則隨機選取步數"""
best_val = -2? # 本程序估值結果只在[-1,0,1]中
my_moves = []
print("開始思考")
for move in SLOTS:
if board[move] == Open_token:
board[move] = O_token
val = alpha_beta_valuation(board, X_token, O_token, -2, 2)
board[move] = Open_token
print("Computer如果下在", move, ",將導致", END_PHRASE[val])
if val > best_val:
best_val = val
my_moves = [move]
if val == best_val:
my_moves.append(move)
return random.choice(my_moves)
HUMAN = 1
COMPUTER = 0
def main():
"""主函數,先決定誰是X(先手方),再開始下棋"""
next_move = HUMAN
opt = input("請選擇先手方，輸入X表示玩家先手，輸入O表示電腦先手：")
if opt == "X":
next_move = HUMAN
elif opt == "O":
next_move = COMPUTER
else:
print("輸入有誤，默認玩家先手")
# 初始化空棋盤
board = [Open_token for i in range(9)]
# 開始下棋
while legal_move_left(board) and winner(board) == Open_token:
print()
print_board(board)
if next_move == HUMAN and legal_move_left(board):
try:
humanmv = int(input("請輸入你要落子的位置(0-8)："))
if board[humanmv] != Open_token:
continue
board[humanmv] = X_token
next_move = COMPUTER
except:
print("輸入有誤，請重試")
continue
if next_move == COMPUTER and legal_move_left(board):
mymv = determine_move(board)
print("Computer最終決定下在", mymv)
board[mymv] = O_token
next_move = HUMAN
# 輸出結果
print_board(board)
print(["平局", "Computer贏了", "你贏了"][winner(board)])
if __name__ == '__main__':
main()
運行結果
)
