Question

Question 3: A smaller version of Connect 4 is played on a vertical board 3-row high and 3-column wide. The two players Maxim and Minnie alternately drop a black and white disc, respectively, from the top of any column, and it will fall to the lowest open row. A player wins when three of his/her discs are aligned either horizontally, vertically, or diagonally; otherwise the game is a draw. Consider the sample game below, where the first four moves have already been played. 2 3 4 (a) The game tree below shows all possible moves after Maxim dropped his next disc (X) in the right-most column. Apply the Minimax algorithm, marking the value of each node as 1 if Maxim wins, -1 if Minnie wins, and 0 if they draw. Indicate accordingly the expected result of the game. Show which outcomes are possible, should a mistake occur. (3 marks) Minnie 0 X O Maxim X O XO X MinnieXO XO X 0 O Minnie Maxim X O X O XO X MinnieXO XO X 0 O X X O Maxim X O X XO X XO X XO X X X O X O X MinnieXO O XOX (b) Highlight on the game tree in part (a) the nodes that will not be evaluated if using alpha-beta pruning. Assume nodes are generated in the left-to-right order. Comment on the improvement, if any. (2 marks) (c) Suppose Maxim dropped his next disc in the centre column, instead of the right-most column as in parts (a-b). Draw the 10-node portion of the game tree below that starts with that move. Apply the Minimax algorithm, clearly marking the node values, and comment on the result. (2 marks) (c) Suppose Maxim dropped his next disc in the centre column, instead of the right-most column as in parts (a-b). Draw the 10-node portion of the game tree below that starts with that move. Apply the Minimax algorithm, clearly marking the node values, and comment on the result. (2 marks) Minnie x X

Answer 1

package Game;

// Class Connect4Logic definition

public class Connect4Logic

{

// Instance variables to store logical data

private int cellsLeft = 0;

private int maximum;

private int rowSize;

private int colSize;

Connect4Grid myGrid;

// Parameterized constructor

public Connect4Logic(Connect4Grid tempGrid)

{

maximum = 4;

myGrid = tempGrid;

// Dynamically allocates memory

cellsLeft = myGrid.getCellsLeft();

rowSize = myGrid.getRowSize();

colSize = myGrid.getColSize();

}// End of method

// Method to set the found coordinate to current player

public boolean setAndCheck(int row, int col, int player)

{

myGrid.set_matrix(row, col, player);

cellsLeft--;

return checkOne(row, col, 0, 1, player) || checkOne(row, col, -1, 1, player)

|| checkOne(row, col, -1, 0, player) || checkOne(row, col, 1, 1, player);

}// End of method

// Method to check for draw game

public boolean draw_game()

{

return cellsLeft == 0;

}// End of method

// Method to check the player position

private boolean checkOne(int row, int col, int diagonalR, int diagonalC, int player)

{

int counter = 0;

int tempX = row;

int tempY = col;

// Loops till counter value is less than maximum'

// and tempX and tempY positions are valid

while (counter < maximum && valid(tempX, tempY))

{

if (!myGrid.matrix_equals(tempX, tempY, player))

{

break;

}// End of if condition

tempX += diagonalR;

tempY += diagonalC;

counter++;

}// End of while loop

tempX = row - diagonalR;

tempY = col - diagonalC;

  

// Loops till counter value is less than maximum'

// and tempX and tempY positions are valid

while (counter < maximum && valid(tempX, tempY))

{

if (!myGrid.matrix_equals(tempX, tempY, player))

{

break;

}// End of if condition

tempX -= diagonalR;

tempY -= diagonalC;

counter++;

}// End of while loop

  

// Returns true if counter value is equals to maximum

// otherwise returns false

return counter == maximum;

}// End of method

// Method to check valid position

private boolean valid(int row, int col)

{

// returns if the bounds are set to be > 0 only then

// first row and column does not work

return row >= 0 && row < rowSize && col >= 0 && col < colSize;

}// End of method

}// End of class

--------------------------------------------------------------------------------------------------------------------------

package Game;

// Class Connect4Grid definition

public class Connect4Grid

