I have created a game in python like tic-tac-toe where I can choose the size of the board and amount of pieces you need in a row to win. I also have created a bot with minimax, alpha-beta pruning, transposition tables, and iterative deepening. I'm using python and my board representation is just a 2d array. For some reason my algorithm is only calculating like 600 nodes per second when there are chess engines out there with 100,000+ nodes per second. I know python is slow and the board representation would affect the speed, but I don't think it should be only calculating around 600 nodes per second. I also have an evaluation function that does a loop of the whole board and evaluates the position of the pieces. I'm just trying to figure out how to speed up the algorithm because it seems unreasonably slow.
My algorithm:
def tt_minimax(board, plr, alpha, beta, depth):
global tt_start_time
if ITERATIVEDEEPENING and timeit.default_timer()-tt_start_time >= MAXTIME:
return "UNFINISHED", 0
alpha_org = alpha
tt_code = tt_hash(board)
pv_move = []
if tt_code in TRANSPOSITION_TABLE:
tt_entry = TRANSPOSITION_TABLE[tt_code]
if tt_entry[3] >= depth:
if tt_entry[2] == 0: # checking for Exact
return tt_entry[0], tt_entry[1]
elif tt_entry[2] == -1: # lower bound
alpha = max(alpha, tt_entry[1])
elif tt_entry[2] == 1: # upper bound
beta = min(beta, tt_entry[1])
if alpha >= beta:
return tt_entry[0], tt_entry[1]
else:
pv_move = tt_entry[0]
global tt_node_count
tt_node_count += 1
moves = find_moves(board)
#random.shuffle(moves)
if pv_move:
moves.insert(0, moves.pop(moves.index(pv_move)))
# if drawn
if len(moves) == 0:
return "none", 0
# maximizing
if plr == 1:
best_score = MIN
best_move = []
for movePair in moves:
y, x = movePair[0], movePair[1]
board[y][x] = plr
wt_code = tt_hash(board)
if wt_code in WIN_TABLE:
test_result = WIN_TABLE[wt_code]
else:
test_result = test_for_win(board)
WIN_TABLE[wt_code] = test_result
if test_result == plr:
evaluation = 1000 + TTD + depth
if evaluation > best_score:
best_score = evaluation
best_move = movePair
elif depth > 0:
returned = tt_minimax(board, 2, alpha, beta, depth - 1)
if returned[0] == "UNFINISHED":
return returned
return_eval = returned[1]
if return_eval > best_score:
best_score = return_eval
best_move = movePair
else:
evaluation = evaluate(board, 2)
if evaluation > best_score:
best_score = evaluation
best_move = movePair
board[y][x] = 0
alpha = max(alpha, best_score)
if beta <= alpha:
break
tt_store(TRANSPOSITION_TABLE, board, alpha_org, beta,
best_move, best_score, depth)
return best_move, best_score
# minimizing
else:
best_score = MAX
best_move = []
for movePair in moves:
y, x = movePair[0], movePair[1]
board[y][x] = plr
wt_code = tt_hash(board)
if wt_code in WIN_TABLE:
test_result = WIN_TABLE[wt_code]
else:
test_result = test_for_win(board)
WIN_TABLE[wt_code] = test_result
if test_result == plr:
evaluation = -1000 - depth
if evaluation < best_score:
best_score = evaluation
best_move = movePair
elif depth > 0:
returned = tt_minimax(board, 1, alpha, beta, depth - 1)
if returned[0] == "UNFINISHED":
return returned
return_eval = returned[1]
if return_eval < best_score:
best_score = return_eval
best_move = movePair
else:
evaluation = evaluate(board, 2)
if evaluation < best_score:
best_score = evaluation
best_move = movePair
board[y][x] = 0
beta = min(beta, best_score)
if beta <= alpha:
break
tt_store(TRANSPOSITION_TABLE, board, alpha_org, beta,
best_move, best_score, depth)
return best_move, best_score
C is more than somewhat faster than Python. C is a LOT faster than Python. Converting this to C would be HUGE. Then you can ask again because the way something is coded in C is also HUGE. Multiply many tens faster by many tens faster and your program will be screaming in C.
Python, well, suffice it to say that Python is not meant to be fast. Speed was not a factor in Python's initial design and now that everything is an object... Suffice it to say that Python gets slower as it gets better. I like Python for its purpose, but C has a purpose too. Your program is a perfect example of the purpose of C. Use Python as a wrapper to play the game. Use C to calculate the next move.