Overview

work on a class to represent states in the game tic-tac-toe. Each state represents a single possible situation in the game, and could be used by a game tree to plan out all possible moves and select the best one.Today you will not build the tree, but will add functionality to the state which would allow the tree to be built, such as giving values for end-game states, generating a list of all possible moves from the current state, and doing or undoing moves on a state to generate a successor state.

Note: Once you have finished the code for this lab, you could use it along with GameTree.java from your project to make a minimax tree application for tic-tac-toe.

Objectives

• Practice writing methods
• Practice representing states for games
• Preparation for building game trees
• Apply test cases to your program

Set-up

1. Start Intellij
2. At the Welcome Window click Make New Project

1. In the New Project window
   1. Type the name of the project in theProject name: textbox.
      1. Name your projectGame Trees
2. Download the starter code from the course public folder (public/22L) and save it into your project directory. (STARTER CODE DOWN BELOW)

Implementation

The starter code includesTicTacToe.java,State.java, andTicTacToeState.java. You should not change anything inTicTacToe.java, orState.java but you can run the main method of TicTacToe.java to test your work. Your task will be to complete several methods inTicTacToeState.java.

public ArrayList findAllMoves( )

Finds all legal moves from the current state, and returns an ArrayList containing those moves. You will need to check all locations in the board, and create a move for that location if its current value is not X or O (it will benull, if so.)

public boolean doMove( State.Move move )

Performs the given move on this state if it was a valid move (inside the boundaries of the board, and does not overwrite existing values), changing the value in the board for this state only if the move was valid. Must also change the value ofplayerTurn. Returnstrue if move was valid,false otherwise.Note: You will need to castmove to be aTicTacToeState.Move inside this method, since the interface specifies it to be aState.Move in the parameter declaration.

public void undoMove( State.Move move )

Undoes the effect of the given move on this state, resetting the board value at the move's row and column tonull.Note: You will need to castmove to be aTicTacToeState.Move inside this method, since the interface specifies it to be aState.Move in the method parameter declaration.

public boolean gameOver()

Returnstrue if the game is over in this state (either player has gotten 3 of their mark in a row, column, or diagonal, or all spaces are notnull),false otherwise. You may want to write helper methods to check if the board is full, and whether one player or the other has won, as you may be able to reuse these in thegetValue method later.

public int getValue()

Returns the value of an end-game state. Throws anew IllegalStateException exception if the current state is not an end-game, because states cannot be evaluated when their outcome isn't known. The GameTree's nodes will be able to assign values to nodes which do not represent end of games using the minimax algorithm, but you cannot do that in this method.

Assessment

Criteria (TicTacToeState.java)	Points
Program compiles without error	8
findAllMoves from one move	5
findAllMoves multiple moves	5
findAllMoves all moves	8
doMove valid move for X	5
doMove valid move for O	5
doMove rejects invalid moves	6
undoMove for one location	5
undoMove for all locations	8
gameOver true for full board	5
gameOver false for empty board	5
gameOver false for unfinished game	5
gameOver true for wins	5
getValue throws IllegalStateException for unfinished game	7
getValue 0 for full board without win	6
getValue 1 for X wins	6
getValue -1 for O wins	6
Total	100

GIVEN CODE

import java.util.*; /** * State representation interface. * * @author sna4 * 04/12/2019 */ public interface State{ /** * Finds all legal moves from the current state. * * @return ArrayList of moves. */ public ArrayList findAllMoves( ); /** * Tests whether the game is over. * * @return true if game is over, false otherwise. */ public boolean gameOver( ); /** * Returns the value of an end-game state. Throws an exception if the * current state is not an end-game. * * @return 1 for a win, -1 for a loss. */ public int getValue( ); /** * Returns whether it is the human player's turn or not. * * @return true if it is the human player's turn. */ public boolean isPlayerTurn( ); /** * Tests whether a move is legal and performs it if so. * * @param m Move The move to be done. * * @return true if move was legal, false otherwise. */ public boolean doMove( Move m ); /** * Undoes the effects of the given move. * * @param m Move The move to be undone. */ public void undoMove( Move m ); /** * Inner class to represent a move. */ public interface Move{ } }

