I have been trying to use a minimax algorithm for a game of connect 4 then implementing alpha beta pruning later to make it stronger. But I am running into the issue where the computer is not returning the best move it will just run through minimax 5 times then give up and not return best move. I'm not really sure how to deal with this issue. Here is the relevant code: Note: Running at a low depth on purpose because my computer can't handle a lot of calculating and just for testing purposes atm
import pygame as p
import sys
import math
from time import sleep
board = [
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
]
def gravity(col):
for r in range(5, -1, -1):
if board[r][col] == 0:
return r
def place_counter(playe, mousex, mousey):
global colour
if playe == 1:
colour = (255, 255, 0)
if playe == 2:
colour = (255, 0, 0)
xbox = math.floor(mousex / 100)
ybox = math.floor(mousey / 100)
row = gravity(xbox)
board[row][xbox] = playe
print_board(board)
p.draw.circle(screen, colour, (50 + 100 * xbox, 50 + 100 * row), 40)
def c_move(b_move):
place_counter(2, b_move, b_move)
def comp_move():
best_score = - 10
best_move = 0
for key in range(len(board)):
print(key)
if board[key][gravity(key)] == 0:
board[key][gravity(key)] = bot
score = minimax(0, False)
board[key][gravity(key)] = 0
if score > best_score:
best_score = score
best_move = key
if best_move != 0:
c_move(best_move)
print_board(board)
def minimax(depth, isMaximizing):
if isMaximizing:
best_score = -800
for key in range(len(board)):
if board[key][gravity(key)] == 0:
board[key][gravity(key)] = bot
score = minimax(depth + 1, False)
board[key][gravity(key)] = 0
if score > best_score:
best_score = score
if depth == 5:
best_score = score
return best_score
else:
best_score = 800
for key in range(len(board)):
if board[key][gravity(key)] == 0:
board[key][gravity(key)] = player
score = minimax(depth + 1, True)
board[key][gravity(key)] = 0
if score < best_score:
best_score = score
if depth == 5:
best_score = score
return best_score
while game_over is False:
for event in p.event.get():
if event.type == p.QUIT:
p.quit()
sys.exit()
if event.type == SCREEN_UPDATE:
p.display.update()
if event.type == p.MOUSEBUTTONDOWN:
if turn % 2 != 0:
player1_move()
winning_move(1)
turn += 1
else:
comp_move()
winning_move(2)
turn += 1
Any suggestions are very welcome
You will have to provide an evaluation function that estimates the score at the leaves of your search tree (when depth==5). As it is now, all possible sequences of moves lead to either 800 or -800, so effectively the first move will be chosen every time.