new Engine, Axolotl

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AxolotlFever
Posts: 24
Joined: Sun Nov 11, 2018 8:26 pm
Location: Germany
Full name: Louis Mackenzie-Smith

Re: new Engine, Axolotl

Post by AxolotlFever » Thu Nov 29, 2018 11:31 am

emadsen wrote:
Wed Nov 28, 2018 2:47 am
AxolotlFever wrote:
Wed Nov 14, 2018 10:21 am
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:
Hi Erik!

Thank you so much for this feedback, I have started implementing the changes you suggested, and I can already feel a speed boost! Thanks also for your kind words - and I definitely see what you mean about constant tinkering!

The next version of Axolotl will be out in a few days, taking on board much of what you and others said. I cannot express how grateful I am for this wonderful and freely given feedback, it is really heartwarming.

Ok back to code! In your answer, one sentence left me unsure,
Prefer to use arrays and for loops over Lists and foreach
I understand the for loops > for each, but when we talk about arrays I am struggling a bit. My understanding is that, in java, arrays are fixed size. So if I use an array to store moves (ints), I would have to know ahead of time how many moves will be generated, which seems impossible. I could also work out the maximum possible number of moves, which might be about 80 (?) and always populate an array that size, but this seems to be wasteful of memory, especially when escaping check. Sorry to be unclear on this! Could you possibly let me know how arrays could be used?

Thanks very much for your time, and I hope to give madchess a good game someday!

Kind regards,
Louis

User avatar
emadsen
Posts: 184
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: new Engine, Axolotl

Post by emadsen » Fri Nov 30, 2018 4:05 am

I could also work out the maximum possible number of moves, which might be about 80 (?) and always populate an array that size, but this seems to be wasteful of memory, especially when escaping check.
The trade of wasted memory for avoiding allocations is worth it. List allocates an array for its internal storage. If you don't specify the maximum size, it guesses. If you call Add() and the internal array is full, a new array is allocated, memory is copied from the old array to the new array, and the old array eventually is garbage-collected. The new array may not be located in memory anywhere near other Board or Position members, possibly causing memory faults as the Board or Position class members interact with the array. Even if you specify the max size when you create the List (to avoid copying memory when resizing), you're still paying the price of going through its indexer.

At its most basic, it comes down to this: Why use a class who's purpose is to surreptitiously allocate and relocate data in memory? You should be writing code that makes memory allocations explicit so they're easy to identify and move out of the search into the engine initialization. Arrays are a better data structure for the search algorithm because you intend to work with fixed memory. If you do not allocate anything on the heap (no object creation) during search, there's nothing to garbage-collect. That's a significant performance win.

Code: Select all

// Allocate move array.
ulong[] Moves = new ulong[128];
int MoveIndex = 0;

// Add a move.
Moves[CurrentPosition.MoveIndex] = move;
CurrentPosition.MoveIndex++;

// Search moves.
for (int moveIndex = 0; moveIndex < CurrentPosition.MoveIndex; moveIndex++)
{
    ulong move = CurrentPosition.Moves[moveIndex];
}
My C# chess engine: http://www.madchess.net

Post Reply