Chess Board representation - Engine [closed]
https://stackoverflow.com/questions/11473909
-
20-06-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I'm working on my own chess engine in C#. Actually I'm searching bugs on my move generator, but I realized that my actual chess system is too slow (even 21 minutes on perft(6)). Here is my Github repository.
I'm using a simple hierarchy for pieces and a board class that implements a list of pieces. Because of the object-oriented nature of this project, I chose to not use a multi-dimensional matrix to represent the board, given that each piece has its own position inside them. The problem is that to get a piece from the board, knowing its position, it takes O(n), where n is the number of pieces currently on the board.
In the move generator I get all possible moves assuming an empy board, and then I check them with a static class (because a piece shouldn't care about board state). I visited some sites, include the chess programming Wiki. I saw that there are many types of board representations, but in my actual state I don't know which is the best (performance and simplicity). I think this is all, I hope you will help me :)
I welcome any advice regarding my project ;) Thanks all.
Here is my board class:
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);
}
}
}
Solution
Array based representations usually have a piece list with each piece and its square, so you don't have to loop through the entire board to find a piece (edit: looking at your code, it seems you already do this?). What's much more important than board representation is how you implement the board operations. For example, testing whether the king is in check does not need to generate an entire move list; you simply have to scan outwards from the king for enemy pieces.
After having looked a bit at your code, it seems that you use a legal move generator, and that you make/unmake (and perhaps other things?) to check legality. The latter isn't necessary, depending on whether you started in check and if any pieces are pinned.
I think you know that bitboards are the standard nowadays, as it performs many piece operations setwise and gets a nice boost on 64 bit platforms. I switched from the mailbox array approach to bitboards in my own engine, and currently perft(6) is 3 seconds. Originally it was something like 30 seconds. Bitboards makes evaluation much simpler, so there's also that to consider.
OTHER TIPS
Thanks for the link for your code, first of all, because that made this a lot easier to answer.
The issue you're having is that you iterate through all of the pieces to find a piece, which is very slow, as you mentioned.
If you want to keep the implementation similar to what you already have in place and at an object-oriented level, I would recommend that you use a Dictionary object to store the pieces. The key can be the location on the board (i.e. A4) and the value would be the piece itself. The Dictionary is a better choice in the case than the List because you can do lookups instead of having to iterate through all of the pieces.
Also in your GetNumberOfPieces method, even in your current implementation, you should use the List.Count property.
But Zong Li's answer is probably better for a chess engine specifically.
EDIT
I looked at your code a little more and I noticed you're passing around Square objects, so maybe you could implement the Dictionary as a dictionary of Square, Piece instead of coordinate, piece.
