new Engine, Axolotl

[ljgw]

<snip>

An engine with your feature set, written in java, should be able to achieve more than 1Mn/s (single threaded, on a modern CPU). One area of concern with java is, of course, the gc. Not sure how much it slows you down, but creating many small objects (moves being the main thing I noticed) certainly isn't helping you.

I can testify to that. When I first made my java engine I had fresh objects everywhere, but it was slooow. The first thing I did to improve was use the int primitive to store my move information (using the first 3 bits for 'from' the next 3 for 'to' etc) but it only reached acceptable speeds once I went through my code and absolutely minimized object creation in the search and eval functions.

The downside is that my program isn't as nicely Object Orientated as I envisioned it to be when I started, but what can you do ^^

Also, I did keep some object creation, for example I do still have ScoredMove objects for the moves at the root node. I'm just extra careful with objects in places that are executed thousands of times per second.

[AxolotlFever]

A new Java engine!

I've just looked at your code and have some performance suggestions:

1) Use Long.numberOfTrailingZeros() instead of getIndexOfFirstPiece()
2) Use the following code instead of getIndexOfAllPieces():

Code: Select all

while (pieces != 0) {
   int index = Long.numberOfTrailingZeros(pieces);
   //do work
   pieces &= pieces - 1;
}

Hi there Sander!

Thank you very much for these two tips, I will get right on this. I have also starred your engine on github - it is extremely impressive! I hope to give it a good game someday. If I may ask you one question with regard to your chess22k engine: I notice you use PHASE objects (/int) in many parts of your engine, but I am not sure I understand why. If you have a minute sometime, could you let me know why? It has been bugging me for a while!

With very kind regards,

Louis

[AxolotlFever]

I didn't run the engine, but I have some notes from reading the source code:

This may seem obvious, but run the engine with profiling to find out where it's spending most of its time. This is necessary before attempting any optimization.

Instead of returning ArrayList objects from each of your move generation methods, pass a List<Move> as a parameter to each move generation method and have them add to the provided list. However, this may be a negligible performance improvement -- see above.

It looks like your transposition table will grow without bounds (unless I missed something). Normally, a transposition table is a simple array with a fixed size (usually configurable in UCI options), with a bucket replacement strategy (simplest being "always replace"). Board positions are indexed by [zobristHash % array.length].

An engine with your feature set, written in java, should be able to achieve more than 1Mn/s (single threaded, on a modern CPU). One area of concern with java is, of course, the gc. Not sure how much it slows you down, but creating many small objects (moves being the main thing I noticed) certainly isn't helping you.

Hello Josh,

Thank you for taking the time to read the code - I hope it was not too bad. You have made some excellent suggestions, and I will fix the table now. You were quite right, it has no limit at the moment. I also like your idea of passing List<Move> as a parameter, I bet this will make a difference too.

As for 1Mn/s, this is still a distant dream for me, but I will get there someday!

Thanks again for your time and tips,
Kind regards,
Louis

[AxolotlFever]

I am from the UK and France. I don't suppose there is support for this?

Go team France !

Wooo! Weirdly, I tick three of these boxes, because I live in Germany at the moment, so your funny cartoon has left me a bit confused! If you have any tips about how I should greet people, let me know

Thanks for responding Laurent,
Kind wishes,
Louis

[AxolotlFever]

<snip>

An engine with your feature set, written in java, should be able to achieve more than 1Mn/s (single threaded, on a modern CPU). One area of concern with java is, of course, the gc. Not sure how much it slows you down, but creating many small objects (moves being the main thing I noticed) certainly isn't helping you.

I can testify to that. When I first made my java engine I had fresh objects everywhere, but it was slooow. The first thing I did to improve was use the int primitive to store my move information (using the first 3 bits for 'from' the next 3 for 'to' etc) but it only reached acceptable speeds once I went through my code and absolutely minimized object creation in the search and eval functions.

The downside is that my program isn't as nicely Object Orientated as I envisioned it to be when I started, but what can you do ^^

Also, I did keep some object creation, for example I do still have ScoredMove objects for the moves at the root node. I'm just extra careful with objects in places that are executed thousands of times per second.

Hi there Laurens,

Thanks for your answer! I did not actually give any thought to the gc while writing the code! I guess I have some work to do. Thanks also for the tip about reducing the number of objects - it seems so obvious once you say it! I was just tunnelvisioning on getting that perfect perft.
Quick question though - At the moment I use 6bits for the "from" square and 6 for the "to" square inside my move integer. I thought this was the minimum needed to allow for 64 individual numbers - but you said you only use three! Is there a trick I do not know? Thanks in advance!

Best wishes,

Louis

[ljgw]

...
Quick question though - At the moment I use 6bits for the "from" square and 6 for the "to" square inside my move integer. I thought this was the minimum needed to allow for 64 individual numbers - but you said you only use three! Is there a trick I do not know? Thanks in advance!

Best wishes,

Louis

Sorry, I'm afraid I mixed up files / ranks with squares. Indeed it's six bits per square: 3 for the file of the square, and 3 for the rank of the square.

As we say in Dutch: sorry for the dead sparrow..

--Laurens

[sandermvdb]

Thank you very much for these two tips, I will get right on this. I have also starred your engine on github - it is extremely impressive! I hope to give it a good game someday. If I may ask you one question with regard to your chess22k engine: I notice you use PHASE objects (/int) in many parts of your engine, but I am not sure I understand why. If you have a minute sometime, could you let me know why? It has been bugging me for a while!

Phase explained:
https://www.chessprogramming.org/Tapered_Eval

[AxolotlFever]

Thank you very much for these two tips, I will get right on this. I have also starred your engine on github - it is extremely impressive! I hope to give it a good game someday. If I may ask you one question with regard to your chess22k engine: I notice you use PHASE objects (/int) in many parts of your engine, but I am not sure I understand why. If you have a minute sometime, could you let me know why? It has been bugging me for a while!

Phase explained:
https://www.chessprogramming.org/Tapered_Eval

Hi there, thanks for the link! Yet another thing I should implement. However when talking about phase, I was thinking of a particular part I have seen in many engines:
If I may quote from your engine (I hope this is ok)

while (phase <= PHASE_QUIET) {}

this is written within the negamax search, and I was wondering what led to you implementing this.
Thanks for your feedback,
Louis

[sandermvdb]

Hi there, thanks for the link! Yet another thing I should implement. However when talking about phase, I was thinking of a particular part I have seen in many engines:
If I may quote from your engine (I hope this is ok)

while (phase <= PHASE_QUIET) {}

this is written within the negamax search, and I was wondering what led to you implementing this.

This is part of the staged move-generation: first the tt-move is performed, then the attacking moves, followed by killers and finally the quiet moves. The idea is that if one of those early moves cause a beta-cutoff, the other moves have not yet been generated (small speed improvement).

[emadsen]

I 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.