alphabeta演算法

Ⅰ python 井字棋 ALPHA-BETA剪枝演算法和暴力演算法 具體代碼

#!/usr/bin/env python
'''Tic tac toe in python, Minimax with alpha-beta pruning.'''
import sys
import random
import getopt

# Board: array of 9 int, positionally numbered like this:
# 0 1 2
# 3 4 5
# 6 7 8

# Well-known board positions
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))
# The order in which slots get checked for absence of a player's token:
SLOTS = (0, 1, 2, 3, 4, 5, 6, 7, 8)

# Internal-use values. Chosen so that the "winner" of a finished
# game has an appropriate value, as X minimizes and O maximizes
# the board's value (function board_valuation() defines "value")
# Internally, the computer always plays Os, even though the markers[]
# array can change based on -r command line flag.
X_token = -1
Open_token = 0
O_token = 1

# Strings for output: player's markers, phrase for end-of-game
MARKERS = ['_', 'O', 'X']
END_PHRASE = ('draw', 'win', 'loss')

HUMAN = 1
COMPUTER = 0

def board_valuation(board, player, next_player, alpha, beta):
'''Dynamic and static evaluation of board position.'''
# Static evaluation - value for next_player
wnnr = winner(board)
if wnnr != Open_token:
# Not a draw or a move left: someone won
return wnnr
elif not legal_move_left(board):
# Draw - no moves left
return 0 # Cat
# If flow-of-control gets here, no winner yet, not a draw.
# Check all legal moves for "player"
for move in SLOTS:
if board[move] == Open_token:
board[move] = player
val = board_valuation(board, next_player, player, alpha, beta)
board[move] = Open_token
if player == O_token: # Maximizing player
if val > alpha:
alpha = val
if alpha >= beta:
return beta
else: # X_token player, minimizing
if val < beta:
beta = val
if beta <= alpha:
return alpha
if player == O_token:
retval = alpha
else:
retval = beta
return retval

def print_board(board):
'''Print the board in human-readable format.
Called with current board (array of 9 ints).
'''
for row in PRINTING_TRIADS:
for hole in row:
print MARKERS[board[hole]],
print

def legal_move_left(board):
''' Returns True if a legal move remains, False if not. '''
for slot in SLOTS:
if board[slot] == Open_token:
return True
return False

def winner(board):
''' Returns -1 if X wins, 1 if O wins, 0 for a cat game,
0 for an unfinished game.
Returns the first "win" it finds, so check after each move.
Note that clever choices of X_token, O_token, Open_token
make this work better.
'''
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]] # Take advantage of "_token" values
return 0

def determine_move(board):
''' Determine Os next move. Check that a legal move remains before calling.
Randomly picks a single move from any group of moves with the same value.
'''
best_val = -2 # 1 less than min of O_token, X_token
my_moves = []
for move in SLOTS:
if board[move] == Open_token:
board[move] = O_token
val = board_valuation(board, X_token, O_token, -2, 2)
board[move] = Open_token
print "My move", move, "causes a", 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)

def recv_human_move(board):
''' Encapsulate human's input reception and validation.
Call with current board configuration. Returns
an int of value 0..8, the Human's move.
'''
looping = True
while looping:
try:
inp = input("Your move: ")
yrmv = int(inp)
if 0 <= yrmv <= 8:
if board[yrmv] == Open_token:
looping = False
else:
print "Spot already filled."
else:
print "Bad move, no donut."

except EOFError:
print
sys.exit(0)
except NameError:
print "Not 0-9, try again."
except SyntaxError:
print "Not 0-9, try again."

if looping:
print_board(board)

return yrmv

def usage(progname):
'''Call with name of program, to explain its usage.'''
print progname + ": Tic Tac Toe in python"
print "Usage:", progname, "[-h] [-c] [-r] [-x] [-X]"
print "Flags:"
print "-x, -X: print this usage message, then exit."
print "-h: human goes first (default)"
print "-c: computer goes first"
print "-r: computer is X, human is O"
print "The computer O and the human plays X by default."

def main():
'''Call without arguments from __main__ context.'''
try:
opts, args = getopt.getopt(sys.argv[1:], "chrxX",
["human", "computer", "help"])
except getopt.GetoptError:
# print help information and exit:
usage(sys.argv[0])
sys.exit(2)

next_move = HUMAN # Human goes first by default

for opt, arg in opts:
if opt == "-h":
next_move = HUMAN
if opt == "-c":
next_move = COMPUTER
if opt == "-r":
MARKERS[-1] = 'O'
MARKERS[1] = 'X'
if opt in ("-x", "-X", "--help"):
usage(sys.argv[0])
sys.exit(1)

# Initial state of board: all open spots.
board = [Open_token, Open_token, Open_token, Open_token, Open_token,
Open_token, Open_token, Open_token, Open_token]

# State machine to decide who goes next, and when the game ends.
# This allows letting computer or human go first.
while legal_move_left(board) and winner(board) == Open_token:
print
print_board(board)

if next_move == HUMAN and legal_move_left(board):
humanmv = recv_human_move(board)
board[humanmv] = X_token
next_move = COMPUTER

if next_move == COMPUTER and legal_move_left(board):
mymv = determine_move(board)
print "I choose", mymv
board[mymv] = O_token
next_move = HUMAN

print_board(board)
# Final board state/winner and congratulatory output.
try:
# "You won" should never appear on output: the program
# should always at least draw.
print ["Cat got the game", "I won", "You won"][winner(board)]
except IndexError:
print "Really bad error, winner is", winner(board)

sys.exit(0)
#-------
if __name__ == '__main__':
try:
main()
except KeyboardInterrupt:
print
sys.exit(1)

Ⅱ 10、填空在AlphaBeta剪枝演算法中,我們把一個結點可能取值的上界記作____值

這個問題問的不是很清楚，個人理解，在AlphaBeta剪枝演算法中，可以把一個節點可能取值的上界記作 Beta 值。
AlphaBeta剪枝演算法是對極大極小演算法的優化，效率更高。極大極小是一種暴力搜索策略，需要遍歷所有可能的情況，隨著節點數特別是深度的增加，演算法性能會大幅下降。AlphaBeta剪枝演算法採用遞歸的方式進行倒推估算，可以在搜索過程中剪除無用的分支，從而減少不必要的搜索（這些搜索中不會有滿足要求的答案），提升演算法的效率。
可以這樣簡單地理解吧，每一層的節點都有Alpha（下界）、Beta（上界），而且是動態調整的，如果在推導過程中發現 Alpha>=Beta，那麼就可以終止當前節點往下各層級的搜索，達到提高效率的目的。

Ⅲ alpha-beta搜索演算法思想（十萬火急）

博弈啊，我以前寫過，大致框架是：

int search(，顏色,deep,alpha,beta)
{
if(deep=最大搜索步數）
return 估值（局面，顏色）；
for(遍歷所有可行走法）
{
局面.走棋；
Score=-int search(局面，-顏色,deep+1,-beta,-alpha)
if(Score>=beta)
return(Score);
if(Score>alpha)
alpha=Score;
局面.撤銷走棋；
}
return 出現過的最大Score；
}

調用的時候是 search(局面，電腦的顏色,0,負無窮,正無窮),得到一個局面的評分