Games of Strategy

par Karthikeyan Bhargavan

Introduction

In this TD, we will learn to write programs that compute winning strategies for games. In the first part, we will implement a backtracking algorithm that solves Sudoku puzzles. In the second part, we will implement a min-max algorithm that computes the best strategy to win a Nim game.

The Sudoku Game

Sudoku is a popular puzzle game where the objective is to fill out an NxN board with numbers such that certain constraints are respected. Typically Sudoku boards have 9 rows and 9 columns. For example, consider the puzzle on the right of the following picture and its solution on the left:

To begin with, we only consider simple Sudoku puzzles with row and column constraints.

Each row in the puzzle must use every number between 1 and 9 exactly once
Each column in the puzzle must use every number between 1 and 9 exactly once

Hence, in the original puzzle on the right, we cannot write the number 3 at position (3,6) since it already appears in column 6. The objective of the first part of the TD is to write a solver that takes a partially-filled Sudoku puzzle, like the one on the right, and compute a valid solution, like the one on the left.

Preliminaries

Download and unzip the files in TD9.zip in your eclipse src directory within the TD9 project. It should create the following directory structure

(default package)
Test.java
puzzle0.txt
puzzle1.txt
puzzle2.txt

(package sudoku) 
sudoku/GameState.java 
sudoku/SudokuBoard.java
sudoku/SudokuInterface.java
sudoku/ValidSudokuBoard.java 
sudoku/SudokuSolver.java
sudoku/SudokuRegionSolver.java 
sudoku/SudokuDrawing.java
sudoku/MoveChooser.java

(package nim) 
nim/GameState.java 
nim/NimBoard.java
nim/NimInterface.java
nim/NimSolver.java
nim/NimDrawing.java 
nim/MoveChooser.java

Move the puzzle*.txt files to the main directory for the project. Compile and run Test.java. It should show you a Sudoku Board as follows

This main class for this window is SudokuBoard which implements the interface SudokuInterface. The important methods in this interface are as follows:

public interface SudokuInterface {
    ...
    public int getBoardSize();
    public boolean hasValue(int x, int y);
    public int getValue(int x, int y);
    public LinkedList<Integer> getMoves(int x, int y);
    public void move(int x, int y, int n);
    public void undo(int x, int y);
    ...
}

getBoardSize() returns the size of the board
hasValue(x,y) returns true if some (valid) value has been assigned to the board position (x,y) (at row x and column y)
getValue(x,y) returns the number written at (x,y)
getMoves(x,y) returns all the valid numbers that may be written to (x,y)
move(x,y,n) writes the number n to (x,y)
undo(x,y) erases the value written at (x,y)

Validating Sudoku Moves

The class SudokuBoard does not check for validity of the values written on the board and hence it accepts invalid solutions. To fix this, we define a new class ValidSudokuBoard as follows:

package sudoku;

public class ValidSudokuBoard extends SudokuBoard {

    public ValidSudokuBoard(int size) {
	super (size); 
    }

   public boolean isValidMove(int x, int y, int n) {
        ...
   }
}

You are already provided with a skeleton of this class in the sudoku package. You must define the method isValidMove(int x,int y,int n) which returns true if and only if the proposed value n for the location at row x and column y is valid. That is, that n is a number in the range [1 .. getBoardSize()] and that n does not appear in row x or column y.

You can test this code using the method test1() in Test.java. It should produce the following output:

Loading Sudoku puzzle from file puzzle0.txt
Invalid value 1 at position (0,1)
Invalid value 1 at position (0,2)
...
Invalid value 9 at position (8,7)
Invalid value 9 at position (8,8)
Loading Sudoku puzzle from file puzzle1.txt

It should also produce a new Sudoku board; you can see that this board now offers fewer options in each drop-down list; this is because the getMoves method calls isValidMove to compute the list of valid moves to offer to the user.

Upload ValidSudokuBoard.java.

Efficient Representation of Sudoku Constraints

The method isValidMove is called many times when loading, drawing, and solving a Sudoku puzzle. The naive implementation of this method takes 2 * boardSize time for each call. Instead, we will now implement a more efficient way of storing and checking the row and column constraints. You are provided with a class SudokuSolver which maintains two vectors, rowMoves and columnMoves. For each row r, the vector rowMoves.get(r) is a set consisting of the numbers that have not yet been added to row r. Similarly, for each column c, columnMoves.get(c) contains the numbers that have not yet been added to column c.

public class SudokuSolver extends SudokuBoard {

   Vector<Set<Integer>> rowMoves;
   Vector<Set<Integer>> columnMoves;

    public SudokuSolver(int size) {
	super (size); 
	initializeSets();
    }

