棋盘表示
我正在C＃中使用我自己的国际象棋引擎。 其实我正在寻找我的移动发生器上的错误，但是我意识到我的实际国际象棋系统太慢了（甚至超过21分钟（6））。 这是我的Github存储库。
我正在使用一个简单的层次结构来实现碎片和一个实现碎片列表的电路板类。 由于这个项目的面向对象性质，我选择不使用多维矩阵来表示棋盘，因为每个棋子都有自己的位置。 问题是，要从板上获得一块，知道它的位置，需要O（n），其中n是板上当前的棋子数量。
在移动生成器中，我假设有一个empy板可以执行所有可能的动作，然后用静态类检查它们（因为一块板不应该关心板状态）。 我访问了一些网站，包括国际象棋程序维基。 我看到有很多类型的棋盘表示形式，但在我的实际状态中，我不知道哪个是最好的（性能和简单性）。 我认为这是全部，我希望你能帮助我:)
我欢迎任何有关我的项目的建议;）谢谢大家。
这是我的班级：
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);
}
}
}
基于数组的表示通常有一个片段列表，每个片段和它的正方形，所以你不必遍历整个板子找到一块（编辑：看你的代码，看起来你已经这样做了？）。 比董事会代表更重要的是你如何实施董事会的运作。 例如，测试国王是否被检查并不需要生成整个移动列表; 你只需要从国王身边向外扫描敌人的部分。
看了一下你的代码后，似乎你使用了一个合法的移动生成器，并且你制作/取消制作（或者其他的东西？）来检查合法性。 后者是没有必要的，这取决于你是否开始检查以及是否有任何东西被钉住。
我认为你知道现在的标准是现在的标准，因为它在许多平台上运行，在64位平台上得到了很好的提升。 我从邮箱阵列方式切换到我自己的引擎中的位板，目前perft（6）是3秒。 最初它大概是30秒。 比特板使得评估更简单，所以还需要考虑。
首先，感谢您的代码链接，因为这使得这更容易回答。
你所遇到的问题是，如你所提到的那样，你遍历所有的片断来找到一个非常缓慢的片断。
如果你想保持实现类似于你已有的和面向对象的级别，我会建议你使用Dictionary对象来存储这些块。 关键可以是棋盘上的位置（即A4），并且该值将是棋子本身。 在List ， Dictionary是比List更好的选择，因为您可以执行查找，而不必遍历所有片段。
同样在你的GetNumberOfPieces方法中，即使在你当前的实现中，你也应该使用List.Count属性。
但宗力的回答可能更适合国际象棋引擎。
编辑
我再看看你的代码，我注意到你正在传递Square对象，所以也许你可以将Dictionary作为Square，Piece的字典而不是坐标，片断来实现。