I am trying to implement Connect 4 game using Min-Max as utility to find best possible move.<br><br>
The game is played on a 6x7 grid, with six rows and seven columns. . The two players take turns placing pieces on the board: the red player can only place red pieces, and the green player can only place green pieces.
It is best to think of the board as standing upright. We will assign a number to every row and column, as follows: columns are numbered from left to right, with numbers 1, 2, ..., 7. Rows are numbered from bottom to top, with numbers 1, 2, ..., 6. When a player makes a move, the move is completely determined by specifying the COLUMN where the piece will be placed. If all six positions in that column are occupied, then the move is invalid, and the program should reject it and force the player to make a valid move. In a valid move, once the column is specified, the piece is placed on that column and "falls down", until it reaches the lowest unoccupied position in that column.The game is over when all positions are occupied
The score, at the end of the game is determined as follows: consider each quadruple of four consecutive positions on board, either in the horizontal, vertical, or each of the two diagonal directions
The work done so far is where user provides a structured input file with some pieces already filled. The AI agent now has to figure out the best move.
Input file:
0000000
0000000
0200000
0100002
0200111
1100222
1where the game board size is 6 X 7 and the last digit at the end states the move of prayer.
Sample output I am getting is
MaxConnect-4 game
Game state before move:
-----------------
| 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 |
| 0 2 0 0 0 0 0 |
| 0 1 0 0 0 0 2 |
| 0 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
Score: Player 1 = 0, Player 2 = 0
0:->True
next 1
-----------------
| 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 |
| 0 2 0 0 0 0 0 |
| 0 1 0 0 0 0 2 |
| 1 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
0:->True
max
-----------------
| 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 |
| 0 2 0 0 0 0 0 |
| 2 1 0 0 0 0 2 |
| 1 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
0:->True
min
-----------------
| 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 |
| 1 2 0 0 0 0 0 |
| 2 1 0 0 0 0 2 |
| 1 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
0:->True
max
-----------------
| 0 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 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
0:->True
min
-----------------
| 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 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
min: 0 alpha: -9223372036854775808 beta: 9223372036854775807 V: 9223372036854775807
1:->True
min
-----------------
| 1 0 0 0 0 0 0 |
| 2 2 0 0 0 0 0 |
| 1 2 0 0 0 0 0 |
| 2 1 0 0 0 0 2 |
| 1 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
min: 0 alpha: -9223372036854775808 beta: 0 V: 0
2:->TrueBut the expected outcome of the last gameboard in sample output should be this
-----------------
| 0 0 0 0 0 0 0 |
| 2 1 0 0 0 0 0 |
| 1 2 0 0 0 0 0 |
| 2 1 0 0 0 0 2 |
| 1 2 0 0 1 1 1 |
| 1 1 0 0 2 2 2 |
-----------------
where 1 should move to next column
Final Answer of the implementation is where my implantation fills the whole board
-----------------
| 1 2 1 2 1 2 1 |
| 2 2 1 2 1 2 1 |
| 1 2 1 2 1 2 1 |
| 2 1 2 2 1 2 2 |
| 1 2 1 2 1 1 1 |
| 1 1 1 2 2 2 2 |
-----------------
but the expected outcome has to be
-----------------
| 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 |
| 0 2 0 0 0 0 0 |
| 0 1 0 0 0 0 2 |
| 0 2 0 0 1 1 1 |
| 1 1 0 1 2 2 2 |
-----------------
desired column 4 where the AI player should place the diceHere is the full source code implementation. If possible could you please point out the mistake I could not figure out what is the wrong..
AiPlayer.py
from GameBoard import *
import sys
class AiPlayer:
def __init__(self,depth):
self.depth = depth
self.maxInt = sys.maxsize
self.minInt = (-sys.maxsize -1)
'''
This method makes the decision to make a move for the computer using
the min and max value from the below given two functions.
param currentGame The GameBoard object that is currently being used to play the game.
return an integer indicating which column the AiPlayer would like to play in.'''
def getBestColumn(self, currentGame):
INVALID = 10
playChoice = INVALID;
if currentGame.getCurrentTurn() == 1 :
v = sys.maxint
for i in range(7):
if (currentGame.isValidPlay(i)):
nextMoveBoard = GameBoard(currentGame.getGameBoard())
nextMoveBoard.playPiece(i)
print("next 1");
nextMoveBoard.printGameBoard();
value = self.Calculate_Max_Utility(nextMoveBoard, self.depth, self.minInt, self.maxInt)
if (v > value) :
playChoice = i
v = value
else:
v = self.minInt
for i in range(7):
if (currentGame.isValidPlay(i)):
nextMoveBoard = GameBoard(currentGame.getGameBoard())
nextMoveBoard.playPiece(i);
print("next 2");
nextMoveBoard.printGameBoard();
value = self.Calculate_Min_Utility(nextMoveBoard, self.depth, self.minInt, self.maxInt);
if (v < value):
playChoice = i;
v = value;
return playChoice;
'''
This method calculates the min value.
param gameBoard The GameBoard object that is currently being used to play the game.
param depth_level depth to which computer will search for making best possible next move
param alpha_value maximum utility value for MAX player
param beta_value maximum utility value for MIN player
return an integer indicating which column the AiPlayer would like to play in.
'''
def Calculate_Min_Utility(self,gameBoard, depth_level, alpha_value, beta_value):
if (not gameBoard.isBoardFull() and depth_level > 0) :
v = self.maxInt;
for i in range(7):
if (gameBoard.isValidPlay(i)) :
board4NextMove = GameBoard(gameBoard.getGameBoard());
board4NextMove.playPiece(i);
print("min");
board4NextMove.printGameBoard();
value = self.Calculate_Max_Utility(board4NextMove, depth_level - 1, alpha_value, beta_value);
print("min: "+str(value)+" alpha: "+str(alpha_value)+" beta: "+str(beta_value)+" V: "+str(v))
if (v > value) :
v = value;
if (v <= alpha_value) :
return v
if (beta_value > v) :
beta_value = v
return v
else :
gameBoard.countScore()
return gameBoard.player2Score - gameBoard.player1Score;
'''This method calculates the max value.
param gameBoard The GameBoard object that is currently being used to play the game.
param depth_level depth to which computer will search for making best possible next move
param alpha_value maximum utility value for MAX player
param beta_value maximum utility value for MIN player
return an integer indicating which column the AiPlayer would like to play in. '''
def Calculate_Max_Utility(self, gameBoard, depth_level, alpha_value, beta_value):
if (not gameBoard.isBoardFull() and depth_level > 0) :
v = self.minInt;
for i in range(7):
if (gameBoard.isValidPlay(i)) :
board4NextMove = GameBoard(gameBoard.getGameBoard())
board4NextMove.playPiece(i)
print("max");
board4NextMove.printGameBoard();
value = self.Calculate_Min_Utility(board4NextMove, int(depth_level) - 1, alpha_value, beta_value)
print("min: "+str(value)+" alpha: "+str(alpha_value)+" beta: "+str(beta_value)+" V: "+str(v))
if (v < value) :
v = value
if (v >= beta_value) :
return v
if (alpha_value < v) :
alpha_value = v
return v;
else:
gameBoard.countScore()
return gameBoard.player2Score - gameBoard.player1Score;GameBoard.py
import sys
class GameBoard:
def __init__(self,gameBoard, currentTurn=1):
self.gameBoard = gameBoard
self.pieceCount = 0
self.currentTurn = currentTurn
self.player1Score = 0
self.player2Score = 0
@classmethod
def readFromFile(cls,inFile):
# Try to open the input file
try:
gameFile = open(inFile, 'r')
except IOError:
sys.exit("\nError opening input file.\nCheck file name.\n")
file_lines = gameFile.readlines()
gameBoard = [[int(char) for char in line[0:7]] for line in file_lines[0:-1]]
currentTurn = int(file_lines[-1][0])
gameFile.close()
return cls(gameBoard,currentTurn)
def getCurrentTurn(self):
return (self.pieceCount % 2) + 1;
def checkPieceCount(self):
self.pieceCount = sum(1 for row in self.gameBoard for piece in row if piece)
def getGameBoard(self):
return self.gameBoard;
def isValidPlay(self, column):
if (not(column >= 0 and column < 7)) :
# check the column bounds
return False
elif self.gameBoard[0][column] > 0 :
# check if column is full
return False
else :
# column is NOT full and the column is within bounds
return True
# Count the number of pieces already played
def isBoardFull(self):
self.checkPieceCount()
return self.pieceCount == 42
# Place the current player's piece in the requested column
def playPiece(self, column):
print(str(column)+':->'+str(self.isValidPlay(column)))
if not self.isValidPlay(column):
return 0
else:
for i in range(5, -1, -1):
if not self.gameBoard[i][column]:
self.checkPieceCount()
self.gameBoard[i][column] = self.getCurrentTurn()
self.pieceCount += 1
return 1
def printGameBoard(self):
print( ' -----------------')
for i in range(6):
print (' |'),
for j in range(7):
print('%d' % self.gameBoard[i][j]),
print ('| ')
print (' -----------------')
# Output current game status to file
def printGameBoardToFile(self,outFile):
try:
gameFile = open(outFile, 'w')
for row in self.gameBoard:
gameFile.write(''.join(str(col) for col in row) + '\r\n')
gameFile.write('%s\r\n' % str(self.currentTurn))
gameFile.close()
except:
sys.exit('Error opening output file.')
# Calculate the number of 4-in-a-row each player has
def countScore(self):
self.player1Score = 0;
self.player2Score = 0;
# Check horizontally
for row in self.gameBoard:
# Check player 1
if row[0:4] == [1]*4:
self.player1Score += 1
if row[1:5] == [1]*4:
self.player1Score += 1
if row[2:6] == [1]*4:
self.player1Score += 1
if row[3:7] == [1]*4:
self.player1Score += 1
# Check player 2
if row[0:4] == [2]*4:
self.player2Score += 1
if row[1:5] == [2]*4:
self.player2Score += 1
if row[2:6] == [2]*4:
self.player2Score += 1
if row[3:7] == [2]*4:
self.player2Score += 1
# Check vertically
for j in range(7):
# Check player 1
if (self.gameBoard[0][j] == 1 and self.gameBoard[1][j] == 1 and
self.gameBoard[2][j] == 1 and self.gameBoard[3][j] == 1):
self.player1Score += 1
if (self.gameBoard[1][j] == 1 and self.gameBoard[2][j] == 1 and
self.gameBoard[3][j] == 1 and self.gameBoard[4][j] == 1):
self.player1Score += 1
if (self.gameBoard[2][j] == 1 and self.gameBoard[3][j] == 1 and
self.gameBoard[4][j] == 1 and self.gameBoard[5][j] == 1):
self.player1Score += 1
# Check player 2
if (self.gameBoard[0][j] == 2 and self.gameBoard[1][j] == 2 and
self.gameBoard[2][j] == 2 and self.gameBoard[3][j] == 2):
self.player2Score += 1
if (self.gameBoard[1][j] == 2 and self.gameBoard[2][j] == 2 and
self.gameBoard[3][j] == 2 and self.gameBoard[4][j] == 2):
self.player2Score += 1
if (self.gameBoard[2][j] == 2 and self.gameBoard[3][j] == 2 and
self.gameBoard[4][j] == 2 and self.gameBoard[5][j] == 2):
self.player2Score += 1
# Check diagonally
# Check player 1
if (self.gameBoard[2][0] == 1 and self.gameBoard[3][1] == 1 and
self.gameBoard[4][2] == 1 and self.gameBoard[5][3] == 1):
self.player1Score += 1
if (self.gameBoard[1][0] == 1 and self.gameBoard[2][1] == 1 and
self.gameBoard[3][2] == 1 and self.gameBoard[4][3] == 1):
self.player1Score += 1
if (self.gameBoard[2][1] == 1 and self.gameBoard[3][2] == 1 and
self.gameBoard[4][3] == 1 and self.gameBoard[5][4] == 1):
self.player1Score += 1
if (self.gameBoard[0][0] == 1 and self.gameBoard[1][1] == 1 and
self.gameBoard[2][2] == 1 and self.gameBoard[3][3] == 1):
self.player1Score += 1
if (self.gameBoard[1][1] == 1 and self.gameBoard[2][2] == 1 and
self.gameBoard[3][3] == 1 and self.gameBoard[4][4] == 1):
self.player1Score += 1
if (self.gameBoard[2][2] == 1 and self.gameBoard[3][3] == 1 and
self.gameBoard[4][4] == 1 and self.gameBoard[5][5] == 1):
self.player1Score += 1
if (self.gameBoard[0][1] == 1 and self.gameBoard[1][2] == 1 and
self.gameBoard[2][3] == 1 and self.gameBoard[3][4] == 1):
self.player1Score += 1
if (self.gameBoard[1][2] == 1 and self.gameBoard[2][3] == 1 and
self.gameBoard[3][4] == 1 and self.gameBoard[4][5] == 1):
self.player1Score += 1
if (self.gameBoard[2][3] == 1 and self.gameBoard[3][4] == 1 and
self.gameBoard[4][5] == 1 and self.gameBoard[5][6] == 1):
self.player1Score += 1
if (self.gameBoard[0][2] == 1 and self.gameBoard[1][3] == 1 and
self.gameBoard[2][4] == 1 and self.gameBoard[3][5] == 1):
self.player1Score += 1
if (self.gameBoard[1][3] == 1 and self.gameBoard[2][4] == 1 and
self.gameBoard[3][5] == 1 and self.gameBoard[4][6] == 1):
self.player1Score += 1
if (self.gameBoard[0][3] == 1 and self.gameBoard[1][4] == 1 and
self.gameBoard[2][5] == 1 and self.gameBoard[3][6] == 1):
self.player1Score += 1
if (self.gameBoard[0][3] == 1 and self.gameBoard[1][2] == 1 and
self.gameBoard[2][1] == 1 and self.gameBoard[3][0] == 1):
self.player1Score += 1
if (self.gameBoard[0][4] == 1 and self.gameBoard[1][3] == 1 and
self.gameBoard[2][2] == 1 and self.gameBoard[3][1] == 1):
self.player1Score += 1
if (self.gameBoard[1][3] == 1 and self.gameBoard[2][2] == 1 and
self.gameBoard[3][1] == 1 and self.gameBoard[4][0] == 1):
self.player1Score += 1
if (self.gameBoard[0][5] == 1 and self.gameBoard[1][4] == 1 and
self.gameBoard[2][3] == 1 and self.gameBoard[3][2] == 1):
self.player1Score += 1
if (self.gameBoard[1][4] == 1 and self.gameBoard[2][3] == 1 and
self.gameBoard[3][2] == 1 and self.gameBoard[4][1] == 1):
self.player1Score += 1
if (self.gameBoard[2][3] == 1 and self.gameBoard[3][2] == 1 and
self.gameBoard[4][1] == 1 and self.gameBoard[5][0] == 1):
self.player1Score += 1
if (self.gameBoard[0][6] == 1 and self.gameBoard[1][5] == 1 and
self.gameBoard[2][4] == 1 and self.gameBoard[3][3] == 1):
self.player1Score += 1
if (self.gameBoard[1][5] == 1 and self.gameBoard[2][4] == 1 and
self.gameBoard[3][3] == 1 and self.gameBoard[4][2] == 1):
self.player1Score += 1
if (self.gameBoard[2][4] == 1 and self.gameBoard[3][3] == 1 and
self.gameBoard[4][2] == 1 and self.gameBoard[5][1] == 1):
self.player1Score += 1
if (self.gameBoard[1][6] == 1 and self.gameBoard[2][5] == 1 and
self.gameBoard[3][4] == 1 and self.gameBoard[4][3] == 1):
self.player1Score += 1
if (self.gameBoard[2][5] == 1 and self.gameBoard[3][4] == 1 and
self.gameBoard[4][3] == 1 and self.gameBoard[5][2] == 1):
self.player1Score += 1
if (self.gameBoard[2][6] == 1 and self.gameBoard[3][5] == 1 and
self.gameBoard[4][4] == 1 and self.gameBoard[5][3] == 1):
self.player1Score += 1
# Check player 2
if (self.gameBoard[2][0] == 2 and self.gameBoard[3][1] == 2 and
self.gameBoard[4][2] == 2 and self.gameBoard[5][3] == 2):
self.player2Score += 1
if (self.gameBoard[1][0] == 2 and self.gameBoard[2][1] == 2 and
self.gameBoard[3][2] == 2 and self.gameBoard[4][3] == 2):
self.player2Score += 1
if (self.gameBoard[2][1] == 2 and self.gameBoard[3][2] == 2 and
self.gameBoard[4][3] == 2 and self.gameBoard[5][4] == 2):
self.player2Score += 1
if (self.gameBoard[0][0] == 2 and self.gameBoard[1][1] == 2 and
self.gameBoard[2][2] == 2 and self.gameBoard[3][3] == 2):
self.player2Score += 1
if (self.gameBoard[1][1] == 2 and self.gameBoard[2][2] == 2 and
self.gameBoard[3][3] == 2 and self.gameBoard[4][4] == 2):
self.player2Score += 1
if (self.gameBoard[2][2] == 2 and self.gameBoard[3][3] == 2 and
self.gameBoard[4][4] == 2 and self.gameBoard[5][5] == 2):
self.player2Score += 1
if (self.gameBoard[0][1] == 2 and self.gameBoard[1][2] == 2 and
self.gameBoard[2][3] == 2 and self.gameBoard[3][4] == 2):
self.player2Score += 1
if (self.gameBoard[1][2] == 2 and self.gameBoard[2][3] == 2 and
self.gameBoard[3][4] == 2 and self.gameBoard[4][5] == 2):
self.player2Score += 1
if (self.gameBoard[2][3] == 2 and self.gameBoard[3][4] == 2 and
self.gameBoard[4][5] == 2 and self.gameBoard[5][6] == 2):
self.player2Score += 1
if (self.gameBoard[0][2] == 2 and self.gameBoard[1][3] == 2 and
self.gameBoard[2][4] == 2 and self.gameBoard[3][5] == 2):
self.player2Score += 1
if (self.gameBoard[1][3] == 2 and self.gameBoard[2][4] == 2 and
self.gameBoard[3][5] == 2 and self.gameBoard[4][6] == 2):
self.player2Score += 1
if (self.gameBoard[0][3] == 2 and self.gameBoard[1][4] == 2 and
self.gameBoard[2][5] == 2 and self.gameBoard[3][6] == 2):
self.player2Score += 1
if (self.gameBoard[0][3] == 2 and self.gameBoard[1][2] == 2 and
self.gameBoard[2][1] == 2 and self.gameBoard[3][0] == 2):
self.player2Score += 1
if (self.gameBoard[0][4] == 2 and self.gameBoard[1][3] == 2 and
self.gameBoard[2][2] == 2 and self.gameBoard[3][1] == 2):
self.player2Score += 1
if (self.gameBoard[1][3] == 2 and self.gameBoard[2][2] == 2 and
self.gameBoard[3][1] == 2 and self.gameBoard[4][0] == 2):
self.player2Score += 1
if (self.gameBoard[0][5] == 2 and self.gameBoard[1][4] == 2 and
self.gameBoard[2][3] == 2 and self.gameBoard[3][2] == 2):
self.player2Score += 1
if (self.gameBoard[1][4] == 2 and self.gameBoard[2][3] == 2 and
self.gameBoard[3][2] == 2 and self.gameBoard[4][1] == 2):
self.player2Score += 1
if (self.gameBoard[2][3] == 2 and self.gameBoard[3][2] == 2 and
self.gameBoard[4][1] == 2 and self.gameBoard[5][0] == 2):
self.player2Score += 1
if (self.gameBoard[0][6] == 2 and self.gameBoard[1][5] == 2 and
self.gameBoard[2][4] == 2 and self.gameBoard[3][3] == 2):
self.player2Score += 1
if (self.gameBoard[1][5] == 2 and self.gameBoard[2][4] == 2 and
self.gameBoard[3][3] == 2 and self.gameBoard[4][2] == 2):
self.player2Score += 1
if (self.gameBoard[2][4] == 2 and self.gameBoard[3][3] == 2 and
self.gameBoard[4][2] == 2 and self.gameBoard[5][1] == 2):
self.player2Score += 1
if (self.gameBoard[1][6] == 2 and self.gameBoard[2][5] == 2 and
self.gameBoard[3][4] == 2 and self.gameBoard[4][3] == 2):
self.player2Score += 1
if (self.gameBoard[2][5] == 2 and self.gameBoard[3][4] == 2 and
self.gameBoard[4][3] == 2 and self.gameBoard[5][2] == 2):
self.player2Score += 1
if (self.gameBoard[2][6] == 2 and self.gameBoard[3][5] == 2 and
self.gameBoard[4][4] == 2 and self.gameBoard[5][3] == 2):
self.player2Score += 1maxconnect4.py
import sys
from GameBoard import *
from AiPlayer import *
class MaxConnect4:
currentGame = None
aiPlayer = None
def __init__(self, argv):
self.argv = argv
argv.append('one-move');
argv.append('input2.txt');
argv.append('outputfile.txt');
argv.append('4');
def oneMoveGame(self,outFile):
global currentGame, aiPlayer
INVALID = 7
print ('\nMaxConnect-4 game\n')
print ('Game state before move:')
currentGame.printGameBoard()
# Update a few game variables based on initial state and print the score
currentGame.countScore()
print('Score: Player 1 = %d, Player 2 = %d\n' % (currentGame.player1Score, currentGame.player2Score))
if currentGame.isBoardFull():
print("\nI can't play.\nThe Board is Full\n\nGame Over.");
sys.exit(0)
column = aiPlayer.getBestColumn(currentGame)
if column == INVALID :
print("\nI can't play.\nThe Board is Full\n\nGame Over.");
return;
currentGame.playPiece(column) # Make a move (only random is implemented)
print( 'Game state after move:')
currentGame.printGameBoard()
currentGame.countScore()
print('Score: Player 1 = %d, Player 2 = %d\n' % (currentGame.player1Score, currentGame.player2Score))
currentGame.printGameBoardToFile(outFile)
def interactiveGame(currentGame):
# Fill me in
sys.exit('Interactive mode is currently not implemented')
def main(self):
# Make sure we have enough command-line arguments
global currentGame, aiPlayer
argv = self.argv
if len(argv) != 5:
print ('Four command-line arguments are needed:')
print('Usage: %s interactive [input_file] [computer-next/human-next] [depth]' % argv[0])
print('or: %s one-move [input_file] [output_file] [depth]' % argv[0])
sys.exit(2)
game_mode, inFile = argv[1:3]
depth = argv[4]
currentGame = GameBoard.readFromFile(inFile)
aiPlayer = AiPlayer(depth)
if not game_mode == 'interactive' and not game_mode == 'one-move':
print('%s is an unrecognized game mode' % game_mode)
sys.exit(2)
if game_mode == 'interactive':
interactiveGame(currentGame) # Be sure to pass whatever else you need from the command line
elif game_mode != 'one-move':
sys.exit("\n" + game_mode + " is an unrecognized game mode \n try again. \n")
else: # game_mode == 'one-move'
# Set up the output file
outFile = argv[3]
self.oneMoveGame(outFile) # Be sure to pass any other arguments from the command line you might need.
if __name__ == '__main__':
maxConnect4 = MaxConnect4(sys.argv)
maxConnect4.main()