Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Checkers for Pocket PC using a Recursive Min-Max Tree

, 19 Jun 2008
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.zip
GamesPackage
GamesPackage.csdproj
GamesPackage.csdproj.user
GamesPackage.csproj.user
GamesPackage.resharperoptions
GamesPackage.suo
SoundPPCLibrary
SoundPPCLibrary.csdproj
SoundPPCLibrary.csdproj.user
SoundPPCLibrary.csproj.user
SoundPPCLibrary.resharperoptions
SoundPPCLibrary.suo
BoardEngine
BoardEngine.csdproj
BoardEngine.csdproj.user
BoardEngine.csproj.user
Checkers
001_select_checker_0.wav
002_select_destination_0.wav
003_player_move_0.wav
004_eat_a_player_0.wav
005_end_of_the_board_0.wav
006_game_over_0.wav
007_win_game_0.wav
CHECKER.ico
Checkers.csdproj
Checkers.csdproj.user
Checkers.csproj.user
Checkers.resharper.user
Checkers.resharperoptions
Checkers.suo
checkersico.ico
Thumbs.db
checkers_source.zip
using System;
using BoardEngine;
using System.Collections;

namespace Checkers
{
	public class Pawn : CheckersPiece 
	{
		int[] XMov = new int[2] {-1,1};
		int[] YMov = new int[2] {-1,-1};

		ArrayList aux;

		protected void EatMoves(int x, int y, ArrayList moves)
		{
			bool wayFound=false;

			//System.Windows.Forms.MessageBox.Show("Antes de annadir: "+aux.Count);
			aux.Add(new BoardPosition(x, y));
			//System.Windows.Forms.MessageBox.Show("Annadi: "+aux.Count);

			for(int i=0; i<2; i++){
				int newX=x+XMov[i];
				int newY=y+YMov[i];
				if(this.ParentBoard.isInsideBoard(newX, newY))
				{
					CheckersPiece piece=this.ParentBoard.GetPieceAt(newX, newY) as CheckersPiece;
					if(piece!=null && piece.Color!=this.Color)
					{
						int newX2=newX+XMov[i];
						int newY2=newY+YMov[i];
						if(this.ParentBoard.isInsideBoard(newX2, newY2) &&
							this.ParentBoard.GetPieceAt(newX2, newY2)==null)
						{
							wayFound=true;
							//System.Windows.Forms.MessageBox.Show("Llamando recursivo: "+aux.Count);
							EatMoves(newX2, newY2, moves);
						}
					}
				}
			}

			if(!wayFound && (this.X!=x || this.Y!=y))
			{
				BoardPosition[] arr=new BoardPosition[aux.Count];
				for(int j=0; j<aux.Count; j++)
					arr[j]=aux[j] as BoardPosition;
				moves.Add(new CheckersMove(arr, true));
			}

			//System.Windows.Forms.MessageBox.Show("Voy a quitar: "+aux.Count);
			aux.RemoveAt(aux.Count-1);
		}

		protected void EatMoves(ArrayList moves)
		{
			aux=new ArrayList();
			EatMoves(this.X, this.Y, moves);
		}

		public override ArrayList PossibleMoves
		{
			get
			{
				ArrayList moves=new ArrayList();
				EatMoves(moves);
				if(moves.Count==0)
				{
					for(int i=0; i<2; i++)
					{
						int newX=this.X+XMov[i];
						int newY=this.Y+YMov[i];
						if(this.ParentBoard.isInsideBoard(newX, newY))
						{
							CheckersPiece piece=this.ParentBoard.GetPieceAt(newX, newY) as CheckersPiece;
							if(piece==null)
								moves.Add(
									new CheckersMove(
									new BoardPosition[] {
															new BoardPosition(this.X, this.Y),
															new BoardPosition(newX, newY)
														},
									false
									)
									);
						}
					}
				}
				else
				{
					int max=0;
					for(int j=0; j<moves.Count; j++){
						CheckersMove move=moves[j] as CheckersMove;
						if(move.MovePath.Length>max)
							max=move.MovePath.Length;
					}
					for(int k=0; k<moves.Count; k++)
						if(((CheckersMove)moves[k]).MovePath.Length!=max)
							moves.RemoveAt(k--);
				}
				return moves;
			}
		}