{

// Instance variable to store matrix information

private int rowSize;

private int colSize;

private int[][] boardMatrix;

private int cellsLeft = 0;

// Default constructor

public Connect4Grid()

{

// Sets the row and column size

rowSize = 7;

colSize = 6;

// Dynamically allocate memory

boardMatrix = new int[rowSize][colSize];

  

// Loops till number of rows

for (int r = 0; r < rowSize; r++)

{

// Loops till number of columns

for (int c = 0; c < colSize; c++)

{

// Initializes each position

boardMatrix[r][c] = 0;

cellsLeft++;

}// End of inner for loop

}// End of outer for loop

}// End of method

  

// Methods to return cell left

public int getCellsLeft()

{

return cellsLeft;

}// End of method

// Method to return matrix

public int[][] getMatrix()

{

return boardMatrix;

}// End of method

// Method to return if matrix pos1 and pos2 index position contains player number

// Otherwise false

public boolean matrix_equals(int pos1, int pos2, int player)

{

return boardMatrix [pos1][pos2] == player;

}// End of method

// Method to set the player at pos1 and po2 index position of matrix

public void set_matrix(int pos1, int pos2, int player)

{

// Assigns player number at pos1 and po2 index position of the matrix

boardMatrix[pos1][pos2] = player;

}// End of method

// Method to returns the row size

public int getRowSize()

{

return rowSize;

}// End of method

  

// Method to return the column Size

public int getColSize()

{

return colSize;

}// End of method

//Method to checks for room in column and returns free position

public int find_y(int row)

{

int position = -1;

// Loops till end of the column

for (int col = 0; col < colSize; col++)

{

// Checks if the matrix r and c position is having zero i.e., free

if (boardMatrix[row][col] == 0)

{

// Assigns column counter value as free position

position = col;

}// End of if condition

}// End of for loop

// Returns the free position

return position;

}// End of method

// Method to change player and returns the player number

public int changeplayer(int player, int maximumPlayers)

{

// Increase the player counter by one

player++;

// Checks if the player counter is greater than maximum player

// then return 1

if (player > maximumPlayers)

{

return 1;

}// End of if condition

// Returns player number

return player;

}// End of method

}// End of class

--------------------------------------------------------------------------------------------------------------------------

package Game;

import javax.swing.*;

import javax.swing.border.*;

import java.awt.*;

import java.awt.event.*;

// Class Connect4GUI definition

public class Connect4GUI

