I'm really stuck. I don't understand why I'm still getting this IndexError from my connectfour minimax function

Here’s the error message I get (also please look at this picture to see the board state):

Traceback (most recent call last):
  File "tester.py", line 325, in <module>
    aimove = minimax(bitted, True, 5, -float("Inf"), float("Inf"))[1]
  File "tester.py", line 273, in minimax
    hypothetical_value = minimax(copied, False, depth - 1, alpha, beta)[0]
  File "tester.py", line 303, in minimax
    hypothetical_value = minimax(copied, True, depth -1, alpha, beta)[0]
  File "tester.py", line 273, in minimax
    hypothetical_value = minimax(copied, False, depth - 1, alpha, beta)[0]
  File "tester.py", line 303, in minimax
    hypothetical_value = minimax(copied, True, depth -1, alpha, beta)[0]
  File "tester.py", line 269, in minimax
    best_move = centredmoves[0]
IndexError: list index out of range

Here’s how I understand the error message:

In the final board state shown just above where the error occurs (see picture), there are only four spaces left in total - all of which are in column 7. Using this board with four spaces left, the minimax function is called in the line “aimove = minimax(bitted, True, 5, -float(“Inf”), float(“Inf”))[1]”. Everything seems to be going fine so far.

Because it is recursive, the minimax function is then called inside the minimax function in this line (shown in the error message too):

“hypothetical_value = minimax(copied, False, depth - 1, alpha, beta)[0]”

In fact, this is done three more times (as seen in the error message). What that means I think is that column 7 is now full. There were only four spaces left after all.

Naturally, the IndexError message then arises because there are no available moves left - so the list remains empty - hence why there’s an error even though I’m referring to the first item of the list.

…But the script shouldn’t even get to this line when the list is empty:

“best_move = centredmoves[0]”

…it should see that theclass.draw == True (or theclass.gameover == True etc.) at the top of the minimax function, and return the appropriate value without going down to the part where it says “best_move = centredmoves[0]”.

This has really stumped me. The unfortunate thing is the code is on the long side, but please don’t be put off by that. It’s really just two classes and a function when it comes down to it, and I’ve deleted a lot of unnecessary parts from the repository in the code I pasted below.

Here’s the repository, and here’s the code:

import copy
import sys, os

class Bitboard:
	turn = 0
	xwin = 0
	owin = 0
	gameover = False
	draw = False

	def __init__(self, board):
		self.oldboard = board

	def get_position_and_mask(self):
		self.position, self.mask = '', ''
		# Start with right-most column
		for j in range(13, 0, -2):
			self.mask += "0"
			self.position += "0"        
			# Start with top row
			for i in range(0, 6, 1):
				if self.oldboard[i][j] == "X" or self.oldboard[i][j] == "O":
					self.mask += "1"
				elif self.oldboard[i][j] == " ":
					self.mask += "0"
				if self.oldboard[i][j] == "X":
					self.position += "1"
				else:
					self.position += "0"
		self.position = int(self.position, 2)
		self.mask = int(self.mask, 2)



	def available_moves(self):
		moves = []
		positionone = self.mask & (1 << 5)                                  
		positiontwo = self.mask & (1 << 12)            
		positionthree = self.mask & (1 << 19)            
		positionfour = self.mask & (1 << 26)            
		positionfive = self.mask & (1 << 33)
		positionsix = self.mask & (1 << 40)                 
		positionseven = self.mask & (1 << 47)  
		if positionone == 0:
			moves.append(1)
		if positiontwo == 0:
			moves.append(2)
		if positionthree == 0:
			moves.append(3) 
		if positionfour == 0:
			moves.append(4)
		if positionfive == 0:
			moves.append(5)
		if positionsix == 0:
			moves.append(6)         
		if positionseven == 0:
			moves.append(7)                  
		return moves

	def make_move(self, column):
		self.turn += 1
		new_position = self.position ^ self.mask
		new_mask = self.mask | (self.mask + (1 << (column*7)))
		self.position = new_position
		self.mask = new_mask

	def connected_four(self):
		#horizontal check  
		crosses = self.position
		mask = self.mask
		naughts = crosses ^ mask
		bitmaps = [crosses, naughts]
		for maps in bitmaps:
			# Horizontal check
			m = maps & (maps >> 7)
			if m & (m >> 14):
				if maps == crosses:
					self.xwin = 1
				elif maps == naughts:
					self.owin = -1
				self.gameover = True
				return
			# Diagonal \
			m = maps & (maps >> 6)
			if m & (m >> 12):
				if maps == crosses:
					self.xwin = 1
				elif maps == naughts:
					self.owin = -1
				self.gameover = True
				return
			# Diagonal /
			m = maps & (maps >> 8)
			if m & (m >> 16):
				if maps == crosses:
					self.xwin = 1
				elif maps == naughts:
					self.owin = -1
				self.gameover = True
				return
    			# Vertical
			m = maps & (maps >> 1)
			if m & (m >> 2):
				if maps == crosses:
					self.xwin = 1
				elif maps == naughts:
					self.owin = -1
				self.gameover = True
				return
		#checks for the draw
		one = self.mask & (1 << 5)
                two = self.mask & (1 << 12)
                three = self.mask & (1 << 19)
                four = self.mask & (1 << 26)
                five = self.mask & (1 << 33)
                six = self.mask & (1 << 40)
                seven = self.mask & (1 << 47)
		if one != 0 and two != 0 and three != 0 and four != 0 and five != 0 and six != 0 and seven != 0:
			self.draw = True