		public Pawn(CheckersBoard board,int x,int y,PieceColor color) : base(board,x,y,color) 
		{
			if (color == PieceColor.Black) 
			{
				YMov[0] = -YMov[0];
				YMov[1] = -YMov[1];
			}
		}

		public override bool CanEat(CheckersPiece piece)
		{
			return false;
		}

		protected bool MoveTo(int newx,int newy,bool firststep) 
		{
			if (this.X == newx && this.Y == newy) return true;
			if (firststep) 
			{
				for(int i=0;i<2;i++) 
				{
					int tempx = this.X+XMov[i];
					int tempy = this.Y+YMov[i];
					if ((tempx == newx && tempy == newy)&& (_ParentBoard.isInsideBoard(tempx,tempy) && (_ParentBoard.isEmptyCell(tempx,tempy)))) 
					{
						return true;
					}
				}
			}    
			
			bool result = false;
			for(int i=0;i<2;i++) 
			{
				int tempx = this.X+XMov[i];
				int tempy = this.Y+YMov[i];
				
                    CheckersPiece piece = (CheckersPiece)_ParentBoard.GetPieceAt(tempx,tempy);
					//if there is an enemy piece there and I can eat
					if (piece!=null && (piece.Color!=this.Color) && _ParentBoard.isEmptyCell(tempx + XMov[i],tempy + YMov[i]) ) 
					{
						//remove the piece I am going to eat
                        _ParentBoard.RemovePiece(piece);
						//move this piece to the future position
						int oldx = this.X;
						int oldy = this.Y;
						_ParentBoard.RemovePiece(this);
						_ParentBoard.PutPieceAt(tempx+XMov[i],tempy+YMov[i],this);
						//call this method recursively
						result = result || MoveTo(newx,newy,false);
						
						//backtrack
						//move this piece back
						_ParentBoard.RemovePiece(this);
						_ParentBoard.PutPieceAt(oldx,oldy,this);
						//put the other piece agai on its position.
						_ParentBoard.PutPiece(piece);

						if (result) break;
					}
				
			}

			return result;

		}

		public override bool CanMoveTo(int newx, int newy)
		{
			
            if (!_ParentBoard.isInsideBoard(newx,newy))	return false;
			if (newx==this.X && this.Y == newy) return false;
			return MoveTo(newx,newy,true);
			
			
		}

		public bool CanMakeMove(CheckersMove move,int start) 
		{
			
			if (start == move.MovePath.Length - 1 ) return true;

			BoardPosition currentpos = new BoardPosition(this.X,this.Y);
			BoardPosition nextpos = (BoardPosition)move.MovePath[start+1];
			
			//if is a simple move
			if (move.MovePath.Length == 2 && start == 0) 
			{
				for(int i=0;i<2;i++) 
				{
					int tempx = this.X+XMov[i];
					int tempy = this.Y+YMov[i];
					if ((tempx == nextpos.X && tempy == nextpos.Y)&& (_ParentBoard.isInsideBoard(tempx,tempy) && (_ParentBoard.isEmptyCell(tempx,tempy)))) 
					{
						return true;
					}
				}
			}

			bool result = false;
			for(int i=0;i<2;i++) 
			{
				int tempx = this.X + XMov[i];
				int tempy = this.Y + YMov[i];
				//System.Windows.Forms.MessageBox.Show(tempx + "," + tempy);
				if ((tempx  + XMov[i] == nextpos.X && tempy + YMov[i] == nextpos.Y))
				{
					CheckersPiece piece = (CheckersPiece)_ParentBoard.GetPieceAt(tempx,tempy);
					//if there is an enemy piece there and I can eat
					if (piece!=null && (piece.Color!=this.Color) && _ParentBoard.isEmptyCell(tempx + XMov[i],tempy + YMov[i]) ) 
					{
						//at the moment the move is valid
						result = true;
						
						//remove the piece I am going to eat
						_ParentBoard.RemovePiece(piece);
						//move this piece to the future position
						int oldx = this.X;
						int oldy = this.Y;
						_ParentBoard.RemovePiece(this);
						_ParentBoard.PutPieceAt(tempx+XMov[i],tempy+YMov[i],this);

						//call this method recursively
						result = result && CanMakeMove(move,start+1);
						
						//backtrack
						//move this piece back
						_ParentBoard.RemovePiece(this);
						_ParentBoard.PutPieceAt(oldx,oldy,this);
						//put the other piece agai on its position.
						_ParentBoard.PutPiece(piece);
					}
				}		
			}

			return result;
		}

