我目前正在用C#开发一个国际象棋引擎,我在开发代码时遇到了一些障碍,以确定任何给定棋子在1,2和3次移动中的未来移动性.基本的想法是奖励可以提高行动能力的奖励,并惩罚行动不便的作品.
棋盘表示为64个正方形的阵列,从0(a8)到63(h1)开始,例如
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
经过几次失败的尝试后,我想出了以下数据结构(Linked List？),我希望这是通过正方形追踪移动性的最佳方式.
+--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 25 | 2 | | 25 | 34 | 16 | 3 | +--------+-------------+-----------+-------+
这个结构告诉我的是方形41上的白色主教在1次移动中移动到方形34,然后在2次移动中移动方形25并且在3次移动中移动方形16.上面的结构使用递归函数填充,该函数遍历Bishop可以在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),然后在3次移动中从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.
我认为你正在倒退。您根本不需要在每一步中修剪低效的动作。您为此提出的递归方法很优雅，但永远不会有效。
您应该简单地生成一份您一次可以到达的所有方块的列表。然后生成一个列表，其中包含最多两步可以到达的所有方块。有一种简单的方法可以做到这一点 - 取出前一个列表中的所有方块，并找到从它们一次移动可以到达的所有方块。将所有这些列表与原始列表合并，删除重复项。然后找出三步内能到达的所有方格。再次，删除重复项，但不要担心您已包含“低效方块”，也就是说，那些位于一步或两步列表中的方块。您希望将所有内容都包含在前两个列表中。
现在，如果您只想要正方形的数量，只需通过计算就可以很快得到它们。三步或更短的时间内可以到达的方格数就是最后列表的长度。两次或更少的移动可以到达的方格数就是第二个列表的长度。因此，它们之间的差异是恰好三步即可到达的方格数。
如果您碰巧想要恰好三个即可到达的方格列表，Except此时可以使用高效的 LINQ 函数。
顺便说一句，这个问题非常适合codereview.stackexchange.com，因为它更多的是关于您想要改进的已编写的代码，而不是语言或技术的特定问题。