I made a minimax algorithm for a Connect 4 game, and I would like to optimize it to improve the calculation time.
I have already done the classic optimization such as alpha beta pruning and a variable where I store all the play already calculated so as not to recalculate them. I think there are still optimizations to be done, but I can't find them.
My code (there may be some French word in it, sorry):
def is_position_a_winner(board, none_pice, row, col=4, length_win=4):
if type(row) in (list, tuple):
length_win, col, row = col, row[1], row[0]
item = board[row][col]
rows = len(board)
cols = len(board[0])
if item == none_pice:
return False
for delta_row, delta_col in [(1,-1), (0,1), (1,1), (1,0)]:
consecutive_items = 1
for delta in (1, -1):
delta_row *= delta
delta_col *= delta
next_row = row + delta_row
next_col = col + delta_col
while 0 <= next_row < rows and 0 <= next_col < cols:
if board[next_row][next_col] == item:
consecutive_items += 1
else:
break
if consecutive_items == length_win:
return True
next_row += delta_row
next_col += delta_col
return False
def is_full(board, none_pice=0):
for row in board:
for col in row:
if col == none_pice:
return False
return True
def calc_piece_pos(col, board, none_pice=0):
for row in range(5, -1, -1):
if board[row][col] == none_pice:
return (row, col)
return False
def inverse(pice):
if pice == 1: return 2
if pice == 2: return 1
def mid(a,b):
a1 = abs(a-3)
b1 = abs(b-3)
if a1 < b1:
return a
else:
return b
def get_hash(board):
return hash(tuple([tuple(i) for i in board]))
def load_save(board, lvl):
try:
return save[lvl][get_hash(board)]
except KeyError:
return None
def save_calcul(board, score, lvl):
global save
try:
save[lvl][get_hash(board)] = score
except KeyError:
pass
test = [3,2,4,1,5,0,6]
def ia(board, pice, limit=6):
global save
save = [{} for _ in range(limit)]
best_score = -100
move = None
for i in range(7):
col = test[i]
pos = calc_piece_pos(col, board)
if pos:
board[pos[0]][pos[1]] = pice
score = mini_max(board, inverse(pice), limit-1, False, pos, -100, 100)
board[pos[0]][pos[1]] = 0
print(best_score, score, move, col)
if score > best_score:
best_score, move = score, col
elif score == best_score:
move = mid(move, col)
return move
def mini_max(board, pice, limit, is_max, last_move, alpha, beta):
global save
load = load_save(board, limit)
if load is not None:
return load
if is_position_a_winner(board, 0, last_move):
score = -50 if is_max else 50
save_calcul(board, score, limit)
return score
elif limit == 0 or is_full(board):
save_calcul(board, 0, limit)
return 0
else:
if is_max:
best_score = -100
for i in range(7):
col = test[i]
pos = calc_piece_pos(col, board)
if pos:
board[pos[0]][pos[1]] = pice
score = mini_max(board, inverse(pice), limit-1, False, pos, alpha, beta)
if score != 0:
score -= (1 if score > 0 else -1)
board[pos[0]][pos[1]] = 0
best_score = max(score, best_score)
alpha = max(alpha, score)
if beta <= alpha:
break
save_calcul(board, best_score, limit)
return best_score
else:
best_score = 100
for i in range(7):
col = test[i]
pos = calc_piece_pos(col, board)
if pos:
board[pos[0]][pos[1]] = pice
score = mini_max(board, inverse(pice), limit-1, True, pos, alpha, beta)
if score != 0:
score -= (1 if score > 0 else -1)
board[pos[0]][pos[1]] = 0
best_score = min(score, best_score)
beta = min(beta, score)
if beta <= alpha:
break
save_calcul(board, best_score, limit)
return best_score
if __name__ == "__main__":
import time
board = [
[0,0,0,2,0,0,0],
[0,0,0,1,0,0,0],
[0,0,0,2,0,0,0],
[0,0,0,1,2,0,0],
[0,0,0,2,1,0,0],
[0,0,2,1,1,0,0]
]
board = [[0 for _ in range(7)] for _ in range(6)]
t=time.monotonic()
print(ia(board, 1, 14))
print(time.monotonic()-t)