		public override bool CanMakeMove(CheckersMove move) 
		{
			//System.Windows.Forms.MessageBox.Show(ShowBoardPosition(this.PossiblePaths));
            return CanMakeMove(move,0);		
		}

		public override object Clone()
		{
			return new Pawn((CheckersBoard)this.ParentBoard, this.X, this.Y, this.Color);
		}

		protected override System.Collections.ArrayList MovementInDirection(System.Drawing.Point increment ,ref bool outOfBoard)
		{
			System.Collections.ArrayList path = new System.Collections.ArrayList();
			BoardPosition pos = null;
			
			pos = new BoardPosition(this.X+increment.X,this.Y+increment.Y);
			if (this._ParentBoard.isInsideBoard(pos.X,pos.Y)) 
			{
				if(!this._ParentBoard.isEmptyCell(pos.X,pos.Y))
				{
					outOfBoard = false;
					return path;
				}   
				path.Add(pos);
			}
			outOfBoard = true;
			return path;
		}

		protected override System.Drawing.Point[] IncMov {
			get 
			{
				return new System.Drawing.Point[]{new System.Drawing.Point(this.XMov[0],this.YMov[0]),new System.Drawing.Point(this.XMov[1],this.YMov[1])};
			}
		}

		#region USED IN DEBUG MODE
		static string ShowBoardPosition(BoardPosition[][] b)
		{
			string mov = ""+b.Length+"\n";
			foreach(BoardPosition[] p in b)
				mov+= ShowPath(p) +"\n";
			return mov;
		}

		static string ShowPath(BoardPosition[] dest)
		{
			string mov = "";
			foreach (BoardPosition p in dest)
				mov += "["+p.X +","+p.Y+"],";				
			return mov;
		}
		#endregion
	}

	public class Queen: CheckersPiece 
	{
		static System.Drawing.Point[] Inc = new System.Drawing.Point[] {
				new System.Drawing.Point(-1,-1),
				new System.Drawing.Point(-1, 1),
				new System.Drawing.Point( 1,-1),
				new System.Drawing.Point( 1, 1)
		};

		ArrayList aux;
		int orgX, orgY;
        public static bool AmericanRules = false;
	    
