我目前正在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在1动作,然后方形25在2动作和方形16在3动作.使用递归函数填充上述结构,该递归函数遍历Bishop可以在1,2和2中移动的所有可能的正方形. 3动.这样做的问题是,所有低效的移动都将被记录下来,这些移动需要被更高效的移动所代替.
例如,通过正方形34和25从3方向移动到方框41到16不是有效的,因为可以在2个移动中移动到正方形16; 41到34 in 1 move然后34到16 in 2 move.在将新的高效移动添加到数据结构之前,我需要递归函数来检测这些低效的移动并删除它们.
我需要递归函数来执行非常快,因为它将被评估函数用来搜索给定位置的最佳移动.
我正在寻找的是一些代码,可以查询(可能使用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,depth ) );
}
function IEnumerable<MoveNode> find_moves( int from,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,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采取了3次从平方41到20的移动,但是一旦递归函数开始处理更有效的移动,则需要搜索数据结构以进行低效移动并将其删除.
如果可以做这样的事情会很好：
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,1 );
parent = addMove( parent,27,2 );
parent = addMove( parent,20,3 );
parent = addMove( parent,13,3 );
parent = addMove( _nodes[ 0 ],2 );
parent = addMove( _nodes[ 0 ],2 );
parent = addMove( null,3 );
parent = addMove( null,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 depthLevel )
{
MoveNode node = null;
var inefficientMoves = getNodesToBeRemoved( from,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 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 );
}
}
我不知道有关复制&粘贴别人的代码,所以您需要从here下载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功能,除此之外.
BTW,这个问题将非常适合codereview.stackexchange.com,因为它更多的是您要改进的已编写的代码,而不是语言或技术的特定问题.