import java.util.ArrayList; import java.util.Scanner; public class TicTacToe { TicTacToeState curr; public TicTacToe(){ curr = new TicTacToeState( false ); Scanner sc = new Scanner( System.in ); while( !curr.gameOver() ) { System.out.println(curr); String mark; if( curr.isPlayerTurn() ) mark = "O"; else mark = "X"; System.out.println( "Choose the next move for " + mark ); ArrayList< State.Move > moves = curr.findAllMoves(); for( int i = 0; moves != null && i < moves.size(); i++ ){ System.out.println( i + ": " + moves.get(i).toString() ); } int choice = sc.nextInt(); curr.doMove( moves.get(choice) ); } System.out.println(curr); if( curr.getValue() == 1 ){ System.out.println( "Win for X!" ); } else if( curr.getValue() == -1 ){ System.out.println( "Win for O!" ); } else{ System.out.println( "Tie!" ); } } public static void main( String[] args ){ new TicTacToe(); } }

import java.util.ArrayList; public class TicTacToeState implements State { String[][] board; boolean playerTurn; /** * Default constructor. Creates a starting game state. * Computer will be X, and player will be O. * * @param turn Indicates whether it is the player's turn first. */ public TicTacToeState( boolean turn ){ board = new String[3][3]; this.playerTurn = turn; } /** * Copy constructor. Creates a new state by * copying the values in the board and turn parameters. * Computer will be X, and player will be O. * * @param board The current game board to be copied. * @param turn Indicates whether it is the player's turn in this state. */ public TicTacToeState( String[][] board, boolean turn ){ this.board = new String[3][3]; for( int r = 0; r < board.length; r++ ){ for( int c = 0; c < board[r].length; c++ ){ this.board[r][c] = board[r][c]; } } this.playerTurn = turn; } /** * Returns the mark for the player whose turn it is in this state. * * @return "O" if playerTurn is true, "X" otherwise. */ public String getMark(){ return playerTurn ? "O" : "X"; } /** * Returns the board for this state. * * @return The board. */ public String[][] getBoard(){ return board; } /** * Returns whether it is the human player's turn or not. * * @return true if it is the human player's turn. (The current turn is "O".) */ public boolean isPlayerTurn() { return playerTurn; } /** * Returns a string representation of this state. * * @return The string representing this state. */ public String toString(){ String ret = ""; String bar = " ------------- "; ret += bar; for( int r = 0; r < board.length; r++ ) { for (int c = 0; c < board[r].length; c++) { if( board[r][c] == null ) { ret += " | "; } else{ ret += " | " + board[r][c]; } } ret += " | "; ret += bar; } return ret; } /** * Finds all legal moves from the current state. * * @return ArrayList of moves. */ public ArrayList findAllMoves() { return null; } /** * Tests whether the game is over. * * @return true if game is over, false otherwise. */ public boolean gameOver() { return false; } /** * Returns the value of an end-game state. Throws a new IllegalStateException if the * current state is not an end-game. * * @return 1 for a win for X, -1 for a loss. */ public int getValue() { return 0; } /** * Tests whether a move is legal and performs it if so. * * @param m Move The move to be done. * @return true if move was legal, false otherwise. */ public boolean doMove(State.Move m) { return false; } /** * Undoes the effects of the given move. * * @param m Move The move to be undone. */ public void undoMove(State.Move m) { } public class Move implements State.Move { int r; int c; /** * Default constructor. */ public Move( int r, int c ){ this.r = r; this.c = c; } /** * Returns a string representation of this move. * * @return The string representing this move. */ public String toString(){ return "row " + r + " column " + c; } /** * Determine whether this move is equal to another object. * * @return true if all data from the move matches, false otherwise. */ public boolean equals( Object o ){ if( o instanceof Move ){ Move m = (Move)o; return m.r==r && m.c==c; } return false; } } }