""" Created by: Brandon Schmidt Last modified: 10/29/25 """ # This is the game class. It allows the user to play against the Engine. class Game: def __init__(self): self.board = Bitboard() self.moves = Moves() self.evaluation = Evaluation() self.engine = Engine() self.lookup = {"R":0b1, "Y":0b0} def play(self): print("------------------------------------------------------------------") print("Welcome to Connect-4, play your piece into the appropriate column!") print("------------------------------------------------------------------") print() self.printBoard() print() while True: try: player = self.lookup[input("I want to play as (R, Y): ").upper()] print() break except: print("Enter a valid choice to play.") while True: if (self.evaluation.wins(self.board) or self.moves.get(self.board)==[]): break if player==self.board.move: while True: try: move = int(input("Your move: "))-1 break except: print("Enter a valid choice to play.") print() if move>=0 and move<9: if self.board.colMap[move]>=6: print("Sorry, that column is full.") else: if self.board.move: self.board.moveR(move) else: self.board.moveY(move) else: self.engine.findBest(self.board) if self.board.move: self.board.moveR(self.engine.bestMove) else: self.board.moveY(self.engine.bestMove) self.printBoard() if (self.evaluation.winCheck(self.board.R)): if player: print("You win!") else: print("You lose.") elif (self.evaluation.winCheck(self.board.Y)): if player: print("You lose.") else: print("You win!") else: print("Draw, well played.") def printBoard(self): p1 = self.board.R p2 = self.board.Y rows = 6 cols = 7 for r in reversed(range(rows)): line = [] for c in range(cols): bit_index = r * cols + c mask = 1 << bit_index if p1 & mask: line.append("R") elif p2 & mask: line.append("Y") else: line.append(".") print(" ".join(line)) print("-------------") print("1|2|3|4|5|6|7") print() """ This is the Engine class, it incorporates the Search class to find the best move in the position. It works similar to the Search class, but it returns a move instead of an evaluation. """ class Engine: def __init__(self): self.moves = Moves() self.search = Search(8) self.bestMove = None self.bestEval = 0 # Search every move in the position and saves the best move def findBest(self, bitboardObject): moveList = self.moves.get(bitboardObject) # Red to move, maximize score if bitboardObject.move: self.bestMove, self.bestEval = None, float('-inf') for move in moveList: # For every move, use search to find # the value of the resulting position bitboardObject.moveR(move) posEval = self.search.go(bitboardObject, 1) bitboardObject.undo() # Save the move if it is the best one if posEval > self.bestEval: self.bestMove, self.bestEval = move, posEval # Yellow to move, minimize score else: self.bestMove, self.bestEval = None, float('inf') for move in moveList: # For every move, use search to find # the value of the resulting position bitboardObject.moveY(move) posEval = self.search.go(bitboardObject, 1) bitboardObject.undo() # Save the move if it is the best one if posEval < self.bestEval: self.bestMove, self.bestEval = move, posEval """ This is the Search class, it creates a game tree and searches it to find the best path. """ class Search: # Creates a Moves and an Evaluation object to assist in # the search. It also takes a number as input, which is # the maximum search depth. def __init__(self, maxDepth): self.moves = Moves() self.evaluation = Evaluation() self.maxDepth = maxDepth # The main method of this class, which uses recursion to # search a game tree and find the best path forward. def go(self, bitboardObject, depth, alpha=float('-inf'), beta=float('inf')): # If the position has a win for red, return the maximum # evaluation minus the search depth if self.evaluation.winCheck(bitboardObject.R): return 0xFFFF - depth # If the position has a win for yellow, return the minimum # evaluation plus the search depth if self.evaluation.winCheck(bitboardObject.Y): return -0xFFFF + depth # If the depth is greater than the maximum depth, stop # searching and return a general position evaluation. if depth>self.maxDepth: return self.evaluation.get(bitboardObject) # If there are no moves, the game is a draw moves = self.moves.get(bitboardObject) if moves==[]: return 0 # Red to move, maximize the game evaluation if bitboardObject.move: maxEval = -0xFFFF for move in moves: bitboardObject.moveR(move) moveEval = self.go(bitboardObject, depth+1, alpha, beta) bitboardObject.undo() maxEval = max(maxEval, moveEval) alpha = max(alpha, maxEval) if alpha >= beta: break return maxEval # Yellow to move, minimize the game evaluation else: minEval = 0xFFFF for move in moves: bitboardObject.moveY(move) moveEval = self.go(bitboardObject, depth+1, alpha, beta) bitboardObject.undo() minEval = min(minEval, moveEval) beta = min(beta, minEval) if beta <= alpha: break return minEval """ This is the Evaluation class, it handles win checks as well as general position evaluations. """ class Evaluation: # Initializes a heatmap that gives each square a value. # This value is the number of wins possible using that square def __init__(self): self.lookup = ( 3, 4, 5, 7, 5, 4, 3, 4, 6, 8, 10, 8, 6, 4, 6, 8, 11, 13, 11, 8, 6, 6, 8, 11, 13, 11, 8, 6, 4, 6, 8, 10, 8, 6, 4, 3, 4, 5, 7, 5, 4, 3) # Returns true if the game state has a win def wins(self, bitboardObject): return self.winCheck(bitboardObject.R) or self.winCheck(bitboardObject.Y) # Shifts the board horizontally, vertically, and diagonally # to check for a win. bbnl and bbnr keep the method from # wrapping around to the next row and declaring a false win. def winCheck(self, bb): bbnl = bb&0b111111011111101111110111111011111101111110 bbnr = bb&0b011111101111110111111011111101111110111111 if bb & (bbnl >> 1) & (bbnl >> 2) & (bbnl >> 3): return True if bb & (bb >> 7) & (bb >> 14) & (bb >> 21): return True if bb & (bbnr >> 6) & (bbnr >> 12) & (bbnr >> 18): return True if bb & (bbnl >> 8) & (bbnl >> 16) & (bbnl >> 24): return True return False # Looks up every squares value and adds it to the score def scoreBitboard(self, bb): total = 0 while bb: lsb = bb & -bb total += self.lookup[lsb.bit_length() - 1] bb &= bb - 1 return total # Finds all of the potential wins in the position def getThreats(self, bb, occ): threats = 0 bbnl = bb&0b111111011111101111110111111011111101111110 bbnr = bb&0b011111101111110111111011111101111110111111 empty = (~occ) & 0x3FFFFFFFFFF threats |= empty & (bb << 7) & (bb << 14) & (bb << 21) threats |= (bbnl >> 3) & (bbnl >> 2) & (bbnl >> 1) & empty threats |= (bbnl >> 2) & (bbnl >> 1) & empty & (bbnr << 1) threats |= (bbnl >> 1) & empty & (bbnr << 1) & (bbnr << 2) threats |= empty & (bbnr << 1) & (bbnr << 2) & (bbnr << 3) threats |= (bbnr >> 18) & (bbnr >> 12) & (bbnr >> 6) & empty threats |= (bbnr >> 12) & (bbnr >> 6) & empty & (bbnl << 6) threats |= (bbnr >> 6) & empty & (bbnl << 6) & (bbnl << 12) threats |= empty & (bbnl << 6) & (bbnl << 12) & (bbnl << 18) threats |= (bbnl >> 24) & (bbnl >> 16) & (bbnl >> 8) & empty threats |= (bbnl >> 16) & (bbnl >> 8) & empty & (bbnr << 8) threats |= (bbnl >> 8) & empty & (bbnr << 8) & (bbnr << 16) threats |= empty & (bbnr << 8) & (bbnr << 16) & (bbnr << 24) return threats # Gives a board state a score based on likelihood winning. def get(self, bitboardObject): sumR = self.scoreBitboard(bitboardObject.R) sumY = self.scoreBitboard(bitboardObject.Y) occ = bitboardObject.R | bitboardObject.Y threatsR = self.getThreats(bitboardObject.R, occ) threatsY = self.getThreats(bitboardObject.Y, occ) sumR += threatsR.bit_count() * 20 sumY += threatsY.bit_count() * 20 return sumR - sumY """ This is the Moves class. It's method function "get" will return all of the possible moves for a given board. """ class Moves: # Simply finds all of the columns that aren't full # and returns a sorted list of those columns. def get(self, bitboardObject): moveList=[] bb = bitboardObject.R | bitboardObject.Y comb = bb & 0x7F comb &= (bb >> 7) & 0x7F comb &= (bb >> 14) & 0x7F comb &= (bb >> 21) & 0x7F comb &= (bb >> 28) & 0x7F comb &= (bb >> 35) & 0x7F bb = 0b1111111 & ~comb while bb: lsb = bb & -bb index = (lsb.bit_length() - 1) moveList.append(index) bb &= bb - 1 moveList.sort(key=lambda m: abs(m - 3)) return moveList """ This is the Bitboard class, it stores the board state and all of the current moves that have been made. It's method functions allow you to make and undo moves on the board. """ class Bitboard: def __init__(self): # Bitboard for the red pieces self.R = 0 # Bitboard for the yellow pieces self.Y = 0 # Player to move, where 0b1 represents # red and 0b0 represents yellow self.move = 0b1 # Storage of moves self.moveStack = [] # Keeps track of the column heights self.colMap = { 0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0} # Places a red piece into the specified column def moveR(self, column): self.moveStack.append(column) self.R |= 1 << (self.colMap[column]*7+column) self.colMap[column]+=1 self.move ^= 0b1 # Places a yellow piece into the specified column def moveY(self, column): self.moveStack.append(column) self.Y |= 1 << (self.colMap[column]*7+column) self.colMap[column]+=1 self.move ^= 0b1 # Undoes the last move def undo(self): column=self.moveStack.pop() self.move ^= 0b1 self.colMap[column]-=1 self.R &= ~(1 << (self.colMap[column]*7+column)) self.Y &= ~(1 << (self.colMap[column]*7+column)) game = Game() game.play()