class ConnectFour():
	turn = 0
	evanorodd = 0
	gameover = False
	draw = False
	xwin = 0
	owin = 0
	
	def __init__(self):
		self.board = [[" " for column in range(15)] for row in range(6)]
		for row_index, row in enumerate(self.board):
			for col_index, item in enumerate(row):
				if col_index % 2 == 0:
					self.board[row_index][col_index] = "|"

	def printer(self):
		if self.gameover == True:
			print("\nThe final board state:")
		else:
			print("\nTurn {turn}.".format(turn=self.turn))
		print("\n  1   2   3   4   5   6   7")
		for row in self.board:
			for item in row:
				print(item, end = " ")
			print()
	def available_moves(self):
		moves = []
		for i in range(1, 14, 2):
			if self.board[0][i] == " ":
				moves.append(i)
		return moves

	def inputter(self, col_index):
		self.turn += 1
		self.evanorodd += 1
		num = col_index * 2 - 1
		if num >=1 and num <= 13 and num % 2 != 0:
			if self.board[0][num] == " ":
				for i in range(5, -1, -1):
					if self.board[i][num] == " ":
						if self.evanorodd % 2 != 0:
							self.board[i][num] = "X"
							break
						else:
							self.board[i][num] = "O"
							break
			else:
				self.evanorodd -= 1
				print("\nI'm afraid that column is full. Choose another one.")
		else:
			self.evanorodd -= 1
			print("\nYou need to give a column number from one to seven.")
		
	def aiinputter(self, col_index):
		self.turn += 1
		self.evanorodd += 1
		for i in range(5, -1, -1):
			if self.board[i][col_index] == " ":
				if self.evanorodd % 2 != 0:
					self.board[i][col_index] = "X"
					break
				else:
					self.board[i][col_index] = "O"
					break
	def checker(self):
		# checks vertical
		for row in range(5, 2, -1):
			for column in range(1, 14, 2):
				if self.board[row][column] == self.board[row-1][column] and self.board[row][column] == self.board[row-2][column] and self.board[row][column] == self.board[row-3][column]:
					if self.board[row][column] == "X":
						print("\nThe game is over! Crosses win with a vertical connect four!")
						self.gameover = True
						self.xwin = 1
						return
					elif self.board[row][column] == "O":
						print("\nThe game is over! Naughts win with a vertical connect four!")
						self.gameover = True
						self.owin = -1
						return
		# checks horizontal
		for row in range(5, -1, -1):
			for column in range(1, 8, 2):
				if self.board[row][column] == self.board[row][column+2] and self.board[row][column] == self.board[row][column+4] and self.board[row][column] == self.board[row][column+6]:
					if self.board[row][column] == "X":
						print("\nThe game is over! Crosses win with a horizontal connect four!")
						self.gameover = True
						self.xwin = 1
						return
					elif self.board[row][column] == "O":
						print("\nThe game is over! Naughts win with a horizontal connect four!")
						self.gameover = True
						self.owin = -1
						return
		# checks diagonal going from left to right
		for row in range(5, 2, -1):
			for column in range(1, 8, 2):
				if self.board[row][column] == self.board[row-1][column+2] and self.board[row][column] == self.board[row-2][column+4] and self.board[row][column] == self.board[row-3][column+6]:
					if self.board[row][column] == "X":
						print("\nThe game is over! Crosses win along a positive diagonal!")
						self.gameover = True
						self.xwin = 1
						return
					elif self.board[row][column] == "O":
						print("\nThe game is over! Naughts win along a positive diagonal!")
						self.gameover = True
						self.owin = -1
						return
		# checks diagonal going from right to left
		for row in range(5, 2, -1):
			for column in range(13, 6, -2):
				if self.board[row][column] == self.board[row-1][column-2] and self.board[row][column] == self.board[row-2][column-4] and self.board[row][column] == self.board[row-3][column-6]:
					if self.board[row][column] == "X":
						print("\nThe game is over! Crosses win along a negative diagonal!")
						self.gameover = True
						self.xwin = 1
						return
					elif self.board[row][column] == "O":
						print("\nThe game is over! Naughts win along a negative diagonal!")
						self.gameover = True
						self.owin = -1
						return
		#checks if everywhere is full
		spaces_left = sum(row.count(" ") for row in self.board)
		if spaces_left == 0 and self.xwin != 1 and self.owin != -1:
			self.draw = True
			self.gameover = True

play = ConnectFour()		

def minimax(theclass, is_maximizing, depth, alpha, beta):
	theclass.connected_four()
	if theclass.gameover == True:
		if theclass.xwin == 1:
			return [(10000000 - theclass.turn), ""]
		elif theclass.owin == -1:
			return [(-10000000 + theclass.turn), ""]
	elif theclass.draw == True:
		return [0, ""]
	elif depth == 0:
		return [0, ""]
	if is_maximizing == True:
		best_value = -float("Inf")
		moves = theclass.available_moves()
		centredmoves = []
		if 4 in moves:
			centredmoves.append(4)
		if 3 in moves:
			centredmoves.append(3)
		if 6 in moves:
			centredmoves.append(6)
		if 2 in moves:
			centredmoves.append(2)
		if 5 in moves:
			centredmoves.append(5)
		if 1 in moves:
			centredmoves.append(1)
		if 7 in moves:
			centredmoves.append(7)
		best_move = centredmoves[0]	
		for move in centredmoves:
			copied = copy.deepcopy(theclass)
			copied.make_move(move-1)
			hypothetical_value = minimax(copied, False, depth - 1, alpha, beta)[0]
			if hypothetical_value > best_value:
				best_value = hypothetical_value
				best_move = move
			alpha = max(alpha, best_value)
			if alpha >= beta:
				break
		return [best_value, best_move]
	elif is_maximizing == False:
		best_value = float("Inf")
		moves = theclass.available_moves()
		centredmoves = []
		if 4 in moves:
			centredmoves.append(4)
		if 3 in moves:
			centredmoves.append(3)
		if 6 in moves:
			centredmoves.append(6)
		if 2 in moves:
			centredmoves.append(2)
		if 5 in moves:
			centredmoves.append(5)
		if 1 in moves:
			centredmoves.append(1)
		if 7 in moves:
			centredmoves.append(7)
		best_move = centredmoves[0]
		for move in centredmoves:
			copied = copy.deepcopy(theclass)
			copied.make_move(move-1)
			hypothetical_value = minimax(copied, True, depth -1, alpha, beta)[0]
			if hypothetical_value < best_value:
				best_value = hypothetical_value
				best_move = move
			beta = min(beta, best_move)
			if alpha >= beta:
				break
		return [best_value, best_move] 

	

twoai = input("Want to watch a game played by two AIs? Y or N?: ")

if twoai.lower() == "y":
	while play.evanorodd < 43:
		play.printer()
		if play.evanorodd % 2 == 0:
			bitted = Bitboard(play.board)
			bitted.get_position_and_mask()
			aimove = minimax(bitted, True, 6, -float("Inf"), float("Inf"))[1]
			play.inputter(aimove)
			print("\nNew AI with depth 6 dropped a piece in column {column}.".format(column=aimove))
			play.checker()
			if play.gameover == True and play.draw != True:
				play.printer()
				break
			elif play.draw == True:
				print("\nThe game is drawn!")
				play.printer()
				break	
		elif play.evanorodd % 2 != 0:
			bitted = Bitboard(play.board)
			bitted.get_position_and_mask()
			aimove = minimax(bitted, False, 6, -float("Inf"), float("Inf"))[1]
			play.inputter(aimove)
			print("\nNew AI with depth 6 dropped a piece in column {column}.".format(column=aimove))
			play.checker()
			if play.gameover == True and play.draw != True:
				play.printer()
				break
			elif play.draw == True:
				print("\nThe game is drawn!")
				play.printer()
				break

One thing you could do is to test your recursive function on models and see if it works as expected. Have expressive f-string statements that highlight the shifting boundaries.

2 Likes