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 CPOL
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
Checkers.csdproj
Checkers.csdproj.user
Checkers.csproj.user
checkersico.ico
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
using System;
using GamesPackage;
using BoardEngine;
using System.Collections;

namespace Checkers
{
	
	public abstract class CheckersPiece : Piece 
	{
		protected PieceColor _Color;
		public PieceColor Color 
		{
			get 
			{
				return _Color;
			}
			set 
			{
				_Color = value;
			}
		}

	
		public CheckersPiece(CheckersBoard board,int x,int y,PieceColor color) : base(board,x,y) 
		{
			this._Color = color;
			
		}
	
		/// <summary>
		/// When overriden on a derivated class should return if the give piece can be eaten by this piece or not 
		/// </summary>
		/// <param name="piece"></param>
		/// <returns></returns>
		public abstract bool CanEat(CheckersPiece piece);

		public abstract bool CanMakeMove(CheckersMove move);

		public abstract ArrayList PossibleMoves
		{
			get;
		}
		
		#region PossiblePaths

		protected abstract System.Drawing.Point[] IncMov {get;}

		public virtual BoardPosition[][] PossiblePaths 
		{
			get 
			{
				ArrayList listToFill = this.PossibleMovements(false);
				
				BoardPosition[][] bps = new BoardPosition[listToFill.Count][];
				for(int i=0; i<listToFill.Count; i++)
					bps[i] = (BoardPosition[])(((ArrayList)listToFill[i]).ToArray(typeof(BoardPosition)));
				return bps;
			}
		}

		
		/*
		* Para cada una de las 4 posibles direcciones en que puedo moverme:
		*	-	Me muevo en esa direccion hasta que se salga del tablero, o hasta que se encuentre una ficha.
		*	-	Si pare porque me sali del tablero
		*		-	(1): Si no habia comido antes, entonces encontre el camino maximo en esa direccion [BINGO :-)]
		*				 En caso contrario desecho el camino (si ya habia comido antes, no puedo moverte ahora sin comer)[FAIL :-(]
		*	-	Si pare porque encontre otra ficha
		*		-	Calculo la casilla de la otra ficha (sea F esa casilla)
		*		-	(2): Calculo el maximo camino en esa direccion hasta la casilla anterior a F, pero teniendo en cuenta la restriccion (1) [BINGO ?]
		*		-	Si la ficha de F es de color contrario,
		*			-	Calculo la casilla que viene detras de la casilla F en esa misma direccion (sea C esa casilla)	
		*			-	Si C esta dentro del tablero y esta vacia
		*				-	Simulo comerme la pieza de F
		*				-	Simulo moverme para la casilla C
		*				-	Llamo recursivo a partir de C, teniendo en cuenta que ya comi. 
		*				-	Contruyo las soluciones teniendo en cuenta el resultado del llamado recursivo
		*				-	Restauro mi posicion
		*				-	Restauro la pieza que quite de F
		* Finalmente retorno todos los caminos que pude construir
		* */
		protected ArrayList PossibleMovements(bool eat)
		{
			int countMovement = 0;
			ArrayList listToFill = new ArrayList();

			for(int i=0; i<IncMov.Length; i++)
			{
				bool outOfBoard = false;
				ArrayList path = MovementInDirection(IncMov[i],ref outOfBoard);
				
				//Restriccion (1) : Camino limpio de fichas
				if (!eat && path!=null && path.Count>0)
					this.Restriction1(listToFill,path,new BoardPosition(this.X, this.Y),ref countMovement);
				if(outOfBoard)	continue;
								
				//Pare la busqueda en esa direccion porque encontre otra ficha
				if (!outOfBoard && path!=null)
				{
					BoardPosition f = (path.Count==0) 
						? (new BoardPosition(this.X+IncMov[i].X, this.Y+IncMov[i].Y))
						: (new BoardPosition(((BoardPosition)path[path.Count-1]).X+IncMov[i].X, ((BoardPosition)path[path.Count-1]).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
							ArrayList tmp = this.PossibleMovements(true);
							this.ConfigurePath(tmp, myPosition);
							foreach(ArrayList al in tmp) listToFill.Add(al);
										
							//Restauro mi posicion y la de 'piece' BACKTRACK!!!
							this._ParentBoard.MovePieceTo(this, myPosition.X, myPosition.Y);
							this._ParentBoard.PutPieceAt(f.X, f.Y,piece);

							countMovement = (tmp.Count>0) ? countMovement+1 : countMovement;
							continue;
						}
					}//pieza de color contrario
				}//Se encontro otra ficha			
			}//for

			if (countMovement==0)
				listToFill.Add(new ArrayList(new BoardPosition[]{new BoardPosition(this.X, this.Y)}));

			return listToFill;
		}

		
		protected abstract System.Collections.ArrayList MovementInDirection(System.Drawing.Point increment ,ref bool outOfBoard);
			