		protected void EatMoves(int x, int y, ArrayList moves)
		{
			bool foodFound=false;

			aux.Add(new BoardPosition(x, y));

			for(int i=0; i<4; i++)
			{
			    //Initializing...
			    int newX=x+Inc[i].X;
			    int newY=y+Inc[i].Y;

			    //Looking for piece...
			    while(this.ParentBoard.isInsideBoard(newX, newY) &&
			          this.ParentBoard.GetPieceAt(newX, newY)==null)
			    {
			        newX+=Inc[i].X;
			        newY+=Inc[i].Y;
			    }
			   

                if (this.ParentBoard.isInsideBoard(newX, newY) )
                {
                    CheckersPiece piece = this.ParentBoard.GetPieceAt(newX, newY) as CheckersPiece;
                    if (piece.Color != this.Color)
                    {
                        //piece found...
                        int newX2 = newX + Inc[i].X;
                        int newY2 = newY + Inc[i].Y; 
                        int dx = Math.Abs(newX2 - x);
			            int dy = Math.Abs(newY2 - y);
                        while (this.ParentBoard.isInsideBoard(newX2, newY2) &&
                               this.ParentBoard.GetPieceAt(newX2, newY2) == null && ((AmericanRules && (dx + dy == 4)) || (!AmericanRules)))
                        {
                            foodFound = true;

                            this.ParentBoard.RemovePiece(this);
                            this.ParentBoard.PutPieceAt(newX2, newY2, this);
                            this.ParentBoard.RemovePiece(piece);

                            EatMoves(newX2, newY2, moves);

                            this.ParentBoard.PutPieceAt(newX, newY, piece);
                            this.ParentBoard.RemovePiece(this);
                            this.ParentBoard.PutPieceAt(x, y, this);

                            newX2 += Inc[i].X;
                            newY2 += Inc[i].Y;
                        }
                    }
                }
			}

			if(!foodFound && (orgX!=x || orgY!=y))
			{
				BoardPosition[] arr=new BoardPosition[aux.Count];
				for(int z=0; z<aux.Count; z++)
					arr[z]=aux[z] as BoardPosition;

				moves.Add(new CheckersMove(arr, true));
			}

			aux.RemoveAt(aux.Count-1);
		}

		protected void EatMoves(ArrayList moves)
		{
			orgX=this.X;
			orgY=this.Y;
			aux=new ArrayList();
			EatMoves(this.X, this.Y, moves);
		}

		protected void SingleMoves(ArrayList moves)
		{
			for(int i=0; i<4; i++)
			{
				int newX=this.X+Inc[i].X;
				int newY=this.Y+Inc[i].Y;
				while(this.ParentBoard.isInsideBoard(newX, newY) &&
					this.ParentBoard.GetPieceAt(newX, newY)==null)
				{
					moves.Add(
						new CheckersMove(
							new BoardPosition[]{
							   new BoardPosition(this.X, this.Y),
							   new BoardPosition(newX, newY)
							},
							false
						)
					);
                    if (AmericanRules) break;
					newX+=Inc[i].X;
					newY+=Inc[i].Y;	
				}
			}
		}

		public override ArrayList PossibleMoves
		{
			get
			{
				ArrayList moves=new ArrayList();
				EatMoves(moves);
				if(moves.Count==0)
					SingleMoves(moves);
				else
				{
					int max=0;
					for(int j=0; j<moves.Count; j++)
					{
						CheckersMove move=moves[j] as CheckersMove;
						if(move.MovePath.Length>max)
							max=move.MovePath.Length;
					}
					for(int k=0; k<moves.Count; k++)
						if(((CheckersMove)moves[k]).MovePath.Length!=max)
							moves.RemoveAt(k--);
				}
				return moves;
			}
		}

		protected override System.Drawing.Point[] IncMov 
		{
			get 
			{
				return Queen.Inc;
			}
		}

		public Queen(CheckersBoard board,int x,int y,PieceColor color) : base(board,x,y,color) 
		{
			
		}
		
		public override bool CanEat(CheckersPiece piece) 
		{
			if (piece==null) return false;
			BoardPosition[][] possiblePos = this.PossiblePaths;
			for(int i =0; i<IncMov.Length; i++)
			{
				BoardPosition p = new BoardPosition(piece.X+IncMov[i].X, piece.Y+IncMov[i].Y);
				if (this._ParentBoard.isInsideBoard(p.X, p.Y) && this._ParentBoard.isEmptyCell(p.X, p.Y) && CanMoveTo(p.X, p.Y, possiblePos)) return true;
			}
			return false;

			// ALGORITMO a IMPLEMENTAR: Muy similar al CanMoveTo(int, int, bool), pero buscando la pieza que te vas a comer
		}

		public override bool CanMoveTo(int newx, int newy) 
		{
			return this.CanMoveTo(newx, newy, this.PossiblePaths);

			/*******************El siguiente codigo no se ha probado aun *******************************/
			//			return this.CanMoveTo(newx, newy,false);
		}
		
