Zero Sum Game With Min-max Trees

What is a min-max game tree?
                 Every two-player game which is also zero-sum can be represented as a min-max tree wherein one player assumes the role of "max" and another is assumed to be "min". This type of assumption is ideal for zero-sum games because the best move for "max" will be the worst move for "min". Every zero-sum game has only one governing utility function that decides the "goodness" of a move for a player. If the value returned by that function for a move for max is 'a', then the value for the same move for min will be '-a' and vice versa. Thus, at any state of the game, the total utility value for both players is zero.
                We maintain a tree structure wherein the nodes of the tree represent the player's (either min or max) state, and the edges represent the move it takes to go from one such state to another.

The Nim game:
                 Since this was intended to be a lesson on min-max tree, we started with a simple game. Our implementation of the Nim game has one pile of 'x' number of stones, where 'x' is taken as an input to our program. Each player can pick up at most 2 stones (i.e either 1 stone or 2 stones). The player which picks up the last stone(s) loses i.e. the player for which there are no more stones left to pick wins. 

Our Implementation:
                   We keep a global static variable 'remStones' which holds the number of stones left in the pile. Since there are at most 2 possible moves (one wherein the player picks 1 stone and another wherein he picks 2), our GameNode data structure can have maximum 2 children (left and right). The left child signifies the state which occurs after the player picks 2 stones, and the right occurs after he picks 1 stone. The left child may be null (in case there is only 1 stone left), or both the children may be null. By linking nodes with its children, we indirectly maintain a tree in the memory space.
                   Remember that in the code, the program acts as the "max" player and the opposite person, whose moves will be inputs to the console during run-time acts as "min". Thus, inside the tree, every move is scored from our perspective i.e. if the move benefits us, we give it a high score. Also, the root node will always signify our(max's) turn. We use a simple utility function:
                    For every leaf node:
                                 if max wins:
                                          score +1 to that node
                                 else:
                                          score -1 to that node
                    We now also propagate the score to the parents and eventually to the entire tree. The method makeMove() takes the current node as input and makes the move that give a state with the highest score. Thus, as the game progresses, a subset of the tree is traversed along a particular path and at every max turn, we calculate the next move based on the utility function.

Below is a commented code of the same program. Any doubts/suggestions/comments are most welcome.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class ZeroSumNimGame{
	static GameNode root;//root of the tree
	public static class GameNode {
	int score = -99999;
	/*the default score of a node is deliberately kept very low since
	*the computer should always be forced to make a move, however bad*/
	GameNode left;
	GameNode right;
	int info;
	int level; //even level = max, odd = min
	public GameNode(int info, int level) {
	this.info = info;
	this.level = level;
	left = null;
	right = null;
	}
	}// end GameNode class
	public static void createMaximinTree(int remStones) {
	root = new GameNode(remStones, 0);
	addChildren(root);
	propagateScores(root);
	}
	//this method populates the tree by adding adding children recursively
	public static void addChildren(GameNode node){
	if(node.info >= 2){
	node.left = new GameNode(node.info-2, node.level+1);
	node.right = new GameNode(node.info-1, node.level+1);
	addChildren(node.left);
	addChildren(node.right);
	return;
	}
	else if(node.info == 1){
	node.right = new GameNode(node.info-1, node.level+1);
	addChildren(node.right);
	return;
	}
	else{
	giveScore(node);
	}
	}
	//this method gives scores only to the leaf nodes depending on whether it is min or max
	public static void giveScore(GameNode node){
	if(node.level%2 == 0){
	node.score = 1;
	}
	else{
	node.score = -1;
	}
	}
	//this method assignes and propagates the scores to all the nodes in the tree
	public static void propagateScores(GameNode node){
	if(node.left != null && node.left.score < -1){
	propagateScores(node.left);
	}
	if(node.right.score < -1){
	propagateScores(node.right);
	}
	if(node.level%2 == 0 && node.score < -1){
	if(node.left != null){
	//if max, select the max score
	node.score = Math.max(node.left.score, node.right.score);
	}
	else{
	node.score = node.right.score;
	}
	}
	else if(node.score < -1){
	if(node.left != null){
	//if min, select min score
	node.score = Math.min(node.left.score, node.right.score);
	}
	else{
	node.score = node.right.score;
	}
	}
	}
	//this method decides which move to make next
	public static int makeMove(){
	int move = 0;
	if(!(root.left == null) && root.left.score > root.right.score){
	move = 2;
	}
	else{
	move = 1;
	}
	return move;
	}
	public static void main(String[] args) throws IOException{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	boolean isComputerTurn = true;
	int remStones = 11;
	int choice;
	createMaximinTree(remStones);//create tree once and traverse acc to moves played
	while(true){
	//game loop
	if(isComputerTurn){
	if(remStones == 0){
	System.out.println("Computer wins!");
	System.exit(0);
	}
	choice = makeMove();
	if(choice == 2){
	root = root.left;
	}
	else{
	root = root.right;
	}
	System.out.println("The computer chose to remove " + choice + " stones");
	remStones -= choice;
	System.out.println("Remaining stones = " + remStones);
	isComputerTurn = false;
	}
	else{
	if(remStones == 0){
	System.out.println("Congratulations! You win!");
	System.exit(0);
	}
	System.out.println("How many stones would you like to pick up?");
	choice = Integer.parseInt(in.readLine());
	if(choice > 2 || choice < 1){
	System.out.println("You can only pick either 1 or 2 stones");
	continue;
	}
	else if(choice > remStones){
	System.out.println("So many stones are not available!");
	continue;
	}
	remStones -= choice;
	if(choice == 2){
	root = root.left;
	}
	else{
	root = root.right;
	}
	isComputerTurn = true;
	}
	}
	}
	}

view raw Maximin Tree hosted with ❤ by GitHub