Home
Syllabus
Readings
Projects
Tests
def evaluate_board(cur_board, depth):
result = cur_board.get_result()
if result != GAME_ON:
if result == TIE_GAME: return 0
elif result == CURRENT_WINS: return 1000
else: return -1000
elif depth == 0:
return cur_board.get_heuristic()
else:
best = -1001
for move in cur_board.get_move_options():
next_board = cur_board.copy()
next_board.make_move(move)
result = -evaluate_board(next_board, depth - 1)
if result > best:
best = result
return best
def evaluate_board(cur_board, depth, alpha, beta):
result = cur_board.get_result()
if result != GAME_ON:
if result == TIE_GAME: return 0
elif result == CURRENT_WINS: return 1000
else: return -1000
elif depth == 0:
return cur_board.get_heuristic()
else:
for move in cur_board.get_move_options():
next_board = cur_board.copy()
next_board.make_move(move)
result = -evaluate_board(next_board, depth - 1, -beta, -alpha)
if result > alpha:
alpha = result
if beta <= alpha:
break
return alpha
(Numbers represent the average number of nodes searched over the first three moves of the Oware rules of Mancala, where the computer plays second.)
| Algorithm | Depth 6 | Depth 8 | Depth 10 |
| Minimax search | 24,000 | 307,000 | 16,614,000 |
| Alpha-beta search | 2,000 | 18,500 | 140,000 |
(There's no real reason to restrict ourselves to even depths: They're just the numbers I used to depict performance here.)
With a depth of 8, minimax search takes about 16 times as long. On my computer, this is the difference between taking 13 seconds versus less than 1 second — without any degradation in move quality, since they both search to the same depth. At a depth of 10, alpha-beta took about 7 seconds, whereas minimax took 6.5 minutes to arrive at the same result.