		public override bool CanMakeMove(CheckersMove move) 
		{
			BoardPosition[][] posiblePositions = this.PossiblePaths;
						
			foreach (BoardPosition[] path in posiblePositions)
			{
				if (path!=null && IsIncluded(move.MovePath,path)) return true;
			}			
			return false;

			/***************** El siguiente codigo no esta terminado aun ************
			 * *************** Estaria sustituyendo al codigo de arriba *************/
			//Algoritmo: Ciclo por los movimientos simulando moverse para ver si es valido
			//
			//			if ( move==null || move.MovePath==null || move.MovePath.Length==0 || 
			//				!(this.X==move.MovePath[0].X && this.Y==move.MovePath[0].Y) ) return false;
			//			int dx = 0;
			//			int dy = 0;
			//			BoardPosition p = null;
			//			BoardPosition myPos = new BoardPosition(this.X,this.Y);
			//
			//			for(int i =0; i<move.MovePath.Length; i++){
			//				p = move.MovePath[i];
			//				dx = Math.Sign(p.X-this.X);
			//				dy = Math.Sign(p.Y=this.Y);
			//				bool found = false;
			//
			//				BoardPosition f = this.FoundInDirecction(p.X, p.Y,new System.Drawing.Point(dx, dy),found);
			//				if (!found){
			//					//Pare la busqueda en esa direccion porque encontre otra ficha
			//					f = (f!=null) 
			//						? (new BoardPosition(this.X+dx, this.Y+dy))
			//						: (new BoardPosition(f.X+dx, f.Y+dy));
			//					
			//					//?????
			//					if (!this._ParentBoard.isInsideBoard(f.X,f.Y) || ) continue;
			//					
			//					CheckersPiece piece = this._ParentBoard.GetPieceAt(f.X, f.Y) as CheckersPiece;
			//						
			//					//La pieza es de color contrario, intentare comer
			//					if (piece.Color!=this.Color){
			//						BoardPosition c = new BoardPosition(f.X+IncMov[i].X, f.Y+IncMov[i].Y);
			//						
			//						if ((this._ParentBoard.isInsideBoard(c.X, c.Y) && this._ParentBoard.isEmptyCell(c.X, c.Y))){
			//							// Me puedo comer a 'piece'
			//				
			//				}
			//				
			//				BoardPosition c = new BoardPosition(f.X+IncMov[i].X, f.Y+IncMov[i].Y);
			//				
			//			}
		}
	
		#region UTILS

		protected override System.Collections.ArrayList MovementInDirection(System.Drawing.Point increment ,ref bool outOfBoard)
		{
			System.Collections.ArrayList path = new System.Collections.ArrayList();
			int top = Math.Min((Math.Sign(increment.X)<0)?this.X:(this._ParentBoard.Width-this.X) , (Math.Sign(increment.Y)<0)?this.Y:(this._ParentBoard.Height-this.Y));
			bool foundPiece = false;
			BoardPosition pos = null;
			
			for(int i=1; i<=top; i++)
			{
				pos = new BoardPosition(this.X+i*increment.X,this.Y+i*increment.Y);
				if (this._ParentBoard.isInsideBoard(pos.X,pos.Y)) 
				{
					if(!this._ParentBoard.isEmptyCell(pos.X,pos.Y))
					{
						foundPiece = true;
						break;
					}   
					path.Add(pos);
				}
			}
			outOfBoard = !foundPiece;
			return path;
		}

	
		/***************************************/
	
