Bitboard Wrapper - Performance and Memory allocation
https://stackoverflow.com/questions/11504169
-
21-06-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I'm currently trying to develop a chess engine in C#. Thanks to the detailed answers given to me in my previous thread, I'm now studying how to apply a bitboard system to my game structure. In principle, I'm trying, again, to apply some Object oriented design to this new concept of engine, but now I have some unanswered questions in mind:
I would like to implement a bitboard structure leaning on a UInt64 field to abstract that concept, maybe providing methods like GetFirstBit() or Shift(..) or even PopCount(..), but I don't know how that would influence performance and memory allocation. Would be better a class to increase performance thanks to reference copy, or for a so small object the Heap would just complicate things?
I would even implement an indexer to enter on single bits like in a normal array, would it a waste of resources or it is a good idea (for a chess engine) ?
I'm trying to minimize changes to my project, but I realized that all my piece hierarchy and my Move and Square classes would be set aside and never used more... Should I just give up that design, or can I reuse those classes somehow?
This is a prototype of what i would like to implement into my engine:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chess_Engine___NOGUI
{
public struct BitBoard
{
public UInt64 bitBoard;
public BitBoard(UInt64 board)
{
bitBoard = board;
}
public static implicit operator BitBoard(UInt64 board)
{
return new BitBoard(board);
}
public static implicit operator UInt64(BitBoard board)
{
return board.bitBoard;
}
public static BitBoard operator <<(BitBoard board, int shift)
{
return board.bitBoard << shift;
}
public static BitBoard operator >>(BitBoard board, int shift)
{
return board.bitBoard >> shift;
}
public static BitBoard operator &(BitBoard a, BitBoard b)
{
return a.bitBoard & b.bitBoard;
}
public static BitBoard operator |(BitBoard a, BitBoard b)
{
return a.bitBoard | b.bitBoard;
}
public static BitBoard operator ^(BitBoard a, BitBoard b)
{
return a.bitBoard ^ b.bitBoard;
}
public static BitBoard operator ~(BitBoard a)
{
return ~a.bitBoard;
}
}
}
And Here the classes that i would like to save...
this is my Move class:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chess_Engine___NOGUI
{
class NullMove : Move
{
public NullMove()
: base(null, null, null)
{
}
}
class Move
{
public string Algebraic
{
get
{
return ToAlgebraic();
}
} // JUST FOR DEBUG
public Square FromSquare { get; set; }
public Square ToSquare { get; set; }
public Piece PieceMoved { get; set; }
public Piece PieceCaptured { get; set; }
public PieceType PiecePromoted { get; set; }
public bool HasPromoted
{
get
{
return PiecePromoted != PieceType.None;
}
}
public bool IsEnpassant { get; set; }
public bool HasCaptured
{
get
{
if (PieceCaptured != null)
return true;
else
return false;
}
}
public bool IsCastling
{
get
{
return IsLongCastling || IsShortCastling;
}
}
public bool IsLongCastling
{
get
{
if (PieceMoved is King)
{
if (FromSquare.X - ToSquare.X == 2)
return true;
else
return false;
}
else
{
return false;
}
}
}
public bool IsShortCastling
{
get
{
if (PieceMoved is King)
{
if (FromSquare.X - ToSquare.X == -2)
return true;
else
return false;
}
else
{
return false;
}
}
}
public bool IsCheck { get; set; }
public bool IsCheckMate { get; set; }
public bool IsDoublePawnPush
{
get
{
if (PieceMoved.Type == PieceType.Pawn)
if (!HasCaptured)
if (ToSquare.X == FromSquare.X)
if (SideMove == PieceColor.White)
{
if (ToSquare.Y - FromSquare.Y == 2)
return true;
}
else
{
if (ToSquare.Y - FromSquare.Y == -2)
return true;
}
return false;
}
}
public PieceColor SideMove
{
get
{
return PieceMoved.Color;
}
}
public Piece RookMoved { get; set; }
public Square KingPosition { get; set; }
public Square RookPosition { get; set; }
public float Score { get; set; }
public Move(Square fromSquare, Square toSquare, Piece pieceMoved, PieceType piecePromoted = PieceType.None)
{
this.FromSquare = fromSquare;
this.ToSquare = toSquare;
this.PieceMoved = pieceMoved;
this.PiecePromoted = piecePromoted;
}
public static bool operator ==(Move a, Move b)
{
return a.Equals(b);
}
public static bool operator !=(Move a, Move b)
{
return !a.Equals(b);
}
public override bool Equals(object other)
{
if (other is Move)
{
Move compare = (Move)other;
return (this.FromSquare == compare.FromSquare && this.ToSquare == compare.ToSquare);
}
else
{
return false;
}
}
public override int GetHashCode()
{
return base.GetHashCode();
}
public string ToAlgebraic()
{
StringBuilder algebraic = new StringBuilder();
if (IsCastling) // se e` una mossa di arrocco
{
if (IsShortCastling)
algebraic.Append("O-O"); // arrocco corto
else
algebraic.Append("O-O-O"); // arrocco lungo
}
else
{
algebraic.Append(FromSquare.ToAlgebraic());
if (HasCaptured)
algebraic.Append("x"); // cattura
algebraic.Append(ToSquare.ToAlgebraic());
}
if (HasPromoted)
algebraic.Append(PiecePromoted.GetInitial());
if (IsCheck)
if (IsCheckMate)
algebraic.Append("#"); // scacco matto
else
algebraic.Append("+"); // scacco
return algebraic.ToString();
}
}
}
Here is my Square class:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chess_Engine___NOGUI
{
sealed class Square
{
public int X { get; set; }
public int Y { get; set; }
public Square(int x, int y)
{
this.X = x;
this.Y = y;
}
public static implicit operator Square(string str)
{
// converte la notazione algebrica (es. a1) in coordinate decimali
str = str.ToLower(); // converte la stringa in minuscolo
int x = (int)(str[0] - 'a');
int y = (int)(str[1] - '1');
return new Square(x, y);
}
public static bool operator ==(Square a, Square b)
{
if (System.Object.ReferenceEquals(a, b))
{
return true;
}
if (((object)a == null) || ((object)b == null))
{
return false;
}
if (a is Square)
{
Square compare = (Square)b;
return (a.X == compare.X && a.Y == compare.Y);
}
else
{
return false;
}
}
public static bool operator !=(Square a, Square b)
{
return !(a == b);
}
public override bool Equals(object obj)
{
return base.Equals(obj);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
public string ToAlgebraic()
{
string str = "";
str += (char)(this.X + 97);
str += (this.Y + 1).ToString();
return str;
}
}
}
and here is my abstract Piece class:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chess_Engine___NOGUI
{
public enum PieceType { None, Pawn, Knight, Bishop, Rook, Queen, King }
public enum PieceColor { None, White, Black }
public static class Extensions
{
public static PieceColor GetOpposite(this PieceColor color)
{
if (color == PieceColor.White)
return PieceColor.Black;
if (color == PieceColor.Black)
return PieceColor.White;
else
return PieceColor.None;
}
public static char GetInitial(this PieceType type)
{
switch (type)
{
case PieceType.Bishop:
return 'B';
case PieceType.King:
return 'K';
case PieceType.Knight:
return 'N';
case PieceType.Pawn:
return 'P';
case PieceType.Queen:
return 'Q';
case PieceType.Rook:
return 'R';
default:
return ' ';
}
}
}
abstract class Piece
{
public char Notation { get; set; }
protected List<Move> movesList;
public Square startingSquare { get; set; }
public Square square { get; protected set; }
public Square lastSquare { get; set; }
public PieceType Type { get; set; }
public PieceColor Color { get; set; }
public virtual bool AlreadyBeenMoved
{
get
{
return square != startingSquare;
}
}
public Piece(Square square, PieceColor color)
{
this.startingSquare = square;
this.square = square;
this.lastSquare = square;
this.Color = color;
this.movesList = new List<Move>();
}
public void Move(Square destination)
{
square = destination; // aggiorna la posizione attuale
}
public bool ShouldUpdateMoves()
{
if (lastSquare == square) // se il pezzo non si e` mosso
{
if (movesList.Count > 0)
return false;
}
else
{
lastSquare = square;
movesList.Clear();
}
return true;
}
public abstract List<Move> GetMoves();
}
}
I would like to emphasize that some really important factors for a correct answers here are speed optimization and well object oriented design.
thanks to all :)
La solution
At the end of your question, you specify 2 factors that fundamentally conflict with each other. My recommendation is that you focus on one or the other. Either you value good OO design or you value good performance. You can't really have both.
To answer the question in your first bullet point, I personally don't use any OO for finding (for example) the first significant bit in a bitboard:
private const UInt64 DEBRUIJN64 = 0x07EDD5E59A4E28C2;
private static readonly Byte[] INDEX64 = {63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5};
// De Bruijn Multiplication, see http://chessprogramming.wikispaces.com/BitScan
// Don't use this if bitmap = 0!
internal static Byte BitScanForward(UInt64 bitmap)
{
Debug.Assert(bitmap != 0);
return INDEX64[((ulong)((long)bitmap & -(long)bitmap) * DEBRUIJN64) >> 58];
}
I don't use Piece or Square classes:
// Piece identifiers, 4 bits each.
// Useful bitwise properties of this numbering scheme:
// white = 0..., black = 1..., sliding = .1.., nonsliding = .0..
// rank/file sliding pieces = .11., diagonally sliding pieces = .1.1
// pawns and kings (without colour bits), are < 3
// major pieces (without colour bits), are > 5
// minor and major pieces (without colour bits set), are > 2.
internal const byte EMPTY = 0; // 00000000
internal const byte WHITE_PAWN = 1; // 00000001
internal const byte WHITE_KING = 2; // 00000010
internal const byte WHITE_KNIGHT = 3; // 00000011
internal const byte WHITE_BISHOP = 5; // 00000101
internal const byte WHITE_ROOK = 6; // 00000110
internal const byte WHITE_QUEEN = 7; // 00000111
internal const byte BLACK_PAWN = 9; // 00001001
internal const byte BLACK_KING = 10; // 00001010
internal const byte BLACK_KNIGHT = 11; // 00001011
internal const byte BLACK_BISHOP = 13; // 00001101
internal const byte BLACK_ROOK = 14; // 00001110
internal const byte BLACK_QUEEN = 15; // 00001111
I do use a Move class, but it should probably be a struct. My tests didn't show a significant difference:
internal sealed class Move
{
internal Move()
{
}
internal Move(byte squareFrom, byte squareTo, byte pieceMoved, byte pieceCaptured, byte piecePromoted)
{
this.SquareFrom = squareFrom;
this.SquareTo = squareTo;
this.PieceMoved = pieceMoved;
this.PieceCaptured = pieceCaptured;
this.PiecePromoted = piecePromoted;
}
// The FROM square.
// Bits 1-3 are the board file, bits 4-6 are the board rank, bits 7-8 are unused.
internal readonly byte SquareFrom;
// The TO square.
// Bits 1-3 are the board file, bits 4-6 are the board rank, bits 7-8 are unused.
internal readonly byte SquareTo;
// The MOVED piece.
// Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
internal readonly byte PieceMoved;
// The CAPTURED piece.
// Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
internal readonly byte PieceCaptured;
// The PROMOTED piece.
// Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
// NB Overloaded to represent EN-PASSANT capture if promoted piece is a pawn.
// NB Overloaded to represent CASTLING if promoted piece is a king.
internal readonly byte PiecePromoted;
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
