AxolotlFever wrote: ↑Wed Nov 14, 2018 11:21 amI would like to introduce my new chess engine, Axolotl! This engine is written in Java (10), and compiled to 8. It is a UCI engine
Hi Louis. Welcome to the TalkChess forum and congratulations on your accomplishment! Writing an original chess engine requires a lot of determination and mental focus. You should be proud of reaching this milestone- an engine that plays a game of chess. I laugh at your use of the word "finished." I know you qualified it with "the first version" but we'll see how you feel about that word in a few months or years. Our hobby is addictive and encourages constant tinkering.
I looked through your source code and can offer some advice regarding why your engine is not a fast as you'd like it to be. The single most significant killer of speed is the use of the "new" keyword. If you want to improve the performance of your engine then eliminate all memory allocations during search. Make it your mission to find every use of the "new" keyword and move it outside of the search function (or any functions called by search). Create and populate all your data structures during engine startup. Reference these pre-allocated data structures during search. Modify them if necessary but do not construct new objects during search. Like this:
During Startup
Code: Select all
_positions = new Position[_maxPositions];
for (int positionIndex = 0; positionIndex < _maxPositions; positionIndex++) _positions[positionIndex] = new Position(GetPositionCount);
public sealed class Position
{
public const int MaxMoves = 128;
public readonly ulong[] Moves;
public ulong WhitePawns;
public ulong WhiteKnights;
public ulong WhiteBishops;
public ulong WhiteRooks;
public ulong WhiteQueens;
public ulong WhiteKing;
public ulong OccupancyWhite;
public ulong BlackPawns;
public ulong BlackKnights;
public ulong BlackBishops;
public ulong BlackRooks;
public ulong BlackQueens;
public ulong BlackKing;
public ulong OccupancyBlack;
public ulong Occupancy;
public ulong PotentiallyPinnedPieces;
public bool WhiteMove;
public uint Castling;
public int EnPassantSquare;
public int HalfMoveNumber;
public int FullMoveNumber;
public bool KingInCheck;
public int MoveIndex;
public ulong PiecesSquaresKey;
public ulong Key;
public ulong PlayedMove;
During Search
Code: Select all
private void GenerateBishopMoves()
{
ulong bishops;
ulong unOrEnemyOccupied;
int attacker;
if (CurrentPosition.WhiteMove)
{
// White move
bishops = CurrentPosition.WhiteBishops;
unOrEnemyOccupied = ~CurrentPosition.OccupancyWhite;
attacker = Piece.WhiteBishop;
}
else
{
// Black move
bishops = CurrentPosition.BlackBishops;
unOrEnemyOccupied = ~CurrentPosition.OccupancyBlack;
attacker = Piece.BlackBishop;
}
int fromSquare;
while ((fromSquare = Bitwise.FindFirstSetBit(bishops)) >= 0)
{
ulong occupancy = BishopMoveMasks[fromSquare] & CurrentPosition.Occupancy;
// Bishops may move to unoccupied squares or squares occupied by enemy.
ulong bishopDestinations = PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & unOrEnemyOccupied;
int toSquare;
while ((toSquare = Bitwise.FindFirstSetBit(bishopDestinations)) >= 0)
{
int victim = CurrentPosition.GetPiece(toSquare);
ulong move = Move.Null;
Move.SetFrom(ref move, fromSquare);
Move.SetTo(ref move, toSquare);
if (victim != Piece.None) Move.SetCaptureAttacker(ref move, attacker);
Move.SetCaptureVictim(ref move, victim);
Move.SetIsQuiet(ref move, victim == Piece.None);
CurrentPosition.Moves[CurrentPosition.MoveIndex] = move;
CurrentPosition.MoveIndex++;
Bitwise.ClearBit(ref bishopDestinations, toSquare);
}
Bitwise.ClearBit(ref bishops, fromSquare);
}
}
Notice the above code does not allocate any memory. You won't find any use of the "new" keyword.
Another tip is to represent moves as a primitive data type (I use ulong). Then provide a static class with helper functions to manipulate that primitive type
by reference. Like this:
Code: Select all
// Move bits
// Higher priority moves have higher ulong value.
// 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
// 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// B|CapV |CapA |Promo |Kil|History |O|K|E|D|P|C|Q|From |To
// B = Best Move
// CapV = Capture Victim
// CapA = Capture Attacker (inverted)
// Promo = Promoted Piece
// Kil = Killer Move
// O = Castling
// K = King Move
// E = En Passant Capture
// D = Double Pawn Move
// P = Pawn Move
// C = Check
// Q = Quiet (not capture, pawn promotion, castling, or check)
// From = From (needs one extra bit for illegal square)
// To = To (needs one extra bit for illegal square)
static Move()
{
// Create bit masks and shifts.
_bestShift = 63;
_bestMask = Bitwise.CreateULongMask(63);
_bestUnmask = Bitwise.CreateULongUnmask(63);
_captureVictimShift = 59;
_captureVictimMask = Bitwise.CreateULongMask(59, 62);
_captureVictimUnmask = Bitwise.CreateULongUnmask(59, 62);
_captureAttackerShift = 55;
_captureAttackerMask = Bitwise.CreateULongMask(55, 58);
_captureAttackerUnmask = Bitwise.CreateULongUnmask(55, 58);
_promotedPieceShift = 51;
_promotedPieceMask = Bitwise.CreateULongMask(51, 54);
_promotedPieceUnmask = Bitwise.CreateULongUnmask(51, 54);
_killerShift = 49;
_killerMask = Bitwise.CreateULongMask(49, 50);
_killerUnmask = Bitwise.CreateULongUnmask(49, 50);
_historyShift = 21;
_historyMask = Bitwise.CreateULongMask(21, 48);
_historyUnmask = Bitwise.CreateULongUnmask(21, 48);
_castlingShift = 20;
_castlingMask = Bitwise.CreateULongMask(20);
_castlingUnmask = Bitwise.CreateULongUnmask(20);
_kingMoveShift = 19;
_kingMoveMask = Bitwise.CreateULongMask(19);
_kingMoveUnmask = Bitwise.CreateULongUnmask(19);
_enPassantShift = 18;
_enPassantMask = Bitwise.CreateULongMask(18);
_enPassantUnmask = Bitwise.CreateULongUnmask(18);
_doublePawnMoveShift = 17;
_doublePawnMoveMask = Bitwise.CreateULongMask(17);
_doublePawnMoveUnmask = Bitwise.CreateULongUnmask(17);
_pawnMoveShift = 16;
_pawnMoveMask = Bitwise.CreateULongMask(16);
_pawnMoveUnmask = Bitwise.CreateULongUnmask(16);
_checkShift = 15;
_checkMask = Bitwise.CreateULongMask(15);
_checkUnmask = Bitwise.CreateULongUnmask(15);
_quietShift = 14;
_quietMask = Bitwise.CreateULongMask(14);
_quietUnmask = Bitwise.CreateULongUnmask(14);
_fromShift = 7;
_fromMask = Bitwise.CreateULongMask(7, 13);
_fromUnmask = Bitwise.CreateULongUnmask(7, 13);
_toMask = Bitwise.CreateULongMask(0, 6);
_toUnmask = Bitwise.CreateULongUnmask(0, 6);
// Set null move.
Null = 0;
SetIsBest(ref Null, false);
SetCaptureVictim(ref Null, Piece.None);
SetCaptureAttacker(ref Null, Piece.None);
SetPromotedPiece(ref Null, Piece.None);
SetKiller(ref Null, 0);
SetHistory(ref Null, 0);
SetIsCastling(ref Null, false);
SetIsKingMove(ref Null, false);
SetIsEnPassantCapture(ref Null, false);
SetIsDoublePawnMove(ref Null, false);
SetIsPawnMove(ref Null, false);
SetIsCheck(ref Null, false);
SetIsQuiet(ref Null, false);
SetFrom(ref Null, Square.Illegal);
SetTo(ref Null, Square.Illegal);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int From(ulong Move) => (int) ((Move & _fromMask) >> _fromShift);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void SetFrom(ref ulong Move, int From)
{
// Clear
Move &= _fromUnmask;
// Set
Move |= (ulong) From << _fromShift;
// Validate move.
Debug.Assert(Engine.Move.From(Move) == From);
Debug.Assert(IsValid(Move));
}
And one more tip tonight: Prefer to use arrays and for loops over Lists and foreach. I don't know the internals of Java, but in C# access to arrays is faster than the indirection introduced by List indexers. And for is faster than foreach because foreach allocates an Enumerator (and this Enumerator must be garbage collected). These may seem like insignificant issues in isolation but they become very significant when called hundreds of thousands or millions of times per second inside tight loops. And that is what search is- recursive calls to very tight loops that iterate over moves.
Good luck improving your engine! Send me a PM if you have any questions. I don't know Java (I mean, I can read it but I don't write Java code as part of my job) but I know C# in depth and am familiar with performance pitfalls of managed languages. The capabilities and performance of manage languages / runtimes has improved
significantly in the last 10 or 15 years.