c# - チェス盤の表現-エンジン

Question

私は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);
        }
    }
}

Answer 1

配列ベースの表現には通常、各ピースとその正方形のピースリストがあるため、ピースを見つけるためにボード全体をループする必要はありません（編集：コードを見ると、すでにこれを行っているようです？）。ボード表現よりもはるかに重要なのは、ボード操作をどのように実装するかです。たとえば、王がチェックされているかどうかをテストするために、移動リスト全体を生成する必要はありません。敵の駒を探すために王から外側にスキャンする必要があります。

あなたのコードを少し見てみると、あなたは合法的な移動ジェネレーターを使用しているようで、合法性をチェックするために作成/作成解除（そしておそらく他のもの？）しているようです。チェックを開始したかどうか、およびピースが固定されているかどうかによっては、後者は必要ありません。

ビットボードは、セット単位で多くのピース操作を実行し、64ビットプラットフォームで優れたブーストを取得するため、今日では標準となっていることをご存知だと思います。メールボックス配列アプローチから自分のエンジンのビットボードに切り替えました。現在、perft（6）は3秒です。もともとは30秒くらいでした。ビットボードを使用すると評価がはるかに簡単になるため、考慮すべき点もあります。

Answer 2

まず第一に、あなたのコードへのリンクをありがとう。それはこれに答えるのをずっと簡単にしたからです。

あなたが抱えている問題は、あなたが言ったように、あなたがすべてのピースを繰り返して、非常に遅いピースを見つけることです。

実装を既存のものと同様に、オブジェクト指向レベルで維持したい場合は、Dictionaryオブジェクトを使用してピースを格納することをお勧めします。キーはボード上の場所（つまりA4）にすることができ、値はピース自体になります。すべての部分を反復処理する代わりにルックアップを実行できるため、このDictionary場合はより適切な選択です。List

また、GetNumberOfPiecesメソッドでは、現在の実装でも、List.Countプロパティを使用する必要があります。

しかし、Zong Liの答えは、特にチェスエンジンの方がおそらく良いでしょう。

編集

コードをもう少し見てみると、オブジェクトを渡していることに気づいたので、座標、ピースではなく、スクエア、ピースの辞書としてSquare実装できるかもしれません。Dictionary