当前位置: 首页 > 知识库问答 >
问题:

棋子的未来机动性

傅正阳
2023-03-14

我目前正在用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.

共有1个答案

李森
2023-03-14

我觉得你这是在走回头路。你根本不需要在每一步都删减低效的动作。这样做的递归方式很优雅,但永远不会高效。

您应该简单地生成一个列表,列出您可以在一次移动中到达的所有方块。然后生成一个列表,列出最多在两次移动中可以到达的所有方块。有一种简单的方法可以做到这一点--把前面列表中的所有方块都取出来,然后一步就找到所有可以从其中到达的方块。将所有这些列表与原始列表合并,删除重复。然后在三步走中找到你能到达的所有方块。同样,删除重复,但不要担心你包含了“低效方块”,也就是说,在一步或两步列表中的方块。您希望在前两个列表中包含所有内容。

现在,如果你只想要平方的数字,你可以通过计算很快得到它们。三步或三步以下可以到达的方格数为最后一个列表的长度。两步或两步以下可以到达的方格数就是第二个列表的长度。因此,它们之间的差值是三次移动所能到达的方格数。

如果您碰巧想要恰好三个可以到达的方块列表,那么此时可以使用高效的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