minimax algorithm optimization for Connect 4

Question

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)

Answer 1

Naming

The name of this function conveys no meaning:

def ia

You should choose a longer name because I can't figure out what it stands for given the context of a Connect 4 game.

there may be some French word

In this line:

def calc_piece_pos(col, board, none_pice=0):

I'm not sure what "pice" means. The name of the function uses the word "piece". If "pice" is a French variant of "piece", I suggest using "piece" everywhere in the code.

Documentation

The PEP 8 style guide recommends adding docstrings for functions. The docstring should summarize the goal of the function as well as provide details of the input and return types.

There should also be a docstring at the top of the code to summarize its purpose, such as:

"""
Connect 4 game.
Add more details about what the code is doing.
"""

When I run the code, I see a few lines of output, but I don't know what it represents. The docstring could also include details about the output.

Simpler

In the mid function, the following code:

a1 = abs(a-3)
b1 = abs(b-3)
if a1 < b1:
 return a
else:
 return b

would be simpler without the intermediate variables a1/b1:

if abs(a-3) < abs(b-3):
 return a
else:
 return b

This line in the ia function:

best_score, move = score, col

would be easier to understand as 2 lines:

best_score = score
move = col

Layout

In the inverse function, the following code:

if pice == 1: return 2
if pice == 2: return 1

the return is more commonly on a separate line:

if pice == 1:
 return 2
if pice == 2:
 return 1

Magic number

The number "7" is used in several places in the code. It would be good to assign it to a constant with a meaningful name. For example, if it represents the number of columns in a game board:

COLUMNS = 7

DRY

In the mini_max function, there is a lot of duplicated code between the if is_max and the else branches. At a minimum, you could factor out the last 2 lines:

if is_max:
 #
else:
 #
save_calcul(board, best_score, limit)
return best_score