3

我正在用 C# 开发自己的国际象棋引擎。实际上，我正在搜索我的移动生成器上的错误，但我意识到我的实际国际象棋系统太慢了（perft(6) 甚至 21 分钟）。这是我的Github 存储库。

我使用了一个简单的片段层次结构和一个实现片段列表的板类。由于这个项目的面向对象的性质，我选择不使用多维矩阵来表示棋盘，因为每个棋子在其中都有自己的位置。问题是要从棋盘上得到一个棋子，知道它的位置，它需要 O(n)，其中 n 是棋盘上当前棋子的数量。

在移动生成器中，假设一个空棋盘，我得到所有可能的移动，然后我用一个静态类检查它们（因为一块不应该关心棋盘状态）。我访问了一些网站，包括国际象棋编程 Wiki。我看到有很多类型的板表示，但在我的实际状态中，我不知道哪个是最好的（性能和简单性）。我想这就是全部，我希望你能帮助我:)

我欢迎任何关于我的项目的建议；）谢谢大家。

这是我的董事会课程：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Chess_Engine___NOGUI
{
    class Board
    {
        public const byte BoardSize = 8;
        private Game game;
        private List<Piece> pieceList = new List<Piece>();
        private List<Piece> whitePieceList = new List<Piece>();
        private List<Piece> blackPieceList = new List<Piece>();

        public Board(Game game)
        {
            this.game = game;
        }

        public void AddPiece(Piece piece)
        {
            pieceList.Add(piece);
            switch (piece.Color)
            {
                case PieceColor.Black:
                    blackPieceList.Add(piece);
                    break;
                case PieceColor.White:
                    whitePieceList.Add(piece);
                    break;
            }
        }
        public void RemovePiece(Piece piece)
        {
            pieceList.Remove(piece);
            switch (piece.Color)
            {
                case PieceColor.Black:
                    blackPieceList.Remove(piece);
                    break;
                case PieceColor.White:
                    whitePieceList.Remove(piece);
                    break;
            }
        }

        public Square GetKingPosition(PieceColor color)
        {
            if (color == PieceColor.White)
                foreach (Piece piece in whitePieceList)
                {
                    if (piece.Type == PieceType.King)
                        return piece.square;
                }
            else
                foreach (Piece piece in blackPieceList)
                {
                    if (piece.Type == PieceType.King)
                        return piece.square;
                }

            throw new Exception("il re deve essere sempre presente");
        }
        public Piece GetPiece(Square square, PieceColor color = PieceColor.None)
        {
            switch (color)
            {
                case PieceColor.White:
                    {
                        foreach (Piece piece in whitePieceList)
                        {
                            if (piece.square == square)
                                return piece;
                        }
                        return new NullPiece(square);
                    }
                case PieceColor.Black:
                    {
                        foreach (Piece piece in blackPieceList)
                        {
                            if (piece.square == square)
                                return piece;
                        }
                        return new NullPiece(square);
                    }
                default:
                    {
                        foreach (Piece piece in pieceList)
                        {
                            if (piece.square == square)
                                return piece;
                        }
                        return new NullPiece(square);
                    }
            }
        }
        public List<Piece> GetPieceList(PieceColor color)
        {
            switch (color)
            {
                case PieceColor.Black:
                    return blackPieceList;
                case PieceColor.White:
                    return whitePieceList;
                default:
                    return pieceList;
            }
        }
        public int GetNumberOfPieces(PieceType type, PieceColor color)
        {
            int num = 0;
            foreach (Piece piece in GetPieceList(color))
            {
                if (piece.Type == type)
                    num++;
            }

            return num;
        }
        public bool IsEmpty(Square square)
        {
            if ((GetPiece(square)) is NullPiece)
            {
                return true;
            }
            return false;
        }
        public void Equip()
        {
            this.Clear();

            PieceFactory pieceFactory = new PieceFactory();
            /*PEDONI*/
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(0, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(1, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(2, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(3, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(4, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(5, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(6, 1)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.White, new Square(7, 1)));
            //
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(0, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(1, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(2, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(3, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(4, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(5, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(6, 6)));
            AddPiece(pieceFactory.Create(PieceType.Pawn, PieceColor.Black, new Square(7, 6)));

            /*TORRI*/
            AddPiece(pieceFactory.Create(PieceType.Rook, PieceColor.White, new Square(0, 0)));
            AddPiece(pieceFactory.Create(PieceType.Rook, PieceColor.White, new Square(7, 0)));
            //
            AddPiece(pieceFactory.Create(PieceType.Rook, PieceColor.Black, new Square(0, 7)));
            AddPiece(pieceFactory.Create(PieceType.Rook, PieceColor.Black, new Square(7, 7)));

            /*CAVALLI*/
            AddPiece(pieceFactory.Create(PieceType.Knight, PieceColor.White, new Square(1, 0)));
            AddPiece(pieceFactory.Create(PieceType.Knight, PieceColor.White, new Square(6, 0)));
            //
            AddPiece(pieceFactory.Create(PieceType.Knight, PieceColor.Black, new Square(1, 7)));
            AddPiece(pieceFactory.Create(PieceType.Knight, PieceColor.Black, new Square(6, 7)));

            /*ALFIERI*/
            AddPiece(pieceFactory.Create(PieceType.Bishop, PieceColor.White, new Square(2, 0)));
            AddPiece(pieceFactory.Create(PieceType.Bishop, PieceColor.White, new Square(5, 0)));
            //
            AddPiece(pieceFactory.Create(PieceType.Bishop, PieceColor.Black, new Square(2, 7)));
            AddPiece(pieceFactory.Create(PieceType.Bishop, PieceColor.Black, new Square(5, 7)));

            /*RE*/
            AddPiece(pieceFactory.Create(PieceType.King, PieceColor.White, new Square(4, 0)));
            //
            AddPiece(pieceFactory.Create(PieceType.King, PieceColor.Black, new Square(4, 7)));

            /*REGINE*/
            AddPiece(pieceFactory.Create(PieceType.Queen, PieceColor.White, new Square(3, 0)));
            //
            AddPiece(pieceFactory.Create(PieceType.Queen, PieceColor.Black, new Square(3, 7)));
        }
        public void Clear()
        {
            pieceList.Clear();
            whitePieceList.Clear();
            blackPieceList.Clear();
        }
        public void LoadGame(FenString fen)
        {
            this.Clear();

            foreach (Piece piece in fen.PiecePlacement)
            {
                AddPiece(piece);
            }
        }
        public void MakeMove(Move move)
        {
            if (move.IsCastling)
            {
                move.RookMoved.Move(move.RookPosition);
                if (move.IsShortCastling)
                    game.GetPlayer(move.SideMove).CanShortCastle = false;
                else
                    game.GetPlayer(move.SideMove).CanLongCastle = false;
            }
            else
            {
                if (move.HasCaptured)
                {
                    RemovePiece(move.PieceCaptured);
                }
                if (move.HasPromoted)
                {
                    RemovePiece(move.PieceMoved);
                    AddPiece(PieceFactory.CreatePiece(move.PiecePromoted, move.SideMove, move.ToSquare));
                }
            }

            // En passant target square updating

            game.EnPassantSquareStack.Push(game.EnPassantSquare); // save the current target square for the unmake-move method

            if (move.IsDoublePawnPush)
            {
                Square targetSquare;
                if (move.SideMove == PieceColor.White)
                    targetSquare = new Square(move.ToSquare.X, 2);
                else
                    targetSquare = new Square(move.ToSquare.X, 5);

                game.EnPassantSquare = targetSquare;
            }

            else if (game.EnPassantSquare != null)
            {
                game.EnPassantSquare = null;
            }

            move.PieceMoved.Move(move.ToSquare); // move piece
        }
        public void CancelMove(Move move)
        {
            if (move.IsCastling)
            {
                move.PieceMoved.Move(move.FromSquare);
                move.RookMoved.Move(move.RookMoved.startingSquare);
                if (move.IsShortCastling)
                    game.GetPlayer(move.SideMove).CanShortCastle = true;
                else
                    game.GetPlayer(move.SideMove).CanLongCastle = true;
            }
            else
            {
                if (move.HasCaptured)
                {
                    AddPiece(move.PieceCaptured);
                }
                if (move.HasPromoted)
                {
                    RemovePiece(GetPiece(move.ToSquare));
                    AddPiece(move.PieceMoved);
                }
            }

            // En passant target square updating

            game.EnPassantSquare = game.EnPassantSquareStack.Pop();

            move.PieceMoved.Move(move.FromSquare);
        }
    }
}
4

2 回答 2

5

基于数组的表示通常有一个包含每个块及其正方形的块列表，因此您不必遍历整个电路板即可找到一块（编辑：查看您的代码，您似乎已经这样做了？）。比董事会代表更重要的是您如何实施董事会运作。例如，测试国王是否在被检查，不需要生成完整的移动列表；你只需要从国王向外扫描敌人的棋子。

在查看了您的代码之后，您似乎使用了合法的移动生成器，并且您制作/取消制作（也许还有其他东西？）来检查合法性。后者不是必需的，具体取决于您是否开始检查以及是否有任何部分被固定。

我想你知道位板是当今的标准，因为它可以按组执行许多分段操作，并在 64 位平台上得到很好的提升。我在自己的引擎中从邮箱数组方法切换到位板，目前 perft(6) 是 3 秒。最初大约是 30 秒。Bitboards 使评估变得更加简单，因此也需要考虑这一点。

于 2012-07-13T15:57:00.277 回答
3

首先，感谢您提供代码的链接，因为这使回答更容易。

正如您所提到的，您遇到的问题是您遍历所有片段以找到一个片段，这非常慢。

如果您想让实现与您已有的实现类似并且在面向对象的级别上，我建议您使用Dictionary对象来存储这些片段。键可以是棋盘上的位置（即 A4），值是棋子本身。在这种情况下，这Dictionary是比 更好的选择，List因为您可以进行查找，而不必遍历所有部分。

同样在您的GetNumberOfPieces方法中，即使在您当前的实现中，您也应该使用该List.Count属性。

但宗立的答案可能更适合专门用于国际象棋引擎。

编辑

我又看了你的代码，发现你在传递Square对象，所以也许你可以将它实现Dictionary为 Square, Piece 的字典，而不是坐标，一块。

于 2012-07-13T16:00:41.337 回答