棋子的未来流动性
我目前正在用C＃开发一个国际象棋引擎，并且在开发代码以确定任何给定棋子的未来移动性时，我已经碰到了一堵砖墙，在1,2和3步中。 基本的想法是奖励奖品以增加行动力，并惩罚行动不便的人。
国际象棋棋盘被表示为从0（a8）到63（h1）开始的64个正方形的阵列，例如
Piece[] _chessboard = new Piece[64];
我以这个棋盘位置为例：
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)
以下是相同位置的FEN字符串： 3r1k2/3nnpp1/qppr3P/P6P/P2PPPP1/NBR5/5K2/2R5
经过多次失败尝试后，我想出了以下数据结构（链接列表？），我希望是通过方块追踪移动性的最佳方式。
+--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 25 | 2 | | 25 | 34 | 16 | 3 | +--------+-------------+-----------+-------+
这个结构告诉我的是，第41平方的白主教一举移动到第34平方，然后第2平方25移动，第3移动平方16。 上述结构使用递归函数进行填充，该函数遍历主教可以在1,2和3移动中移动的所有可能的正方形。 问题在于所有低效率的举措都将被记录下来，并且在被更有效的举措所取代之前，这些举措必须被检测和删除。
例如，经由正方形34和25以3次移动从正方形41移动到16是不高效的，因为可能以2次移动移动到正方形16; 41到34中1移动然后34到16 2移动。 我需要递归函数来检测这些低效的移动，并在将新的高效移动添加到数据结构之前将其删除。
我需要递归函数执行得非常快，因为它将被评估函数用于搜索给定位置中的最佳移动。
我正在寻找的是一些代码，它们将查询（可能使用LINQ？）上面的数据结构，以返回上述数据结构中低效移动的列表，以便将它们移除，例如
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
这只是一个示例，它可能不会编译; 我希望有一些向导可以帮助我在这里编写find_moves函数，以便正确地返回效率低下的动作，因为我不知道如何去做这件事。
我希望我能够在这里清楚地解释一切。
谢谢！
**编辑**
考虑到没有人发布任何建议，我会尽量简化一下。 我正在寻找一种算法，用来更新数据结构（类似于上面给出的），它包含棋盘上方块之间最有效的移动，这正是我所需要的。
例如：
假设我在方块41（b3）为白主教递归产生了这些动作; 在1次移动中它可以从41移动到34（b3-c4），然后在2次移动中从34移动到27（c4-d5）并且最后从27移动到20（d5-e6）。
这意味着它已经通过34和27从方块41到20获得了3次移动，但是一旦递归函数开始处理更高效的移动，它将需要搜索数据结构以查找低效移动并删除它们。
如果可以做到这样的话，那将是非常棒的：
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.
**编辑2 **
在对可能的解决方案进行一些分析和开发之后，我认为我可能通过采用与上面给出的不同的数据结构来破解它。
目前为止的解决方案 - 欢迎所有的批评尽可能地尝试和改进这个版本。
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 );
}
}
我不确定有关复制和粘贴别人代码的版权规则，因此您需要从这里下载PredicateBuilder源代码才能运行我的代码。
上面的代码将产生以下输出：
+--------+---------+---------+---------+---------+ | 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.
我想你会回头看这个。 你根本不需要在每一步中修剪低效的移动。 您为此提出的递归方式是优雅的，但永远不会高效。
你应该简单地生成一个可以在一次移动中达到的所有正方形的列表。 然后生成最多两次移动中可以达到的所有广场列表。 有一个简单的方法可以做到这一点 - 将前一个列表中的所有方块取出，并一次找出所有可以从它们到达的方块。 将所有这些列表与原始列表相结合，消除重复。 然后找到所有可以用三步移动的方块。 再一次，删除重复，但不要担心你已经包括'低效的方块'，也就是说，在一个移动或两个移动列表中。 你想包括前两个列表中的所有内容。
现在，如果您只需要数量的方块，只需通过计算即可快速获得它们。 以三次或更少的次数达到的方格数是最后一个列表的长度。 第二个列表的长度可以在两次或更少的时间内达到的平方数。 因此，它们之间的差异是可以在三次移动中达到的平方数。
如果您碰巧想要三个正方形的列表，您可以使用高效的LINQ函数， Except 。
顺便说一句，这个问题非常适合codereview.stackexchange.com，因为它更多的是关于已经编写的代码，而不是语言或技术的特定问题。
听起来像一个有趣的方法......我认为大多数引擎只是使用近似值（比如给中间位置赋予块值），因为直接计算它太昂贵，并且额外的周期更适合进一步搜索先。
这里是我在下面的伪执行的尝试，我不能完全理解你的数据结构，所以这显然需要大量的修改，哦，它不是LINQ的，对此抱歉：
///<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);
}
}
祝你好运，并希望它成为一个有价值的对手。
使用jwg给出的建议，我认为我已经设法计算了在一个正方形上给定棋子的1,2和3次移动中的所有可能移动。
以下是有兴趣的人的示例代码 - 它使用原始帖子中给出的棋盘样本并计算方块b3上白主教将来的潜在移动性。 无论是否正确，我还不确定，所以我将不得不验证结果的准确性。
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();
}
}