我目前正在用C#开发一个国际象棋引擎,在开发用来确定任何给定棋子在1、2和3步中的未来移动性的代码时,我遇到了一点困难。基本的想法是奖励增加机动性的棋子和惩罚减少机动性的棋子。
象棋棋盘被表示为64个方块的阵列,从0(a8)到63(h1)开始,例如。
piece[]_chessboard=新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/P2PPP1/NBR5/5K2/2R5
在几次失败的尝试之后,我想出了以下数据结构(链表?)我希望这是追踪方块移动性的最好方法。
+--------+-------------+-----------+-------+ | Square | Predecessor | Successor | Depth | +--------+-------------+-----------+-------+ | 41 | NULL | 34 | 1 | | 34 | 41 | 25 | 2 | | 25 | 34 | 16 | 3 | +--------+-------------+-----------+-------+
这个结构告诉我的是41号方块上的白主教1步走到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)上为一个白主教递归地生成了这些移动;在一次移动中,它可以从41移动到34(b3-c4),然后在两次移动中从34移动到27(c4-d5),最后在三次移动中从27移动到20(d5-e6)。
这意味着它已经用了3个移动从方块41通过34和27到达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, 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.
我觉得你这是在走回头路。你根本不需要在每一步都删减低效的动作。这样做的递归方式很优雅,但永远不会高效。
您应该简单地生成一个列表,列出您可以在一次移动中到达的所有方块。然后生成一个列表,列出最多在两次移动中可以到达的所有方块。有一种简单的方法可以做到这一点--把前面列表中的所有方块都取出来,然后一步就找到所有可以从其中到达的方块。将所有这些列表与原始列表合并,删除重复。然后在三步走中找到你能到达的所有方块。同样,删除重复,但不要担心你包含了“低效方块”,也就是说,在一步或两步列表中的方块。您希望在前两个列表中包含所有内容。
现在,如果你只想要平方的数字,你可以通过计算很快得到它们。三步或三步以下可以到达的方格数为最后一个列表的长度。两步或两步以下可以到达的方格数就是第二个列表的长度。因此,它们之间的差值是三次移动所能到达的方格数。
如果您碰巧想要恰好三个可以到达的方块列表,那么此时可以使用高效的LINQhtml" target="_blank">函数except
。
顺便说一句,这个问题非常适合codereview.stackExchange.com,因为它更多地是关于您想要改进的已经编写的代码,而不是某个语言或技术的特定问题。
上面的代码显示了一个可以上下移动的部分的示例。这不是一个有效的棋步。所以,如果我要移动一个皇后,我该怎么做呢?我们只是假设我们已经有了一个矩阵(x,y)8×8的板。
五子棋单机版: 规则:5子连成一线者胜 特色: 1、单人游戏,对于人机对战此款小游戏具备一定的智能性。 2、双人对战,更支持多人混战 3、棋盘残局保存功能 1、游戏主界面 2、设置界面 可以设置棋盘的相关属性,棋盘行列数,玩家数目,棋盘背景,游戏难易度,等。 3、残局恢复 (1)单击选择曾经的游戏日期,当天的所有游戏记录会显示到列表中。 (2)双击游戏对应的游戏记录,即可恢复至对应的棋局。
本文向大家介绍Java棋类游戏实践之单机版五子棋,包括了Java棋类游戏实践之单机版五子棋的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了java实现的五子棋游戏代码,分享给大家供大家参考,具体代码如下 一、实践目标 1.掌握JavaGUI界面设计 2.掌握鼠标事件的监听(MouseListener,MouseMotionListener) 二、实践内容
本文向大家介绍java实现单机版五子棋,包括了java实现单机版五子棋的使用技巧和注意事项,需要的朋友参考一下 这个小游戏是我和我姐们儿的JAVA课程设计,也是我做的第一个JAVA项目,适合初学者,希望能帮到那些被JAVA课设所困扰的孩纸们~~~ 一、该游戏需要实现 1、设计主框架,界面。 2、利用ActionListener接口实现按钮事件的监听。 3、重新开始功能的实现。 4、悔棋功能的实现。
本文向大家介绍java绘制五子棋棋盘,包括了java绘制五子棋棋盘的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了java绘制五子棋棋盘的具体代码,供大家参考,具体内容如下 源码: 效果图: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。
本文向大家介绍c# 绘制中国象棋棋盘与棋子,包括了c# 绘制中国象棋棋盘与棋子的使用技巧和注意事项,需要的朋友参考一下 本文是利用C# 实现中国象棋的棋盘绘制,以及初始化布局,并不实现中国象棋的对弈逻辑。仅供学习参考使用。 思路: 绘制中国象棋棋盘,竖线九条,横线十条。再中间绘制‘楚河',‘汉界' 。 绘制棋子,然后将棋子布局在棋盘上即可。 涉及知识点: 用户控件:用于实现棋盘的绘制,重写 OnP