c# – 棋子的未来移动

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