Nim Challenge

• Download source code - 251 Kb
• Find the application in Google Play

Introduction

Nim is a strategy game, where two players take turns removing objects from distinct heaps. A player can remove any number of items, as long as they all come from the same heap and they appear in consecutive places. The player who removes the last item from all the heaps wins.

I believe that most of you have played this game before and many of you would also probably know that Nim is by no means a game of luck. Instead, an algorithm exists that if applied correctly, allows one of the two players to always win. Nim Challenge is an Android application that implements this "Winning Strategy" and challenges the player to apply it in different situations and under time pressure.

Winning Strategy

Let us start the description of the Winning Strategy with an example. Consider an arrange of three heaps, one of size 1, one of size 2 and one of size 3.

This arrange can be represented as follows:

For each row we count the number of elements. We convert the number to its binary representation. A binary number consists of 1s and 0s. In each column we count the number of 1s. If the result is an odd number, then in the corresponding column at the Sum we get an 1. If it is an even number, we get a 0.

If the Sum is all zeros, then the player who plays first loses. On the other hand, if there is even a single 1 in the Sum, then the first player can always find a move that it will convert the arrange of items into a form that has a zero Sum and win.

The above algorithm assumes that the last player to remove an item wins. However the game is also frequently played such as the last player loses. This is referred as a "misère " game. In a "misère " game the same algorithm can be applied, with the exception when only heaps of size 1 are to be left. In that case, the player must try to leave an odd number of size 1 heaps.

When you play, it is difficult to convert into binary and calculate the sum quickly. Even if you do so, you still need to find the move that it will lead to a zero sum arrange and this is not easy either. In order to play quickly, you can follow a small set of rules:

• An arrange of 1, 2, 3 loses.
• An arrange of 1, 3, 5 wins (convert it to 1, 2, 3).
• An arrange, where each number appears an even number of times loses (e.g 1,1,2,2 and 4,4). You can quickly draw out of the picture duplicating rows.
• A combination of a winning and a losing arrange wins.

Game modes

Nim Challenge offers three different game modes. In Classic mode the original arrange of items is used. The player can select whether to play first or not, but in order to win the player must start first. You can try this mode to practice and follow computer's moves.

In Variations mode different arranges of items are used. The player selects, if she wants to play first or not. This is a crucial decision and the specific arrange of items must be taken into account. If the player wins, she can continue playing another game. Every time the arrange of items is getting more complicated. In this mode a score is kept. The player must play as quickly as possible in order to win more points.

In Challenge mode you play against time. You only have a limited amount of time to find the best move. If the time expires, you lose. In this mode also a score is kept and faster moves win more points.

Nim Challenge also allows you to create Custom Boards. You can create any number of custom boards and edit them by long touching on them in the Custom Boards list. You can use this facility to practice by playing the same board again and again.

Settings

The following aspects of the game can be configured:

• Single Touch: If checked each move needs not to be confirmed and it is instantly played. This is quicker, but doesn't give a chance to correct an error.
• Theme: Selects the appearance of the board.
• Last wins: Selects if the game will be played as a normal (checked) or misère game (unchecked). In a normal game the player who removes the last element wins. In a misère game the last player loses.

The above settings affect all game modes.

Source Code

The design and the implementation of Nim Challenge follow the same principles as Puzzles Solver. These principles were thoroughly described in a previous article. Instead of repeating them here, I would like to briefly refer to some challenging problems I faced during the implementation of Nim Challenge.

Drawing lines

All graphics in the game are using Canvas drawing and simple View objects. The nature of the game is such that fast updates aren't needed. so a more advanced solution isn't necessary. There is however a detail that needs special treatment. In order to select items from a heap the user strikes a line between two points in the screen:

The user first touches on the screen to select the starting point and then drags his/her finger to select the ending point. While dragging the line is dynamically updated. The code snippet below presents how the dynamic update is handled in the onTouchEvent method of the NimView.