    public void initializeSets(){
	rowMoves = new Vector<Set<Integer>>(getBoardSize());
	columnMoves = new Vector<Set<Integer>>(getBoardSize());
	for (int i = 0; i < getBoardSize(); i++) {
	    HashSet<Integer> rs = new HashSet<Integer>();
	    rs.addAll(getAllMoves());
	    rowMoves.add(rs);
	    HashSet<Integer> cs = new HashSet<Integer>();
	    cs.addAll(getAllMoves());
	    columnMoves.add(cs);
	}
    }

    ...

}

The constructor calls initializeSets to initialize all the rowMove and columnMove sets to contain all the numbers (e.g 1,...,9) that may be written to a board location. In this exercise, you must write three methods

public boolean isValidMove(int x, int y, int n);
public void move(int x, int y, int n);
public void undo(int x, int y);

isValidMove(x,y,n) is a new implementation of isValidMove that uses rowMoves and columnMoves to check that the value n may be written to (x,y)
move(x,y,n) is called when the current player chooses to write n at (x,y). It first calls super.move(x,y,n) and then modifies rowMoves and columnMoves accordingly
undo(x,y) is called when the "Undo" button is pressed on the Sudoku board. It first modifies rowMoves and columnMoves and then called super.undo(x,y)

The test method for this exercise in Test.java is test2(). It should produce the exact same result as Exercise 1.

Upload SudokuSolver.java.

A Sudoku Solver with Backtracking

Using the method getMoves from SudokuBoard, we now define a method solve(int i, int j) that solves a Sudoku puzzle starting from row i and column j. Initially, some board positions have values (hasValue(x,y) = true) but others are blank (hasValue(x,y) = false). The method solve implements a backtracking algorithm, trying out all possible moves (using move) for each blank position and backtracking (using undo) if it finds an invalid board. (A board is invalid when the number of moves returned by getMoves is empty). Finally, solve returns a boolean representing whether it found any solution or not.

public boolean solve(int i, int j){
  ...
}

Then define the method solve as follows (it is already provided in SudokuSolver); this method is called when the "Solve" button is pressed on the Sudoku board:

public boolean solve(){
  boolean b = solve(0,0);
  if (b) setGameState(GameState.Winning);
  else setGameState(GameState.Losing);
  return b;
}

To test these methods, use test3() and click on the "Solve" button. The resulting board should look like the Sudoku solution shown before the first exercise.

Upload SudokuSolver.java.

Sudoku with Region Constraints

Sudoku puzzles often have a third constraint. The board is divided into several two-dimensional regions and the numbers that appear in each region must also be distinct. For example, consider the 9x9 puzzle below, divided into 9 regions of 3x3 each. Then the region constraint is written as follows:

Each region in the puzzle must use every number between 1 and 9 exactly once

Computing Regions

The class SudokuBoard already supports puzzles with region constraints. You are provided with a class SudokuRegionSolver that extends SudokuSolver with region constraints as follows:

public class SudokuRegionSolver extends SudokuSolver {

   Vector<Set<Integer>> regionMoves;
   public SudokuRegionSolver(int size, int x, int y) {
	super (size,x,y);
	initializeRegions();
   }

   public void initializeRegions(){
	regionMoves = new Vector<Set<Integer>>(getBoardSize());
	for (int i = 0; i < getBoardSize(); i++) {
	    HashSet<Integer> rs = new HashSet<Integer>();
	    rs.addAll(getAllMoves());
	    regionMoves.add(rs);
	}
   }
}

Define a method getRegion that computes the region that a board location falls in:

public int getRegion(int x, int y);

For example, the location (3,5) in a 9x9 puzzle falls in region 4. To program this method, you may use the following methods in SudokuInterface:

public boolean hasRegions();
public int getRegionRows();
public int getRegionColumns();

hasRegions() returns true only if the current puzzle has region constraints
getRegionRows() returns the number of rows in each region
getRegionColumns() returns the number of columns in each region

The test method for this exercise is test4() in Test.java. It should return the following result.

Loading Sudoku puzzle from file puzzle2.txt
The region for location (3,5) is 4
The region for location (8,0) is 6
The region for location (7,7) is 8

It should also display a puzzle board that looks like the original board but with 9 regions being displayed.

You can play with this puzzle. You will find that solving it is more difficult than solving the first puzzle.

Upload SudokuRegionSolver.java.

Solving Sudoku Puzzles with Region Constraints

The backtracking algorithm in solve relies on the methods isValidMove, move, and undo to enforce the puzzle constraints. You must now reimplement these three methods in SudokuRegionSolver to account for the region constraints encoded in the vector regionMoves.

