Introduction

Nim is a two-player strategy game where objects are placed into several stacks. On their turn, a player must pick one stack and take away 1, 2, or 3 objects from that stack (not from multiple stacks.) The player who is forced to take away the last object loses, and the other player wins.

Your task for this project will be to implement agame tree for Nim, which uses theminimax algorithm to select moves for the computer. This allows the computer to consider all possible future moves for either player, and select its moves that ensure a preferable outcome.

Remember that minimax creates the entire tree of all possible move sequences. Leaf nodes (containing end-game states) should be assigned their own value according to whether the computer wins (1), human wins (-1), or tie (0) for games which allow ties. Non-leaf nodes should be assigned values based on their maximum child value for computer moves, or minimum value for human moves.

Pseudocode for minimax tree building:

public Node makeSubtree( State state, Move m ){

a new node

if state is an end of game{ // leaf node

if computer player wins

node's value =1

else if human opponent wins

node's value =-1

else

node's value =0

}

else{// non-leaf node

for each move possible from state

do move on state

recursively call makeSubtree for updated state

save the root of that new subtree as a child of node

undo move

if( it's the computer player's turn in state )

node's value =max of all children's values

else

node's value =min of all children's values

}

return node

}

Program and Starter Code

The starter code contains two files:State.java andNim.java.State.java contains an interface representing aState for a zero-sum game. It contains the signatures of the methods that you need to implement.Nim.java contains the code for a text-based user interface forNim, allowing users to enter their moves at command prompt and selecting the computer player's moves

using the game tree. Do not changeState.java orNim.java.

NimState.java inner class Move

This class represents a single move in a Nim game, where some number of items (between 1 and 3) is taken from a given stack. It should be declared aspublic static class Move implements State.Move . It will need to implement the following methods:

public Move( int stack, int num )

The constructor for Move. It should initialize the fields for stack (an integer indicating which stack to take items from) and number (an integer indicating how many items to take) using the given parameters.Note: Stack numbers start at 1 for the first stack, not zero.

public boolean equals( Object o )

Compares an objecto to this move. Returns true ifo is aMove and takes the same number of items from the same stack as this move.

public String toString()

Returns a string representing the move. It should do so in a user-friendly way that works well for the user interface:Taking 2 from stack 3

NimState.java

This class represents a single state in a Nim game, including all the important features (how many items are in each stack and whose turn it is, for instance.) It will also provide some functionality for using states, such as determining whether the state represents an ended game, and what value that state may have (only if it is an end-game state. The tree will be used to evaluate whole branches of possibilities.) It should be declared aspublic class NimState implements State . It will need to implement the following methods:

public NimState( int n, boolean pt )

The main constructor for NimState. It should create a default style Nim starting state, where there are n stacks created with 1 throughn items in each stack (so stack 1 starts with 1 item, stack 2 with 2 items, etc.) Note that the physical game uses stacks of objects, but you do not need Java stacks for these. You only need an array of integers to track how many objects remain in each stack. The second variable,pt, indicates whether the game should begin with the human player taking the first turn (true) or the computer taking the first turn (false.)

public NimState( int[] stacks, boolean pt )

A copy constructor for NimState. It takes the information from another NimState (thestacks array and the booleanpt for whose turn it is) and copies it into a new state.Note: When copying objects or arrays, you should make a new object/array and copy all values over individually. Just making a new array variable and storing the other state's array in it whole will lead to both states changing when you modify either of them.Required for testing.

public int[] getStacks()

Returns the stacks array for this state.Required for testing.

public boolean isPlayerTurn()

Indicates whether it is the human player's turn (true) or the computer's turn (false) in this state.Required for testing.

public String toString()

Returns a string representation of this game state, displaying a label for each stack and an X for each item in it. For example:

1:

2: XX

3: XX

4: XXXX

public boolean gameOver()

Returnstrue if the game is over in this state (there are no items left in any stack),false otherwise.

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.

public boolean doMove( State.Move move )

Performs the given move on this state if it was a valid move, changing the values of the stacks and the boolean for turn for this state only if the move was valid. Returnstrue if move was valid,false otherwise.Note: You will need to castmove to be aNimState.Move inside this method, since the interface specifies it to be aState.Move in the method parameter declaration.

public void undoMove( State.Move move )

Undoes the effect of the given move on this state, changing the values of the stacks and the boolean for turn for this state.Note: You will need to castmove to be aNimState.Move inside this method, since the interface specifies it to be aState.Move in the method parameter declaration.

public ArrayList findAllMoves( )

Finds all legal moves from the current state, and returns an ArrayList containing those moves.

GameTree.java inner class Node

This class represents a node in the minimax game tree, which reports certain information about the values and predictions from this position in the tree.It may need fields to store things like the node's value, its children, and its best child. It should be written to useState andState.Move objects, so the tree could be used for any kind of game with a properly defined state.Do not use variables of typeNimState orNimState.Move in this class. It will need to implement the following methods:

public Node( State.Move m )

The constructor for Node. It should initialize any necessary fields.

public int getValue()

Returns the minimax value for this node. Unlike states, nodes can have values even if they do not represent an end-of-game state, because they inherit values from their children by the minimax algorithm.

public State.Move getMove()

Get the move that led to this node.

public Node getBestChild()

Get the node's best child. This will be the child that gave this node its value, according to the minimax algorithm, or in other words the node the player or computer (whoever's turn it is) would select as their preferred next state.

public Node findChild( State.Move m )

Find the child whose move matches the parameter. This is required so that when the human player selects a move, the tree can be changed to have the node representing that move as its new root and planning for the computer can continue from that node.

public String getPrediction()

Get the predicted winner for this subtree ("player" for human player,"computer" for our computer player, or"no one" for ties), based on minimax values.

GameTree.java

This class represents an entire minimax game tree containing a node for each possible state from the given starting state. It should be written to useState andState.Move objects, so the tree could be used for any kind of game with a properly defined state.Do not use variables of typeNimState orNimState.Move in this class. It will need to implement the following methods:

public GameTree( State start )

The constructor for GameTree. It should initialize any necessary fields, including calling methods to build the tree starting fromstart.

public Node getRoot(){

Returns the root of this tree.Required for testing.

public Node buildTree( State state, State.Move move )

Builds a node and its subtree from a given state. Should return a new Node object that represents the root of the subtree beginning atstate. In the returned tree, each node should be assigned its correct value according to the minimax algorithm.

public int getSize( )

Returns the total number of nodes in the tree.Required for testing.

Example output from Nim.java:

Number of stacks: 3

Who moves first? Player (0) or computer (1): 0

447 nodes in tree.

1: X

2: XX

3: XXX

Predicted win for computer.

Number to take (1-3): 2

From stack: 1

Can't take 2 objects from 1

Please try again!

1: X

2: XX

3: XXX

Predicted win for computer.

Number to take (1-3): 1

From stack: 2

Player move: Taking 1 from stack 2

1: X

2: X

3: XXX

Predicted win for computer.

Computer move: Taking 2 from stack 3

1: X

2: X

3: X

Predicted win for computer.

Number to take (1-3): 1

From stack: 3

Player move: Taking 1 from stack 3

1: X

2: X

3:

Predicted win for computer.

Computer move: Taking 1 from stack 1

1:

2: X

3:

Predicted win for computer.

Number to take (1-3): 1

From stack: 2

Player move: Taking 1 from stack 2

Game over!

Computer won.