{

// Declares component and container objects

private JFrame myFrame;

private JLabel[][] slotsL;

private JButton[] buttonsB;

  

// Instance variables to store the grid size

private int rowSize = 7;

private int colSize = 6;

private int currentPlayer = 1;

  

// Instance variables to store game status

private boolean hasWon = false;

private boolean hasDraw = false;

private boolean quit = false;

private boolean newGame = false;

  

// Creates Grid and Logic class object

Connect4Grid myGrid = new Connect4Grid();

// For the logic applied in the game

Connect4Logic myLogic = new Connect4Logic(myGrid);

  

// Default constructor

public Connect4GUI()

{

// Instantiate objects

myFrame = new JFrame("connect four");

JPanel panel = (JPanel) myFrame.getContentPane();

panel.setLayout(new GridLayout(rowSize, colSize + 1));

slotsL = new JLabel[rowSize][colSize];

buttonsB = new JButton[rowSize];

// Loops 7 times for row

for (int c = 0; c < rowSize; c++)

{

// Create buttons

buttonsB[c] = new JButton("" + (c + 1));

buttonsB[c].setActionCommand("" + c);

// Register action listener to each button

buttonsB[c].addActionListener(new ActionListener()

{

// Overrides the method of ActionListener

public void actionPerformed(ActionEvent e)

{

int command = Integer.parseInt(e.getActionCommand());

// Calls the method to check space in column

int isSpace = myGrid.find_y(command);

// Checks if the method return value is not -1

if (isSpace != -1)

{

// Sets a place to current player

if (myLogic.setAndCheck(command, isSpace, currentPlayer))

hasWon = true;

// Otherwise calls the method to check for game draw

else if (myLogic.draw_game())

hasDraw = true;

// Otherwise

else

{

// Calls the method to change player

currentPlayer = myGrid.changeplayer(currentPlayer, 2);

myFrame.setTitle("Connect four - player " +

currentPlayer + "'s turn");

}// End of else

}// End of if condition

// Otherwise displays error message

else

JOptionPane.showMessageDialog(null, "Choose another one",

"Column is filled", JOptionPane.INFORMATION_MESSAGE);

}

});// End of anonymous class

// Adds the button to panel

panel.add(buttonsB[c]);

}// End of for loop

  

// Loops 6 times for column

for (int column = 0; column < colSize; column++)

{

// Loops 7 times for row

for (int row = 0; row < rowSize; row++)

{

// Assigns panels to matrix sloat's row and column index position

slotsL[row][column] = new JLabel();

slotsL[row][column].setHorizontalAlignment(SwingConstants.CENTER);

slotsL[row][column].setBorder(new LineBorder(Color.black));

// Adds the sloat's panes to main panel

panel.add(slotsL[row][column]);

}// End of inner for loop

}// End of outer for loop

// Sets the frame properties

myFrame.setContentPane(panel);

myFrame.setSize(700, 600);

myFrame.setVisible(true);

myFrame.setLocationRelativeTo(null);

myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

}// End of constructor

// Method to update the board after each move

public void updateBoard()

{

// Loops 7 times for row

for (int row = 0; row < rowSize; row++)

{

// Loops 6 times for column

for (int column = 0; column < colSize; column++)

{

// Calls the method to check if player 1

if (myGrid.matrix_equals(row, column, 1))

{

// Set it to true for selected

slotsL[row][column].setOpaque(true);

// Sets the background color to red

slotsL[row][column].setBackground(Color.red);

}// End of if condition

// Calls the method to check if player 2

if (myGrid.matrix_equals(row, column, 2))

{

slotsL[row][column].setOpaque(true);

slotsL[row][column].setBackground(Color.blue);

}// End of if condition

}// End of inner for loop

}// End of outer for loop

}// End of method

// Method to show winning status

public void showWon()

{

String winner = "player " + currentPlayer + " wins";

// Asks the user for new game

int conformation = JOptionPane.showConfirmDialog(myFrame, "new game?",

winner, JOptionPane.YES_NO_OPTION);

// Checks if yes button is clicked

if (conformation < 1)

{

// Clears the frame for the next game

myFrame.dispose();

// Set the new game status to true

newGame = true;

}// End of if condition

// Otherwise no button clicked

else

{

// Clears the frame

myFrame.dispose();

// Sets the quit status to true to exit

quit = true;

}// End of else

}// End of method

// Method for game draw

public void showDraw()

{

String winner = "draw game";

// Asks the user for new game

int conformation = JOptionPane.showConfirmDialog(myFrame, "new game?",

winner, JOptionPane.YES_NO_OPTION);

// Checks if yes button is clicked

if (conformation < 1)

{

// Clears the frame for the next game

myFrame.dispose();

// Set the new game status to true

newGame = true;

}// End of if condition

// Otherwise no button clicked

else

{

// Clears the frame

myFrame.dispose();

// Sets the quit status to true to exit

quit = true;

}// End of else

}// End of method

// Method to return true if own otherwise false

public boolean getHasWon()

{

return hasWon;

}// End of method

  

// Method to return true if draw otherwise false

public boolean getHasDraw()

{

return hasDraw;

}// End of method

// Method to return quit status

public boolean getQuit()

{

return quit;

}// End of method

// Method to return new game status

public boolean getNewGame()

{

return newGame;

}// End of method

// main method definition

public static void main(String[] args)

{

// Creates an object of the Connect4GUI class

Connect4GUI gui = new Connect4GUI();

}// End of main method

}// End of class

--------------------------------------------------------------------------------------------------------------------------

package Game;

// Class Connect4Driver definition

public class Connect4Driver

{

// main method definition

public static void main(String[] args)

{

int status = 0;

Connect4GUI Gui = new Connect4GUI();

// Checks if program is in quitting status

while (status != -1)

{

switch (status)

{

case 0:

Gui.updateBoard();

if (Gui.getHasWon())

status = 1;

else if (Gui.getHasDraw())

status = 2;

else if (Gui.getNewGame())

{

Gui = new Connect4GUI();

status = 0;

}// End of else if

break;

// End game with winner

case 1:

Gui.showWon();

if (Gui.getQuit())

status = -1;

else if (Gui.getNewGame())

{

Gui = new Connect4GUI();

status = 0;

}// End of else if

break;

// End game with draw game

case 2:

Gui.showDraw();

if (Gui.getQuit())

status = -1;

else if (Gui.getNewGame())

{

Gui = new Connect4GUI();

status = 0;

}// End of else if

break;

}// End of switch - case

}// End of while loop

}// End of main method

}// End of class

Sample Output:

× Connect four-player ...- × connect four Connect four-player ...- XConnect four- player 4 1 2 3 45 67 一口 × Connect four-player 4 4 player 2 wins new game? Yes N