		protected static bool IsIncluded(BoardPosition[] source, BoardPosition[] dest)
		{
			if (source==null || source.Length==0 || dest==null) return false;
			int startPos = 0;
			bool found = false;
			while (!found && startPos<dest.Length)
			{
				if (BoardPosition.Equals(dest[startPos++],source[0]))
					found = true;	
			}
			//No encontre la primera coincidencia o los BoardPosition restantes son menos de los que estoy buscando
			if (!found || ((dest.Length-startPos)<(source.Length-1))) return false;

			if (source.Length==1) return true;

			int i=1; 
			while(i<source.Length && startPos<dest.Length)
				if (BoardPosition.Equals(source[i],dest[startPos++])) i++;
				
			return (i>=source.Length);
		}

		
		protected virtual bool CanMoveTo(int newx, int newy, BoardPosition[][] posiblePositions) 
		{
			if (!this._ParentBoard.isInsideBoard(newx, newy)) return false;
			
			foreach (BoardPosition[] path in posiblePositions)
			{
				if (path!=null)
				{
					for(int i=0; i<path.Length; i++)
						if (path[i].X==newx && path[i].Y==newy) return true;
				}
			}
			return false;
		}

		
		protected virtual bool CanMoveTo(int newx, int newy, bool eat) 
		{
			for(int i=0; i<IncMov.Length; i++)
			{
				bool found = false;
				BoardPosition f = FoundInDirecction(newx, newy, IncMov[i],ref found);
				if (found) return true;
				
				//Pare la busqueda en esa direccion porque encontre otra ficha
				f = (f!=null) 
					? (new BoardPosition(this.X+IncMov[i].X, this.Y+IncMov[i].Y))
					: (new BoardPosition(f.X+IncMov[i].X, f.Y+IncMov[i].Y));
					
				if (!this._ParentBoard.isInsideBoard(f.X,f.Y)) continue;
				CheckersPiece piece = this._ParentBoard.GetPieceAt(f.X, f.Y) as CheckersPiece;
						
				//La pieza es de color contrario, intentare comer
				if (piece.Color!=this.Color)
				{
					BoardPosition c = new BoardPosition(f.X+IncMov[i].X, f.Y+IncMov[i].Y);
						
					if ((this._ParentBoard.isInsideBoard(c.X, c.Y) && this._ParentBoard.isEmptyCell(c.X, c.Y)))
					{
						// Me puedo comer a 'piece'
						this._ParentBoard.RemovePiece(f);
						BoardPosition myPosition = new BoardPosition(this.X, this.Y);
						this._ParentBoard.MovePieceTo(this, c.X,c.Y);
								
						//Llamo recursivo y construyo mi solucion
						if (this.CanMoveTo(newx, newy ,true))return true;
										
						//Restauro mi posicion y la de 'piece' BACKTRACK!!!
						this._ParentBoard.MovePieceTo(this, myPosition.X, myPosition.Y);
						this._ParentBoard.PutPieceAt(f.X, f.Y,piece);
					}
				}//pieza de color contrario
			}//for
			
			return false;
		}

		
		protected BoardPosition FoundInDirecction(int X, int Y, System.Drawing.Point increment, ref bool found)
		{
			int top = Math.Min((Math.Sign(increment.X)<0)?this.X:(this._ParentBoard.Width-this.X) , (Math.Sign(increment.Y)<0)?this.Y:(this._ParentBoard.Height-this.Y));
			BoardPosition pos = null;
			
			for(int i=1; i<=top; i++)
			{
				pos = new BoardPosition(this.X+i*increment.X,this.Y+i*increment.Y);
				if (this._ParentBoard.isInsideBoard(pos.X,pos.Y) && this._ParentBoard.isEmptyCell(pos.X, pos.Y))
				{
					if (pos.X==X && pos.Y==Y) 
					{
						found =true;
						return null;
					}
				}
				else 
				{
					found = false;
					return (this._ParentBoard.isInsideBoard(pos.X,pos.Y)) ? pos : null;
				}
			}
			return null;
		}

		
		#region USED IN DEBUG MODE
		static string ShowBoardPosition(BoardPosition[][] b)
		{
			string mov = ""+b.Length+"\n";
			foreach(BoardPosition[] p in b)
				mov+= ShowPath(p) +"\n";
			return mov;
		}

		static string ShowPath(BoardPosition[] dest)
		{
			string mov = "";
			foreach (BoardPosition p in dest)
				mov += "["+p.X +","+p.Y+"],";				
			return mov;
		}
		#endregion
		
		/**************************************/
		#endregion
		public override object Clone() 
		{
			return new Queen((CheckersBoard)this.ParentBoard, this.X, this.Y, this.Color);
		}

	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

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

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

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