c# - 棋子的 future 流动性

Question

我目前正在用 C# 开发国际象棋引擎，在开发代码以确定任何给定棋子在第 1、2 和 3 步中的 future 移动性时，我遇到了一些困难。基本思想是奖励棋子移动性增加的奖励，惩罚移动性差的棋子。

棋盘表示为 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)

Here is the FEN string for the same position: 3r1k2/3nnpp1/qppr3P/P6P/P2PPPP1/NBR5/5K2/2R5

After several failed attempts I have come up with the following data structure (Linked List?) that I hope is the best way of tracing mobility through squares.

+--------+-------------+-----------+-------+| Square | Predecessor | Successor | Depth |+--------+-------------+-----------+-------+|     41 | NULL        |        34 |     1 ||     34 | 41          |        25 |     2 ||     25 | 34          |        16 |     3 |+--------+-------------+-----------+-------+

What this structure tells me is the White Bishop on square 41 goes to square 34 in 1 move, then square 25 in 2 moves and square 16 in 3 moves. The above structure is populated using a recursive function that traverses all possible squares that the Bishop can move to in 1, 2 & 3 moves. The problem with this is that all inefficient moves will be recorded and these need to be detected and deleted before being replaced by more efficient moves.

For example, moving from square 41 to 16 in 3 moves via squares 34 and 25 is not efficient because it is possible to move to square 16 in 2 moves; 41 to 34 in 1 move then 34 to 16 in 2 moves. I require the recursive function to detect these inefficient moves and delete them before adding the new efficient move to the data structure.

I need the recursive function to execute very fast as it will be used by the evaluation function to search for the best move in a given position.

What I am looking for is some code that will query (possibly using LINQ?) the data structure above to return a list of the inefficient moves from the above data structure so they can be removed, e.g.

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 的代码。函数以便正确返回低效的 Action ，因为我不确定如何去做。

我希望我已经设法清楚地解释了这里的一切。

谢谢!

** 编辑 **

考虑到没有人发布任何建议，我将尝试简化一些事情。我正在寻找一种算法，该算法将用于更新包含棋盘上正方形之间最有效移动的数据结构(类似于上面给出的那个)，这就是我所寻找的。

例如:

假设我为第 41 格 (b3) 的白主教递归生成了这些移动；在 1 步中它可以从 41 到 34 (b3-c4)，然后在 2 步中从 34 到 27 (c4-d5)，最后从 27 到 20 (d5-e6) 3 步。

这意味着从方格 41 到 20 通过 34 和 27 已经走了 3 步，但是一旦递归函数开始处理更有效的 Action ，它将需要搜索数据结构以寻找低效的 Action 并将其删除。

如果可以做这样的事情就太好了:

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.

** Edit 2 **

After some analysis and development of a possible solution I think that I may have cracked it by adopting a different data structure to the one given above.

Here is the solution so far -- all critique is welcome to try and improve this version as much as possible.

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源代码来自 here为了运行我的代码。

上面的代码将产生以下输出:

+--------+---------+---------+---------+---------+| 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-c4b3-d5b3-e6b3-f7Press any key to exit.

Answer 1

我认为你在倒退。您根本不需要在每一步都修剪低效的 Action 。您为此提出的递归方法很优雅，但永远不会有效。

您应该简单地生成一个您一次可以到达的所有方格的列表。然后生成一个列表，其中包含您最多可以通过两次移动到达的所有方格。有一种简单的方法可以做到这一点——取出前面列表中的所有方格，并找到从它们一步可以到达的所有方格。将所有这些列表与原始列表合并，删除重复项。然后找到所有你可以在三步内到达的方格。同样，删除重复项，但不要担心您包含了“低效方 block ”，也就是说，那些在一步或两步列表中的方 block 。您想要包括前两个列表中的所有内容。

现在，如果你只想要方 block 的数量，你可以通过计算很快地得到它们。以三步或更少的步数可以到达的方格数就是最后一个列表的长度。在两次或更少的移动中可以到达的方格数是第二个列表的长度。因此，它们之间的区别在于恰好三步可以到达的方格数。

如果您恰好想要正好三个可以到达的正方形列表，此时您可以使用高效的 LINQ 函数 Except。

顺便说一句，这个问题很适合 codereview.stackexchange.com ，因为它更多地是关于您想要改进的已经编写的代码，而不是语言或技术的特定问题。