		protected virtual void ConfigurePath(ArrayList listToFill, BoardPosition p)
		{
			if (listToFill!=null)
			{
				for(int i=0; i<listToFill.Count; i++)
				{
					ArrayList al = listToFill[i] as ArrayList;
					if (al!=null)
						al.Insert(0,p);
				}
			}
		}

		
		private void Restriction1(ArrayList listToFill, ArrayList path, BoardPosition p, ref int countMovement)
		{
			ArrayList list = null;
			for(int i=0; i<path.Count; i++)
			{
				list = new ArrayList();
				list.Add(p);
				list.Add(path[i]);
				listToFill.Add(list);
			}
			//			path.Insert(0,p);
			//			lisToFill.Add(path);
			countMovement++ ;
		}

		
		#endregion PossiblePaths

	}

	public class CheckersBoard : Board,IGameStateForPlayer,IGameState
	{
		#region private and protected variables
		
		internal ArrayList BlackPiecesList = new ArrayList(12);
		internal ArrayList WhitePiecesList = new ArrayList(12);


		#endregion

		public CheckersBoard() : base(8,8) 
		{
		}

		public ArrayList RightMoves(PieceColor color)
		{
			System.Collections.ArrayList moves=new System.Collections.ArrayList();
			System.Collections.ArrayList moves2=new System.Collections.ArrayList();
 
			//getting all the moves
			bool eatMove=false;
			int length=0;

			for(int x=0; x<this.Width; x++)
				for(int y=0; y<this.Height; y++) {
					CheckersPiece piece=this.GetPieceAt(x, y) as CheckersPiece;
					if(piece!=null && piece.Color==color)
						foreach(CheckersMove move in piece.PossibleMoves) {
							moves.Add(move);
							if(move.EatMove)
								eatMove=move.EatMove;
							if(move.MovePath.Length>length)
								length=move.MovePath.Length;
						}
				}

			//looking for right moves...
			for(int l=0; l<moves.Count; l++) {
				CheckersMove m2=moves[l] as CheckersMove;
				if(m2!=null && eatMove==m2.EatMove && length==m2.MovePath.Length)
					moves2.Add(m2);
			}
			return moves2;
		}

		/// <summary>
		/// Clear all the boardm including the move's log
		/// </summary>
		public void Clear() 
		{
			WhitePiecesList.Clear();
			BlackPiecesList.Clear();
			_BoardMatrix = new Piece[8,8];
		}

		public override void InitializeBoard()
		{
			this.Clear();
			
			for(int i=0 ; i<8 ; i++) 
			{
				for(int j=0; j < 8; j++ )
				{
					bool xeven = (i % 2 == 0);
					bool yeven = (j % 2 == 0);
					if (!(xeven ^ yeven))
					{
						if (j<=2) PutPieceAt(i,j,new Pawn(this,i,j,PieceColor.Black));
						else if(j>=5) PutPieceAt(i,j,new Pawn(this,i,j,PieceColor.White));
					}
				}
			}


		}
		
		public object Clone() {			
			CheckersBoard newBoard=new CheckersBoard();
			for(int x=0; x<newBoard.Width; x++)
				for(int y=0; y<newBoard.Height; y++) {
					CheckersPiece piece=this.GetPieceAt(x, y) as CheckersPiece;
					if(piece!=null) {
						CheckersPiece clone=(CheckersPiece)piece.Clone();
						newBoard.PutPieceAt(x, y, clone);
					}
				}
			return newBoard;
		}

		public override string ToString()
		{
			string s="";
			foreach(CheckersPiece piece in WhitePiecesList) {
				s+="w"+piece.ToString();
			}
				s+='\n';

			foreach(CheckersPiece piece in BlackPiecesList) {
				s+="b"+piece.ToString();
			}
			
			return s;
		}

		public override bool Equals(object obj) {
			CheckersBoard other = (CheckersBoard)obj;
			return (this.ToString().Equals(other.ToString()));
		}

	}
	
}

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)

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

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