isValidMove(x,y,n) implements region constraints using the vector regionMoves; It calls super.isValidMove to check row and column constraints
move(x,y,n) calls super.move(x,y,n) and then modifies regionMoves accordingly
undo(x,y) calls super.undo(x,y) and then modifies regionMoves accordingly

All three methods should use getRegion to compute the region that corresponding to each board position. (The solve method does not have to be redefined. It simply uses the new definitions of the three methods above.) To test this exercise, use test5() and click on solve in the GUI. The resulting board should look like the solved Sudoku board before the fourth exercise.

Upload SudokuRegionSolver.java.

The Nim Game

Nim is a two-player strategy game. The board consists of rows of stones, and in each move, a player must remove one or more stones from some row. The player who removes the last stone loses. Traditionally, a Nim board consists of three rows of 3, 4, and 5 stones, respectively:

The goal of this TD is to write a Nim playing program that computes the best (winning) strategy before each move by using a min-max algorithm. To begin, you are provided with a class NimBoard that implements the interface NimInterface.

public interface NimInterface {
    public int getRows();
    public int getStones(int row);
    public void move(int row, int stones);
    public void printMove(int row, int stones);
    public void undo(int row, int stones);
    
    public GameState evaluateGame();
    public GameState max(GameState g1, GameState g2);
    public GameState negate(GameState g);
}

The interface uses an enumeration GameState to represent the different possible results of the game for the current player:

public enum GameState{
    Unknown,
    Losing,
    Winning;
}

The methods in NimInterface are as follows:

getRows(r) returns the initial number of rows
getStones(r) returns the current number of stones in row r
move(r,s) removes s stones from row r
printMove(r,s) prints a move (r,s) to the standard output
undo(r,s) restores s stones to row r
evaluateGame() evaluates the current game position for the current user: if no stone remains, then it returns GameState.Winning; if one stone remains, then it returns GameState.Losing; otherwise it returns GameState.Unknown.
max(gs1,gs2) computes the maximum of two game states; it uses the rule Unknown < Losing < Winning
negate(gs) returns the negative of the game state gs; if gs = GameState.Winning, it returns GameState.Losing and vice versa; It leaves GameState.Unknown unchanged

The NimBoard class already implements a naive Nim player; you can test this code by running the method testNim() in Test.java and playing with the program. You should be able to win easily.

Computing the Best Result

We will first compute whether there exists a winning strategy starting from the current state of the game. Define a class NimSolver as follows:

package nim;

public class NimSolver extends NimBoard{
    
    public NimSolver(int x, int y) {
	super(x,y);
    }

    public GameState bestResult(){
       ....
    }

    public GameState worstResult(){
       ....
    }
}

You are provided with a skeleton of this class and you must implement the bestResult and worstResult methods.

bestResult(): The best possible result is computed as follows:
enumerate every possible move in the current board, execute the move and compute the worst result in the next game;
the best result in the original game is the maximum of all these worst results in the next games.
(bestResult should only return GameState.Losing or GameState.Winning, never GameState.Unknown.)
worstResult(): The worst possible result is computed as the negation of the best result.
This is because Nim is a "zero-sum" game, the worst result for the current player is the best result for the other player; hence the "score" of one player can be computed as the negation of the "score" of the other player. (In more complicated games, worstResult would need to compute the minimum of the best results over all possible next games.)

The test code for this is test6(). It should produce the following output

Move: Removing 1 from row 0
      Projected result for next player: Winning
Move: Removing 1 from row 0
      Projected result for next player: Losing
Projected result: Losing

It should also show you a Nim board with 1 stone remaining in the first row, 4 stones in the second row, and 5 stones in the third row. The program predicts that the user will definitely lose from this position, if the program always makes the best moves.

Upload NimSolver.java.

Computing the Best Move

Write a method bestMove, similar to bestResult above, that executes the best next move, that is, a move that is most likely to result in a winning result for the current player.

public void bestMove() {
  ...
}

Just like in bestResult, your code will enumerate all possible next moves and compute worst results for the next game. The best move is one whose worst result in the next game is the maximum of all the worst results. After finding the best move, you must execute the move using move and then use printMove to printout this move. The test code for this exercise is in test7(). It should produce the following output

User's Turn:
------------
Move: Removing 1 from row 0
      Projected result for next player: Winning
Computer's Turn:
----------------
Move: Removing 1 from row 0
      Projected result for next player: Losing
------------
New Game
------------
User's Turn:
------------
Move: Removing 2 from row 0
      Projected result for next player: Losing
Computer's Turn:
----------------
Move: Removing 1 from row 0
      Projected result for next player: Winning

It should also show you a Nim board and the program predicts that you can win. But be careful, your program is now a really smart player!

Upload NimSolver.java.