Click here to Skip to main content
Click here to Skip to main content
Go to top

Checkers for Pocket PC using a Recursive Min-Max Tree

, 19 Jun 2008
Rate this:
Please Sign up or sign in to vote.
Checkers/Draughts game for Pocket PC, using the recursive Min-Max tree to calculate moves, coded with C# over the .NET Compact Framework
Checkers20_cab

Introduction

One day, I just typed "checkers" here on The Code Project and found no results for a checkers game, so I decided to put the code here for a checkers game which I coded some time ago and share with you what I did at that time to learn programming for .NET Compact Framework. It was a game meant to be simple and considering that I wanted it to run on a pocket PC, it had to be small and "think" quick, and hopefully, a good player. Otherwise it would be boring (although I think that an invincible player won't be so much fun either).

Basically I needed a recursive approach, so I decided to use a min max game tree instead of reinventing the wheel. But like every coder, you always want to make things perfect. So the next second, I wanted to make more board games and more games (yet simple ones) using the min max method, all of them turn based games.

So... I decided to create reusable modules for those simple turn based games, and also a module for the board games. And the modules finally fit well on other games that I coded later, such as Chess and Othello or Reversi.

Basically the games have three main modules. The game was initially coded for .NET Compact Framework 1.1, so those "modules" are .NET assemblies.

BoardEngine Library

The idea behind this library is just to refactor the classes used and to share that library across the rest of the games coded later.

BoardEngine, the library for the board work has the following classes:

  • Board
  • BoardPosition
  • Piece
  • PieceColor (enum)

GamesPackage Library

GamesPackage, the library for turn based games has the following classes:

  • IPlayer (interface)
  • Moderator (abstract class, but with important base implementation)
  • Delegates and other useful items

The Moderator class is constructed by receiving N objects implementing the IPlayer, interface, and it manages to control how they play. In this case, we can use moderator to allow two different implementations of the game to play (maybe to see who coded the best Checker or Chess playing machine) or you can create a player that only reacts to user input on the device.

The UI

The Graphics are not so fancy but they are good and the game also has some skins (easy ones). This project contains:

The Game UI

  • Implementation for a computer player
  • Implementation for a human player (in its turn, waits for user input)

The Player...

 protected double SelectMove(CheckersBoard board, PieceColor color, 
    int level, double alpha, double beta)
        {
            System.Collections.ArrayList moves = board.RightMoves(color);
            if (level == 0 || moves.Count == 0)
                return Eval(board, level);
            else
            {
                if (level == LEVELS + (int)this.Color && (moves.Count == 1))
                {
                    sMove = moves[0] as CheckersMove;
                    return 0;
                }
                double max = (this.Color == color) ? double.MinValue : double.MaxValue;
                for (int i = 0; i < moves.Count; i++)
                {
                    CheckersMove move = moves[i] as CheckersMove;
                    CheckersBoard newBoard = PerformMove(board, move);
                    double eval = SelectMove(newBoard, (PieceColor)
                (((int)color + 1) % 2), level - 1, alpha, beta);
                    if (color == this.Color)
                    {
                        if (max < eval)
                        {
                            max = eval;
                            if (level == LEVELS + (int)this.Color) sMove = move;
                            if (beta <= max) break; else alpha = Math.Max(alpha, max);
                        }
                        else if (max == eval && (level == LEVELS + (int)this.Color) && 
                                (r.Next(9) % 2 == 0))
                            sMove = move;

                    }
                    else
                    {
                        if (max > eval) max = eval;
                        if (alpha >= max) break; else beta = Math.Min(beta, max);
                    }
                }
                return max;
            }
        }

The Evaluation Function

The evaluation function used on this min max tree gives importance to how many Queens exist and how close the Pawns are to be promoted. Here is the code for that function:

protected double Eval(CheckersBoard board, int level)
{         
    double myval = 0;
    double enemyval = 0;
    for(int x=0; x<board.Width; x++)
    for(int y=0; y<board.Height; y++)
    {
        CheckersPiece piece=board.GetPieceAt(x, y) as CheckersPiece;
        if(piece!=null)
        {
            int factor  = (piece.Color == PieceColor.White)?(7-y):(y);
            if (piece.Color == this.Color) 
            {
                if (piece is Pawn) myval+=100 + (factor*factor);
                else 
                {                               
                    myval+=200;
                    if (y==0) 
                    {
                        if (x==0) myval-=40;
                        else myval-=20;
                    }
                    else if (y == 7) 
                    {
                        if (x==7) myval-=40;
                        else myval-=20;                                                                        
                    }
                }
            }
            else 
            {
                if (piece is Pawn) enemyval+=100 + (factor*factor);
                else  
                {
                    enemyval+=200;
                    if (y==0) 
                    {
                        if (x==0) enemyval-=40;
                        else enemyval-=20;
                    }
                    else if (y == 7) 
                    {
                        if (x==7) enemyval-=40;
                        else enemyval-=20;                                                                        
                    }
                }
            }
        }
    }

    if (enemyval == 0) return 100000 + level*level;
    else if (myval == 0) return -100000 - level*level;
    return (myval - enemyval);
}

The game offers four levels of intelligence that analyze(2, 4, 6, and 8 levels) perfect values on the PDA. On a desktop computer, you can compute a lot more levels so it will be harder to beat.

Finally

Both the BoardEngine and the GamesPackage saved a lot of time when coding turn based games. Although the library needs to be polished and prepared for CF 2.0 and newer (Generics), it works fine and I have coded backgammon and dominoes games using them too.
Hope you like it!

History

  • 20th June, 2008: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Leonardo Paneque
Team Leader
United States United States
Leonardo loves to code with C# and thinks .NET platforms rocks.
He has a Master degree in Computer Sciences and likes to share code and ideas.
Follow on   Twitter

Comments and Discussions

 
GeneralVGA Pinmemberjoubertvasc25-Jan-09 5:59 
GeneralThanks PinmemberGaj-IT20-Jun-08 22:44 
Thanks for that Leo, I'll have to download it and have a play.
GeneralMissing Code PinmemberSteven Bralovich20-Jun-08 1:51 
GeneralRe: Missing Code PinmemberLeonardo Paneque20-Jun-08 2:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140916.1 | Last Updated 20 Jun 2008
Article Copyright 2008 by Leonardo Paneque
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid