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), e.g.
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, e.g.
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.