Future mobility of chess pieces
I am currently developing a chess engine in C# and I have hit a bit of a brick wall in developing the code to determine future mobility of any given chess piece in 1, 2 and 3 moves. The basic idea is to reward pieces with a bonus for increased mobility and penalise pieces with less mobility.
The chess board is represented as an array of 64 squares, starting from 0 (a8) through 63 (h1), eg
Piece[] _chessboard = new Piece[64];
I am using this chess board position as an example:
Black Rooks on squares 3 & 19 (d8 & d6) Black King on square 5 (f8) Black Knight on squares 11 & 12 (d7 & e7) Black Queen on square 16 (a6) Black Pawns on squares 13, 14, 17, 18, 19 (f7, g7, b6 & c6) White Rook on squares 58 & 42 (c1 & c3) White King on square 53 (f2) White Knight on square 40 (a3) White Bishop on square 41 (b3) White Pawns on squares 32, 35, 36, 37, 38 & 31 (a4, d4, e4, f4, g4 & h5)
Here is the FEN string for the same position: 3r1k2/3nnpp1/qppr3P/P6P/P2PPPP1/NBR5/5K2/2R5
After several failed attempts I have come up with the following data structure (Linked List?) that I hope is the best way of tracing mobility through squares.
+--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 25 | 2 | | 25 | 34 | 16 | 3 | +--------+-------------+-----------+-------+
What this structure tells me is the White Bishop on square 41 goes to square 34 in 1 move, then square 25 in 2 moves and square 16 in 3 moves. The above structure is populated using a recursive function that traverses all possible squares that the Bishop can move to in 1, 2 & 3 moves. The problem with this is that all inefficient moves will be recorded and these need to be detected and deleted before being replaced by more efficient moves.
For example, moving from square 41 to 16 in 3 moves via squares 34 and 25 is not efficient because it is possible to move to square 16 in 2 moves; 41 to 34 in 1 move then 34 to 16 in 2 moves. I require the recursive function to detect these inefficient moves and delete them before adding the new efficient move to the data structure.
I need the recursive function to execute very fast as it will be used by the evaluation function to search for the best move in a given position.
What I am looking for is some code that will query (possibly using LINQ?) the data structure above to return a list of the inefficient moves from the above data structure so they can be removed, eg
IEnumerable<MoveNode> _moves = new List<MoveNode>();
function void AddMove( int from, int to, int depth )
{
// locate the inefficient moves that need to be deleted
IEnumerable<MoveNode> list_of_moves_to_delete = find_moves( from, to, depth );
if ( list_of_moves_to_delete.Any() )
{
_moves.RemoveAll( list_of_moves_to_delete );
}
// then add the more efficient move
_moves.Add( new MoveNode( from, to, depth ) );
}
function IEnumerable<MoveNode> find_moves( int from, int to, int depth )
{
// TODO: return a list of moves that are inefficient; moves
// that need to be deleted and replaced by efficient
// moves.
}
// Sample calling code (adds the inefficient moves)...
AddMove( 41, 34, 1 );
AddMove( 34, 25, 2 );
AddMove( 25, 16, 3 );
// This one is for the efficient moves...
AddMove( 41, 34, 1 );
AddMove( 34, 16, 2 ); // when this is called it should find the inefficient moves
// and remove them first before adding this move
This is just a sample and it probably won't compile; I'm hoping there is some wizard out there who can help me out here and code the find_moves function so that is correctly returns the inefficient moves as I am not sure how to go about doing this.
I hope I have managed to clearly explain everything here.
Thanks!
** EDIT **
Considering that nobody has posted any suggestions I will try and simplify things a bit. I am looking for an algorithm that will be used to update a data structure (similar to the one given above) that contains the most efficient moves between squares on a chess board, that is all I am looking for.
For example:
Say I have these moves generated recursively for a White Bishop on square 41 (b3); in 1 move it can go from 41 to 34 (b3-c4), then in 2 moves from 34 to 27 (c4-d5) and finally from 27 to 20 (d5-e6) in 3 moves.
This means it has taken 3 moves to get from square 41 to 20 via 34 and 27, however once the recursive function starts to process the more efficient moves it will need to search the data structure for the inefficient moves and delete them.
It would be great if it was possible to do something like this:
Replace these entries: +--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 25 | 2 | | 25 | 34 | 16 | 3 | +--------+-------------+-----------+-------+ With this: +--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 16 | 2 | +--------+-------------+-----------+-------+ After processing 41-34-16 in 2 moves.
** Edit 2 **
After some analysis and development of a possible solution I think that I may have cracked it by adopting a different data structure to the one given above.
Here is the solution so far -- all critique is welcome to try and improve this version as much as possible.
public class MoveNode
{
public Guid Id;
public int DepthLevel;
public int Node0Ref;
public int Node1Ref;
public int Node2Ref;
public int Node3Ref;
public MoveNode()
{
Id = Guid.NewGuid();
}
// Copy constructor
public MoveNode( MoveNode node )
: this()
{
if ( node != null )
{
this.Node0Ref = node.Node0Ref;
this.Node1Ref = node.Node1Ref;
this.Node2Ref = node.Node2Ref;
this.Node3Ref = node.Node3Ref;
}
}
}
class Program
{
static List<MoveNode> _nodes = new List<MoveNode>();
static IQueryable<MoveNode> getNodes()
{
return _nodes.AsQueryable();
}
static void Main( string[] args )
{
MoveNode parent = null;
// Simulates a recursive pattern for the following moves:
//
// 41 -> 34 (1)
// 34 -> 27 (2)
// 27 -> 20 (3)
// 27 -> 13 (3)
// 34 -> 20 (2)
// 34 -> 13 (2)
// 41 -> 27 (1)
// 27 -> 20 (2)
// 20 -> 13 (3)
// 41 -> 20 (1)
// 20 -> 13 (2)
// 41 -> 13 (1)
//
parent = addMove( null, 41, 34, 1 );
parent = addMove( parent, 34, 27, 2 );
parent = addMove( parent, 27, 20, 3 );
parent = addMove( parent, 27, 13, 3 );
parent = addMove( _nodes[ 0 ], 34, 20, 2 );
parent = addMove( _nodes[ 0 ], 34, 13, 2 );
parent = addMove( null, 41, 27, 1 );
parent = addMove( parent, 27, 20, 2 );
parent = addMove( parent, 20, 13, 3 );
parent = addMove( null, 41, 20, 1 );
parent = addMove( parent, 20, 13, 2 );
parent = addMove( null, 41, 13, 1 );
StringBuilder validMoves = new StringBuilder();
StringBuilder sb = new StringBuilder();
sb.Append( "+--------+---------+---------+---------+---------+n" );
sb.Append( "| Depth | Node 0 | Node 1 | Node 2 | Node 3 |n" );
sb.Append( "+--------+---------+---------+---------+---------+n" );
foreach ( MoveNode node in getNodes() )
{
sb.AppendFormat( "| {0,2} | {1,3} | {2,3} | {3,3} | {4,3} |n", node.DepthLevel, node.Node0Ref, node.Node1Ref, node.Node2Ref, node.Node3Ref );
if ( node.DepthLevel == 1 )
validMoves.AppendFormat( "{0}n", convertToBoardPosition( node.Node0Ref, node.Node1Ref ) );
else if ( node.DepthLevel == 2 )
validMoves.AppendFormat( "{0}n", convertToBoardPosition( node.Node1Ref, node.Node2Ref ) );
else if ( node.DepthLevel == 3 )
validMoves.AppendFormat( "{0}n", convertToBoardPosition( node.Node2Ref, node.Node3Ref ) );
}
sb.Append( "+--------+---------+---------+---------+---------+n" );
Console.WriteLine( sb.ToString() );
Console.WriteLine( "List of efficient moves:" );
Console.WriteLine( validMoves.ToString() );
Console.WriteLine( "Press any key to exit." );
Console.ReadKey();
}
static MoveNode addMove( MoveNode parent, int from, int to, int depthLevel )
{
MoveNode node = null;
var inefficientMoves = getNodesToBeRemoved( from, to, depthLevel );
if ( inefficientMoves.Any() )
{
// remove them...
HashSet<Guid> ids = new HashSet<Guid>( inefficientMoves.Select( x => x.Id ) );
_nodes.RemoveAll( x => ids.Contains( x.Id ) );
}
node = new MoveNode( parent );
node.DepthLevel = depthLevel;
if ( depthLevel == 1 )
{
node.Node0Ref = from;
node.Node1Ref = to;
}
else if ( depthLevel == 2 )
{
node.Node1Ref = from;
node.Node2Ref = to;
}
else if ( depthLevel == 3 )
{
node.Node2Ref = from;
node.Node3Ref = to;
}
_nodes.Add( node );
return node;
}
static IEnumerable<MoveNode> getNodesToBeRemoved( int from, int to, int depth )
{
var predicate = PredicateBuilder.True<MoveNode>();
if ( depth == 1 )
predicate = predicate.And( p => p.Node0Ref == from );
else if ( depth == 2 )
predicate = predicate.And( p => p.Node1Ref == from );
else if ( depth == 3 )
predicate = predicate.And( p => p.Node2Ref == from );
predicate = predicate
.And( a => a.Node1Ref == to )
.Or( a => a.Node2Ref == to )
.Or( a => a.Node3Ref == to );
return getNodes().Where( predicate );
}
static string convertToBoardPosition( int from, int to )
{
string a = Convert.ToChar( 97 + file( from ) ) + Convert.ToString( rank( from ) );
string b = Convert.ToChar( 97 + file( to ) ) + Convert.ToString( rank( to ) );
return a + '-' + b;
}
static int file( int x )
{
return ( x & 7 );
}
static int rank( int x )
{
return 8 - ( x >> 3 );
}
}
I am not sure about copyright rules regarding copying & pasting somebody else's code so you'll need to download the PredicateBuilder source code from here in order to run my code.
The code above will produce the following output:
+--------+---------+---------+---------+---------+ | Depth | Node 0 | Node 1 | Node 2 | Node 3 | +--------+---------+---------+---------+---------+ | 1 | 41 | 34 | 0 | 0 | | 1 | 41 | 27 | 0 | 0 | | 1 | 41 | 20 | 0 | 0 | | 1 | 41 | 13 | 0 | 0 | +--------+---------+---------+---------+---------+ List of efficient moves: b3-c4 b3-d5 b3-e6 b3-f7 Press any key to exit.
I think you're going about this backwards. You simply don't need to prune the inefficient moves at each step. The recursive way that you have come up with for doing so is elegant but will never be efficient.
You should simply generate a list of all the squares you can reach in one move. Then generate a list of all the squares you can reach in at most two moves. There is an easy way of doing this - take all the squares in the previous list and find all the squares that can be reached from them in one move. Combine all these lists with the original list, removing repetitions. Then find all the squares you can reach in three moves. Again, remove repetitions, but don't worry that you have included 'inefficient squares', that is to say, ones which are in the one-move or two-moves lists. You want to include everything in the first two lists.
Now, if you only want numbers of squares, you can get them very quickly just by calculating. The number of squares that can be reached in three moves or less is the length of the last list. The number of squares that can be reached in two moves or less is the length of the second list. Therefore the difference between these is the number of squares that can be reached in exactly three moves.
If you happen to want the list of squares that can be reached in exactly three, you can use the efficient LINQ function Except at this point.
BTW, this question would be a great fit for codereview.stackexchange.com, since it's more about already written code that you want to improve than a specific issue with a language or technology.
Sounds like an interesting approach... I think that most engines just use an approximation for this (such as giving piece values a bonus for central placement), as computing it directly is too expensive, and the extra cycles are better spent on searching further ahead.
Here's my attempt at a pseudo-implementation below, I couldn't fully understand your data structures, so this will obviously need heavy modification, oh and it's not LINQ at all, sorry about that:
///<summary>After calling with recurseDepth = 0 initially, reachedSquares will afterwards hold a number of key-value
/// pairs indicating the minimum number of moves required to reach that square from the initial startSquare.</summary>
void FindPathableSquares(int recurseDepth, Dictionary<int, int> reachedSquares, int startSquare){
reachedSquares[startSquare] = recurseDepth
// Can't reach all squares with most pieces. Would suggest at *most* 3 for this constant.
if(recurseDepth >= MAX_RECURSE_DEPTH)
return;
// Appropriate move generation algorithm here.
// Presumably you have some board state reference in scope.
var reachable = GenerateMoves(startSquare);
foreach(int mv in reachable){
// Skip nodes already found. Interesting alternative, perhaps multiple paths to a square are
// useful, in which case reward this in the evaluation somehow.
if(reachedSquares.ContainsKey(mv))
continue;
FindPathableSquares(recurseDepth + 1, reachedSquares, mv);
}
}
Good luck, and hope it turns out to be a worthy opponent.
Using the suggestion given by jwg I think I've managed to calculate all potential moves in 1, 2 and 3 moves for a given piece on a square.
Here is the sample code for those who are interested -- it uses the board sample given in the original post and calculates the potential future mobility of the White Bishop on square b3. Whether it's correct I am not sure yet so I'm going to have to verify the results for accuracy.
public enum PieceType
{
Empty = 0,
WhitePawn = 1,
WhiteKnight = 2,
WhiteBishop = 3,
WhiteRook = 4,
WhiteQueen = 5,
WhiteKing = 6,
BlackPawn = 7,
BlackKnight = 8,
BlackBishop = 9,
BlackRook = 10,
BlackQueen = 11,
BlackKing = 12
}
public enum PieceColor
{
Unknown = -1,
Black = 0,
White = 1
}
public enum ContentType
{
NotInspected,
Empty,
BlockedFriendlyNotMoveable,
BlockedFriendlyMoveable,
BlockedCapturable,
}
public class Node
{
public List<Node> ReachableSquares = new List<Node>();
public int Square;
public int RecurseDepth;
public ContentType Content;
public Move FreeingMove;
public Node FreeingMoveNode;
public Node( int square )
{
Square = square;
}
}
[StructLayout( LayoutKind.Explicit )]
public struct Move
{
[FieldOffset( 0 )]
public MoveBytes b;
[FieldOffset( 0 )]
public int u;
}
public struct MoveBytes
{
public int from;
public int to;
public PieceType promote;
public sbyte bits;
}
public class FutureMove
{
public string Path;
public int Depth;
public ContentType Content;
public string PathIds;
}
public class ChessBoard
{
private PieceType[] _board = new PieceType[ 64 ];
public ChessBoard()
{
for ( int n = 0; n < 64; n++ )
_board[ n ] = PieceType.Empty;
}
public void SetupBoard( KeyValuePair<Int32, PieceType>[] pieces )
{
foreach ( var piece in pieces )
Set( piece.Value, piece.Key );
}
public void Set( PieceType pieceType, Int32 square )
{
checkSquareThrowExceptionIfInvalid( square );
_board[ square ] = pieceType;
}
public PieceType Get( Int32 square )
{
checkSquareThrowExceptionIfInvalid( square );
return _board[ square ];
}
public Boolean Is( PieceType pieceType, Int32 square )
{
return Get( square ) == pieceType;
}
public ContentType Inspect( int sourceSquare, int targetSquare, out Move move )
{
checkSquareThrowExceptionIfInvalid( sourceSquare );
checkSquareThrowExceptionIfInvalid( targetSquare );
move = new Move();
ContentType content = ContentType.NotInspected;
PieceType pieceOnTargetSquare = _board[ targetSquare ];
PieceType pieceOnSourceSquare = _board[ sourceSquare ];
PieceColor pieceColorOnTargetSquare = PieceColor.Unknown;
PieceColor pieceColorOnSourceSquare = PieceColor.Unknown;
if ( pieceOnTargetSquare == PieceType.BlackPawn || pieceOnTargetSquare == PieceType.BlackKnight || pieceOnTargetSquare == PieceType.BlackBishop || pieceOnTargetSquare == PieceType.BlackRook || pieceOnTargetSquare == PieceType.BlackQueen || pieceOnTargetSquare == PieceType.BlackKing )
pieceColorOnTargetSquare = PieceColor.Black;
else
pieceColorOnTargetSquare = PieceColor.White;
if ( pieceOnSourceSquare == PieceType.WhitePawn || pieceOnSourceSquare == PieceType.WhiteKnight || pieceOnSourceSquare == PieceType.WhiteBishop || pieceOnSourceSquare == PieceType.WhiteRook || pieceOnSourceSquare == PieceType.WhiteQueen || pieceOnSourceSquare == PieceType.WhiteKing )
pieceColorOnSourceSquare = PieceColor.White;
else
pieceColorOnSourceSquare = PieceColor.Black;
switch ( pieceOnTargetSquare )
{
case PieceType.Empty:
content = ContentType.Empty;
break;
case PieceType.WhitePawn:
bool captureLeft = pieceColorOnTargetSquare == PieceColor.Black && Common.File( targetSquare ) > 0 && InspectSquare( targetSquare - 9 ) != PieceType.Empty;
bool captureRight = pieceColorOnTargetSquare == PieceColor.Black && Common.File( targetSquare ) < 8 && InspectSquare( targetSquare - 7 ) != PieceType.Empty;
bool moveForwardOneSquare = Common.Rank( targetSquare ) != 2 && InspectSquare( targetSquare - 8 ) == PieceType.Empty;
bool moveForwardTwoSquares = Common.Rank( targetSquare ) == 2 && InspectSquare( targetSquare - 8 ) == PieceType.Empty;
if ( !captureLeft && !captureRight && !moveForwardOneSquare && !moveForwardTwoSquares )
content = ContentType.BlockedFriendlyNotMoveable;
else
{
move.b.from = targetSquare;
if ( moveForwardTwoSquares )
move.b.to = targetSquare - 16;
else if ( moveForwardOneSquare )
move.b.to = targetSquare - 8;
else if ( captureLeft )
move.b.to = targetSquare - 9;
else if ( captureRight )
move.b.to = targetSquare - 7;
content = ContentType.BlockedFriendlyMoveable;
}
break;
default:
if ( ( pieceColorOnSourceSquare == PieceColor.Black && pieceColorOnTargetSquare == PieceColor.White ) || ( pieceColorOnSourceSquare == PieceColor.White && pieceColorOnTargetSquare == PieceColor.Black ) )
content = ContentType.BlockedCapturable;
break;
}
return content;
}
public PieceType InspectSquare( int square )
{
return _board[ Common.GetMailboxAddress( square ) ];
}
public ChessBoard MakeMove( int from, int to )
{
ChessBoard newBoard = new ChessBoard();
for ( int n = 0; n < 64; n++ )
newBoard.Set( _board[ n ], n );
newBoard.Set( _board[ from ], to );
newBoard.Set( PieceType.Empty, from );
return newBoard;
}
public ChessBoard MakeMove( Move move )
{
return MakeMove( move.b.from, move.b.to );
}
public void DisplayBoard()
{
StringBuilder sb = new StringBuilder();
int rank = 8;
sb.Append( "+------------------------+" );
for ( int i = 0; i < 64; i++ )
{
if ( ( i & 7 ) == 0 )
{
sb.AppendLine();
sb.Append( rank );
rank--;
}
PieceType piece = Get( i );
if ( piece == PieceType.Empty )
{
sb.Append( " . " );
if ( ( i & 7 ) == 7 )
{
sb.Append( "|" );
}
continue;
}
switch ( piece )
{
case PieceType.WhitePawn:
sb.Append( " P " );
break;
case PieceType.WhiteKnight:
sb.Append( " N " );
break;
case PieceType.WhiteBishop:
sb.Append( " B " );
break;
case PieceType.WhiteRook:
sb.Append( " R " );
break;
case PieceType.WhiteQueen:
sb.Append( " Q " );
break;
case PieceType.WhiteKing:
sb.Append( " K " );
break;
case PieceType.BlackPawn:
sb.Append( " p " );
break;
case PieceType.BlackKnight:
sb.Append( " n " );
break;
case PieceType.BlackBishop:
sb.Append( " b " );
break;
case PieceType.BlackRook:
sb.Append( " r " );
break;
case PieceType.BlackQueen:
sb.Append( " q " );
break;
case PieceType.BlackKing:
sb.Append( " k " );
break;
}
if ( ( i & 7 ) == 7 )
{
sb.Append( "|" );
}
}
sb.AppendLine();
sb.Append( "+-a--b--c--d--e--f--g--h-+" );
Console.WriteLine( sb.ToString() );
}
#region Helper functions
private void checkSquareThrowExceptionIfInvalid( int square )
{
if ( square < 0 || square > 63 )
throw new ArgumentOutOfRangeException( "square" );
}
#endregion
}
public partial class ChessEngine
{
private const int PAWN_OFFSET_INDEXOR = 0;
private const int KNIGHT_OFFSET_INDEXOR = 1;
private const int BISHOP_OFFSET_INDEXOR = 2;
private const int ROOK_OFFSET_INDEXOR = 3;
private const int QUEEN_OFFSET_INDEXOR = 4;
private const int KING_OFFSET_INDEXOR = 5;
private const int MAX_RECURSE_DEPTH = 3;
/* slide, offsets, and offset are basically the vectors that
* pieces can move in. If slide for the piece is false, it can
* only move one square in any one direction. offsets is the
* number of directions it can move in, and offset is an array
* of the actual directions. */
private bool[] _slide = new bool[ 6 ] {
false, false, true, true, true, false
};
private int[] _offsets = new int[ 6 ] {
0, 8, 4, 4, 8, 8
};
private int[][] _offset = new int[ 6 ][] {
new int[] { 0, 0, 0, 0, 0, 0, 0, 0 }, /* pawns */
new int[] { -21, -19, -12, -8, 8, 12, 19, 21 },/* knights */
new int[] { -11, -9, 9, 11, 0, 0, 0, 0 }, /* bishops */
new int[] { -10, -1, 1, 10, 0, 0, 0, 0 }, /* rooks */
new int[] { -11, -10, -9, -1, 1, 9, 10, 11 }, /* queen */
new int[] { -11, -10, -9, -1, 1, 9, 10, 11 } /* king */
};
private Stack<ChessBoard> _boardHistory = new Stack<ChessBoard>();
public List<FutureMove> Calculate( ChessBoard board, int square )
{
Node root = new Node( square );
root.ReachableSquares = calculateReachableSquares( board, root, 0 );
foreach ( var node in root.ReachableSquares )
{
if ( node.Content != ContentType.Empty )
continue;
_boardHistory.Push( board );
var tempBoard = board.MakeMove( root.Square, node.Square );
var allReachableSquares = calculateReachableSquares( tempBoard, node, 1 );
node.ReachableSquares = RemoveDuplicateSquares( allReachableSquares, root.ReachableSquares );
foreach ( var innerNode in node.ReachableSquares )
{
if ( innerNode.Content != ContentType.Empty )
continue;
_boardHistory.Push( tempBoard );
tempBoard = tempBoard.MakeMove( node.Square, innerNode.Square );
allReachableSquares = calculateReachableSquares( tempBoard, innerNode, 2 );
innerNode.ReachableSquares = RemoveDuplicateSquares( allReachableSquares, node.ReachableSquares, root.ReachableSquares );
tempBoard = _boardHistory.Pop();
}
board = _boardHistory.Pop();
}
checkBoardHistoryEmptyThrowExceptionIfNot();
return getFutureMoves( root );
}
private List<Node> calculateReachableSquares( ChessBoard board, Node node, int recurseDepth )
{
if ( recurseDepth > MAX_RECURSE_DEPTH )
return null;
int indexor = -1;
switch ( board.Get( node.Square ) )
{
case PieceType.WhiteBishop:
case PieceType.BlackBishop:
indexor = BISHOP_OFFSET_INDEXOR;
break;
}
bool takeBackMove = false;
if ( indexor >= 0 )
{
for ( int j = 0; j < _offsets[ indexor ]; ++j )
{
for ( int n = node.Square; ; )
{
int oset = _offset[ indexor ][ j ];
n = Common.GetMailboxAddress( n, oset );
if ( n == -1 )
break;
Move move;
ContentType pieceOnSquare = board.Inspect( node.Square, n, out move );
if ( pieceOnSquare == ContentType.NotInspected )
throw new Exception( String.Format( "Unable to inspect square {0}", n ) );
Node newNode = new Node( n ) { Content = pieceOnSquare, RecurseDepth = recurseDepth + 1 };
if ( move.u > 0 )
newNode.FreeingMove = move;
node.ReachableSquares.Add( newNode );
// Do we need to move the piece out of the way?
if ( pieceOnSquare == ContentType.BlockedFriendlyMoveable && newNode.RecurseDepth < 3 )
{
// Yes, we do.
recurseDepth++;
// Put the current board on the stack to preserve state.
_boardHistory.Push( board );
// Make the move.
board = board.MakeMove( move );
pieceOnSquare = board.Inspect( node.Square, n, out move );
var freeingMoveNode = new Node( n ) { Content = pieceOnSquare, RecurseDepth = recurseDepth + 1 };
if ( move.u > 0 )
freeingMoveNode.FreeingMove = move;
freeingMoveNode.FreeingMoveNode = newNode;
node.ReachableSquares.Add( freeingMoveNode );
// Lets the method know we need to put the board back.
takeBackMove = true;
}
else if ( pieceOnSquare != ContentType.Empty )
break;
}
// Reverts to a previous board state.
if ( takeBackMove )
{
recurseDepth--;
takeBackMove = false;
board = _boardHistory.Pop();
}
}
}
return node.ReachableSquares;
}
/// <summary>
/// Compares <paramref name="firstList"/> with <paramref name="secondList"/> and
/// returns a list of squares that exist in both lists.
/// </summary>
static IEnumerable<int> Intersect( List<Node> firstList, List<Node> secondList )
{
return firstList.Select( a => a.Square )
.Intersect( secondList.Select( a => a.Square ) )
.ToList();
}
/// <summary>
/// Combines <paramref name="firstList"/> and <paramref name="secondList"/> to make a single list before
/// comparing the combined list with <paramref name="thirdList"/> returning a list of squares that in the
/// two lists.
/// </summary>
private IEnumerable<int> Intersect( List<Node> firstList, List<Node> secondList, List<Node> thirdList )
{
return firstList.Select( a => a.Square )
.Union( thirdList.Select( a => a.Square ) )
.Intersect( secondList.Union( firstList ).Select( a => a.Square ) )
.ToList();
}
/// <summary>
/// Looks for duplicates squares in <paramref name="originalList"/> and returns a new
/// List without these duplicates.
/// </summary>
private List<Node> RemoveDuplicateSquares( List<Node> originalList, List<Node> comparerList )
{
List<Node> newList = originalList.ToList();
IEnumerable<Int32> dups = Intersect( newList, comparerList );
newList.RemoveAll( a => dups.Contains( a.Square ) );
return newList;
}
/// <summary>
/// Looks for duplicates squares in <paramref name="originalList"/> and returns a new
/// List without these duplicates.
/// </summary>
private List<Node> RemoveDuplicateSquares( List<Node> originalList, List<Node> comparerList1, List<Node> comparerList2 )
{
List<Node> newList = originalList.ToList();
IEnumerable<Int32> dups = Intersect( comparerList1, comparerList2, newList );
newList.RemoveAll( a => dups.Contains( a.Square ) );
return newList;
}
private void checkBoardHistoryEmptyThrowExceptionIfNot()
{
// Must ensure the board history is empty before exiting.
if ( _boardHistory.Count > 0 )
throw new Exception( "Board stack not empty." );
}
private List<FutureMove> getFutureMoves( Node node )
{
return getFutureMoves( node, null, null );
}
private List<FutureMove> getFutureMoves( Node node, String path, String pathIds )
{
List<FutureMove> rows = new List<FutureMove>();
StringBuilder currentPath = new StringBuilder();
StringBuilder currentPathIds = new StringBuilder();
if ( path != null )
currentPath.AppendFormat( "{0}", path );
else
currentPath.AppendFormat( "{0}", Common.ConvertToBoardPosition( node.Square ) );
if ( pathIds != null )
currentPathIds.AppendFormat( "{0}", pathIds );
else
currentPathIds.AppendFormat( "{0}", node.Square );
foreach ( var n in node.ReachableSquares )
{
string temp = String.Format( "{0}-{1}", currentPath, Common.ConvertToBoardPosition( n.Square ) );
string tempPathIds = String.Format( "{0}-{1}", currentPathIds, n.Square );
if ( n.ReachableSquares.Any() )
{
rows.AddRange( getFutureMoves( n, temp, tempPathIds ) );
}
FutureMove fm = new FutureMove();
fm.Depth = n.RecurseDepth;
fm.Path = temp.ToString();
fm.PathIds = tempPathIds;
fm.Content = n.Content;
rows.Add( fm );
}
return rows;
}
}
public static class Common
{
static int[] _mailbox = new int[ 120 ] {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 0, 1, 2, 3, 4, 5, 6, 7, -1,
-1, 8, 9, 10, 11, 12, 13, 14, 15, -1,
-1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
-1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
-1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
-1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
-1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
-1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1
};
static int[] _mailbox64 = new int[ 64 ] {
21, 22, 23, 24, 25, 26, 27, 28,
31, 32, 33, 34, 35, 36, 37, 38,
41, 42, 43, 44, 45, 46, 47, 48,
51, 52, 53, 54, 55, 56, 57, 58,
61, 62, 63, 64, 65, 66, 67, 68,
71, 72, 73, 74, 75, 76, 77, 78,
81, 82, 83, 84, 85, 86, 87, 88,
91, 92, 93, 94, 95, 96, 97, 98
};
public static int GetMailboxAddress( int square )
{
return _mailbox[ _mailbox64[ square ] ];
}
public static int GetMailboxAddress( int square, int offset )
{
return _mailbox[ _mailbox64[ square ] + offset ];
}
public static string ConvertToBoardPosition( int from, int to )
{
string a = Convert.ToChar( 97 + File( from ) ) + Convert.ToString( Rank( from ) );
string b = Convert.ToChar( 97 + File( to ) ) + Convert.ToString( Rank( to ) );
return a + '-' + b;
}
public static string ConvertToBoardPosition( int square )
{
string a = Convert.ToChar( 97 + File( square ) ) + Convert.ToString( Rank( square ) );
return a;
}
public static int File( int x )
{
return ( x & 7 );
}
public static int Rank( int x )
{
return 8 - ( x >> 3 );
}
public static string ContentTypeValueToString( ContentType contentTypeEnumValue )
{
string contentTypeStr = string.Empty;
switch ( contentTypeEnumValue )
{
case ContentType.BlockedCapturable:
contentTypeStr = "Blocked, Capturable";
break;
case ContentType.BlockedFriendlyMoveable:
contentTypeStr = "Blocked, Friendly, Moveable";
break;
case ContentType.BlockedFriendlyNotMoveable:
contentTypeStr = "Blocked, Friendly, Not Moveable";
break;
case ContentType.Empty:
contentTypeStr = "Empty";
break;
default:
contentTypeStr = "Error!";
break;
}
return contentTypeStr;
}
}
// Main calling program
class Program
{
static void Main( string[] args )
{
ChessBoard cb = new ChessBoard();
cb.SetupBoard( new KeyValuePair<Int32, PieceType>[]
{
// Setup Black pieces
new KeyValuePair<Int32, PieceType>( 3, PieceType.BlackRook ),
new KeyValuePair<Int32, PieceType>( 5, PieceType.BlackKing ),
new KeyValuePair<Int32, PieceType>( 11, PieceType.BlackKnight ),
new KeyValuePair<Int32, PieceType>( 12, PieceType.BlackKnight ),
new KeyValuePair<Int32, PieceType>( 13, PieceType.BlackPawn ),
new KeyValuePair<Int32, PieceType>( 14, PieceType.BlackPawn ),
new KeyValuePair<Int32, PieceType>( 16, PieceType.BlackQueen ),
new KeyValuePair<Int32, PieceType>( 17, PieceType.BlackPawn ),
new KeyValuePair<Int32, PieceType>( 18, PieceType.BlackPawn ),
new KeyValuePair<Int32, PieceType>( 19, PieceType.BlackRook ),
new KeyValuePair<Int32, PieceType>( 23, PieceType.BlackPawn ),
new KeyValuePair<Int32, PieceType>( 24, PieceType.BlackPawn ),
// Setup White pieces
new KeyValuePair<Int32, PieceType>( 31, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 32, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 35, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 36, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 37, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 38, PieceType.WhitePawn ),
new KeyValuePair<Int32, PieceType>( 40, PieceType.WhiteKnight ),
new KeyValuePair<Int32, PieceType>( 41, PieceType.WhiteBishop ),
new KeyValuePair<Int32, PieceType>( 42, PieceType.WhiteRook ),
new KeyValuePair<Int32, PieceType>( 53, PieceType.WhiteKing )
}
);
cb.DisplayBoard();
int square = 41;
ChessEngine eng = new ChessEngine();
List<FutureMove> futureMoves = eng.Calculate( cb, square );
int move1 = futureMoves.Where( m => m.Depth == 1 ).Count();
int move2 = futureMoves.Where( m => m.Depth == 2 ).Count();
int move3 = futureMoves.Where( m => m.Depth == 3 ).Count();
Console.WriteLine();
Console.WriteLine( String.Format( "Number of potential squares reached in 1 move {0,3} from square {1,2}", move1, square ) );
Console.WriteLine( String.Format( "Number of potential squares reached in 2 moves {0,3} from square {1,2}", move2, square ) );
Console.WriteLine( String.Format( "Number of potential squares reached in 3 moves {0,3} from square {1,2}", move3, square ) );
Console.WriteLine();
Console.WriteLine( "Press any key to exit." );
Console.ReadKey();
}
}
上一篇: 国际象棋游戏项目VB.net
下一篇: 棋子的未来流动性