switch(event.getAction())
{
case MotionEvent.ACTION_DOWN:
    // First touch - Set the starting point, reset the isAnimationDelayed flag, start the move
    isAnimationDelayed = false;
    if (moveState == MoveState.Move_Idle) {
        startPoint.set((int) event.getX(), (int) event.getY());
        endPoint.set((int) event.getX(), (int) event.getY());
        moveState = MoveState.Move_Started;
    }
case MotionEvent.ACTION_MOVE:
    // User drags his/her finger - set the ending point and update the line
    if (moveState == MoveState.Move_Started) {
        endPoint.set((int) event.getX(), (int) event.getY());
        // Only invalidate the view if more than 100ms (animationDelay) from the previous
        // update have passed
        if (!isAnimationDelayed) {
            isAnimationDelayed = true;
            animationDelayHandler.postDelayed(new Runnable() {
                @Override
                public void run() {
                    if (isAnimationDelayed) {
                        invalidate();
                        isAnimationDelayed = false;
                    }
                }

            }, animationDelay);
        }
    }
case MotionEvent.ACTION_UP:
    isAnimationDelayed = false;
    if (moveState == MoveState.Move_Started) {
        endPoint.set((int) event.getX(), (int) event.getY());
        moveState = MoveState.Move_Idle;
        
        // Find the objects selected by the user
    }

As you can see the screen is only updated every 100ms (or when the user lifts his/her finger) and not every time a new ACTION_MOVE event is received. ACTION_MOVE are sent too often and if one makes the mistake to respond to each one of them, then one will seriously degrade the application's performance.

Time Counter

In order to count the game time I have created a simple TimeCounter class. This class uses System.currentTimeMillis() method to measure time and a single instance of it is used by NimGame, which is the game Activity and NimView, which is the View responsible for drawing the game canvas and handling user input.

Inside NimView there is a Handler that launches a Runnable to run once a second.

// Constructor
timerHandler = new Handler();

// Start of time measurement
timeCounter.start();
timerHandler.postDelayed(timeRunnable, 1000);

// Code to run once a second
private Runnable timeRunnable = new Runnable() {
    @Override
    public void run() {
        if (gameState == GameState.User_Move || gameState == GameState.First_Player_Question) {
            // Re-draw the screen
            invalidate();
        }
        timerHandler.postDelayed(timeRunnable, 1000);
    }
};

Inside the onDraw method the updated time is rendered on the screen. The check if the time has expired, also happens there. This gives some extra milliseconds to the user to respond.

From all these it may seems that the TimeCounter is only needed by the NimView and that there is no reason to be shared with the NimGame. The reason that the NimGame needs access to the TimeCounter has to do with the life cycle handling of the application. NimGame hosts the onPause and onResume methods, where some important time related actions need to be performed. For sure the timer needs to be paused, when the onPause method is called. This will happen for example, when the phone rings during a game. We would then like the user to answer the call and then return to the game without the time having advanced. So one solution will be to resume the timer, when the onResume method is called. However, it isn't always as simple as this. In some devices the onResume method may be not called, when the uses switches off the screen. In that case the application will be behind a lock screen. Upon unlocking the screen, the onResume isn't called. One may register a Broadcast Receiver to monitor the events. Or utilize the public void onWindowFocusChanged (boolean hasFocus) method. These are all complicated solutions and may not work the same among all devices. However, I don't believe that any of these is actually needed. There is an alternative that is both simpler and provides better user experience. In order to deal with these cases, we follow this pattern:

• When the application is paused or loses foreground focus, pause the timer. Gray-out the screen to indicate that the game is in paused mode.
• Require user action to resume the timer. Whenever the user returns to the user, he/she will be met with a gray-out screen and will have to touch anywhere at the screen to continue.

This logic is easy to implement, works well across all devices and in all cases of the application going into background and most of all works better for the user.

@Override
public void onPause() {
    super.onPause();

    if (!gameFinished) {
        // Pause the timer
        timeCounter.pause();
        // Pause the view - the screen will be grayed out and a "Pause" message will appear
        nimView.setPaused(true);
    }
}

@Override
public void onResume() {
    super.onResume();

    // Invalidate the view for the gray-out screen to appear - wait for user input to continue
    nimView.invalidate();
}

History

• First version of the article