EPD Test Suites

In order to track the progress on the engine and also to compare different features between my mACE and the iCE engine I felt to need to be able to run test positions against the engines.

So far I test single mid game positions before and after some changes, Usually the change was so significant that testing a single position showed the outcome very clearly (adding 0 move or LMR). For a better estiamtion of change impact I need a more comprehensive test setup.

There are test suites available in the internet containing EPD position lines. A EPD line is a basically a position in FEN notation and a best move command, that gives the best move in that position. Running such a test suite against an engine will be much better than running simple positions.

There are available programs on the net that do EPD stress tests with engines, but I rather programmed my own test arena, so I can tweak it a bit better to the results I want to have.

The arena is now done and part of the GUI.

Detecting Three-fold repetition

While designing the new engine I thought about a way to efficiently detect two-fold and three-fold repetitions. My PASCAL mACE engine stores the hash keys of all positions that happened on the board and when a new position is added it looks through the last ones (up to the last pawn move or capture) whether this key shows up in the history. This is very safe, not too bad, but it involves a loop every time a move is made.

Maybe there are better ways of doing that, I thought about a special hash table that only stores a counter for every position that is incremented when the move to that positions is made and decremented when the moves is unmade (in search this happens very often). This would be pretty fast, but what about hash table collisions. Two different positions on the board map to the same hash slot. Are the likely, do I have to care about them.

So question is, in a game of maybe 200 moves, how likely is it that in a table of lets say 32.768 slots 2 different positions map to the same slot. This would confuse the repetition counter and lead to incorrect results.

When you consider the numbers (200 moves, 32768 slots) you might think that is is very unlikely that two positions collide, but in fact it is rather likely. The probability is about 46%. So it that setup every other game you would end up with incorrect repetition detection, which is not acceptable.

How does the probability change when I increase the the hash size. I created a little spreadsheet, that did this for me. The probability P for a collision is P = 1 - (y/(y-x))^(y-x) * e^-x

So it shows that even with large hash sizes a significant probability remains that a collision occurs, I have to find a smart way of handling them.

The prototype of a C++ engine is done

The first version of a new C++ based chess engine that knows the rules and can play random legal moves is done. There is still a awful lot of programming work left as basically the only real thing already working is the move generator, but as far as I can tell it looks promising.

It generates moves faster than my Free Pascal based engine. But probably it is rather from a different implementation of things than by the change of programming language.

• I avoided to use threads, in C++ on Windows you can use PeekNamedPipe to mange unblocking IO.

• I implemented magic bitboards instead of rotated bitboards (It was far easier to implement, the board transformations for rotated bitboards were really mind bending)
• I used int as TMove representation

To verify the correct implementation of the UCI protocol I let the new yet unnamed engine play 2 games against my latest version of the mACE engine. Of course mACE crushed it very fast. (No surprise when one engine is just playing random moves).  It took mACE at most 15 moves to mate the other engine.

And the Mates looked like this

Prototyping a new chess engine

After careful consideration I decided to start a parallel engine project for a new chess engine written in C++. This means that the work on my free pascal engine is frozen for the moment as I cannot develop two engines in parallel. Especially the mental switching between Pascal and C++ syntax is quite difficult.

Such small bugs like

Pascal: if sideToMove = WHITE then perform something;
C++ : if (sideToMove = WHITE) perform something;   // this is a bug, must be if (sideToMove == WHITE) ...

make the programming difficult. My older formed Borland compiler warned when it encountered such statements (was very helpful). Visual C++ warns sometimes when it is suspicious about the involved types but not always.

So at the moment I put my efforts on a chess engine skeleton in C++. So especially the board class, where the moves are generated and executed will require some time. I wonder what the new perft values will be compared to my Pascal based mACE engine.

I hope that using magic bit boards and using plain int as move type will pay off somehow too.

Chess Engine Design Considerations

My MACE engine is now functional, it does not play very strong yet, so if competing against other engines it loses most of the time. I think I can improved it by tuning the evaluation function, but this will not fix one of the fundamental problems of the engine.


It is too slow !

Slow relates here to the raw speed "nodes per second".

Using intelligent pruning methods like NULL move or LMR one can reduce the number of nodes  the engine considers but there are limits to that. In one point in time the engine is faced with a number of nodes it just has to evaluate. And if it is slow in doing that it will not reach the depths necessary to compete with other engines. It also makes the transposition table less useful as it does contain lesser nodes compared with a fast engine.

I have considered several options to increase the speed

1. Dropping the TMove class and using plain integers as move (saving the construction and destruction)
2. Using magic bitboards instead of rotated bitboards (should increase move generation and execution)
3. Dropping the IO thread that is listening on stdin for new commands, making the engine single threaded and saving the shared memory handling overhead

This requires some major changes to the engine and option 3 is probably not possible with Free Pascal.


I think instead of rewriting large parts of the code about starting a parallel engine project using C++ as language. I've not used C++ for quite some time so I'm probably a lot slower programming at first but it helps me refreshing my skills, which is quite necessary I think.