Pros and Cons of MS Visual C++ 2010 Express

Since I was feeling that my Free Pascal based mACE engine executes to slowly I started the iCE engine which is using C++ as programming language. When I came to choose the actual compiler I decided to use MS Visual C++ 2010 Express Edition.

After a few weeks of coding with it here is my very personal opinion about its Pros and Cons

Pros:

1. It's free. (I don't want to spend money for a little spare time project)
2. It has a pleasing ergonomic usage view and feeling. (MS always knew how to make things look nice)
3. It allows a fast start into programming. Just type a little "hello world" program into the editor and click the run button.
4. It has an extremely good on the fly syntax checking, called IntelliSense. While you type your code it checks it for syntax correctness. Things like type mismatches, missing brackets, misspelled type names, missing ; or missing includes are spotted and marked (like in MS Word) while you type. This is really impressing and gives you a huge boost in coding performance. When you build your project your code is already pretty good and your are not flooded with countless error messages because of a missing closing bracket somewhere.
5. It has a powerful integrated debugger, it gives you an auto pane where it automatically displays the variables and values of the just used scope. It is also able to interpret complex statements like (ESquare)((ml->moves[i] & MASK_FROM_SQ) >> SHIFT_FROM_SQ) and it can show you the contents of complex types behind pointers. Free Pascal just showed the memory address of the object which is quite useless and you had to write code to map your objects into local variables as the debugger was not able to display the object directly. 
6. It supports the INTEL inline assembler style, the syntax is a little different from the one in Free Pascal but basically comparable. And you can start a assembler block with a _asm directive and just write assembler code between { }. When you see the GNU compiler assembler mess with assembler statements being C++ strings in an awkward AT&T style you will see what I mean. I would love to see the architectural decision that made the GNU guys decide to use a programming language from a Telco provider rather than from a processor manufacturer.  (I know the -masm=intel option in GNU, but the assembler syntax is still not the same as in Free Pascal or Visual C++).
7. In Warning Level 4 it gives you good hints where you might have coded dirty causing you problems later on. It will spot things like if (value = 0), which is in almost all cases an error or usage of not initialized variables (useful when you have a lot of branches in your code and in one of the branches you access the variable without its initialization first).

This is a long list of Pros, longer than I expected, now to the Cons

1. The Express Edition does not include a code profiler that allows you to find not optimized parts of your code, or just to give you information what code is spend the most time on, so you know where to optimize first. The Professional Edition shall include one (not verified by me) but this edition is not free so for my little non commercial project not affordable.
2. The generated executable includes dependencies on some dll's so they don't run on other computers unless a redistributable framework is installed on them. There might be a code generation option for a runtime library like "Multithreaded-Debug-DLL" where the dependency  might not exist (not tested so far), but the pure existence of a default that generates an executable that does not run on another computer is annoying. 
3. The generated code does not seem to be optimal. I use seem, because I might not have found all tweaks to make it faster. VC++ comes with 2 code generation defaults, a DEBUG Release and a RELEASE release. the RELEASE option generates code that is about twice as fast as the DEBUG option, so I assume a lot of optimization is turned on here. But the resulting code was still much slower than the code generated by my Free Pascal engine. Usually this is not a problem as computers today are so fast they run even unoptimized code fast enough, but when you program a chess engine execution speed is one of your main concerns (and it was the reason to start with a C++ engine at the beginning).

The last Con is real concern to me and for this little chess engine project. When the final code is slow it doesn't matter how nice and painless it was to write it. I decided to test another C++ compiler on my source code just to see whether I made mistakes in porting it from Pascal to C++.

I used g++ (the GNU C++ compiler) on my source. I had to make a few source code adjustemenst (like I defined my own INFINITY constant, VC++ was fine with that, g++ not, even with an own namespace). Most hassle went into the inline assembler functions for bitboard operations (finding the least signinficat bit) which did just not compile in g++ even with -masm=intel. I replaced the assembler code with C++ code like

#ifdef _MSC_VER
    __asm
    {
            ; use bsf to get the least significant bit
    }
#else
      if (B==0) return 64; else return __builtin_ctzll(B);
#endif

So it finally compiled. To my surprise the almost identical source code generated a much faster executable with g++. I did not expect such a huge difference.

Just to give an impression of the difference

VC++:
go depth 11

info depth 10 seldepth 29 time 42125 nodes 7924921 pv b4b7 f7b7 h5g6 h7g6 d8g8 g6f5 g8g4 f5e5 g4h5 f3f5 f2f4 h2f4 h5e2 d1e2 a4e4 d5e4 d3d4  nps 188128 score mate 9 hashfull 190 tbhits 0
 
info depth 11 seldepth 24 time 135391 nodes 38553528 pv b4b7 f7b7 h5g6 h7g6 d8g8 g6f5 g8g4 f5e5 g4h5 f3f5 f2f4 h2f4 h5e2 d1e2 a4e4 d5e4 d3d4  nps 284756 score mate 9 hashfull 132 tbhits 0
bestmove b4b7

g++:
go depth 11

info depth 10 seldepth 29 time 15203 nodes 7924921 pv b4b7 f7b7 h5g6 h7g6 d8g8 g6f5 g8g4 f5e5 g4h5 f3f5 f2f4 h2f4 h5e2 d1e2 a4e4 d5e4 d3d4  nps 521273 score mate 9 hashfull 190 tbhits 0
 
info depth 11 seldepth 24 time 54906 nodes 38553528 pv b4b7 f7b7 h5g6 h7g6 d8g8g6f5 g8g4 f5e5 g4h5 f3f5 f2f4 h2f4 h5e2 d1e2 a4e4 d5e4 d3d4  nps 702173 score mate 9 hashfull 132 tbhits 0
bestmove b4b7


So the g++ code processed 702.173 nodes per second where the VC++ only processed 284.756 nodes.


My personal outcome:
I will continue to write and debug the code with Visual C++ but for the release code generation I will use the GNU compiler instead.

C++ and backward for loops

Although I'm programming for many years now sometimes I just make simple coding errors. Just recently I used a statement like

unsigned in i;

for (i=ml->moveCnt; i>=0; i--)

{

    // do something

}

It was meant to apply some actions for all moves in a list of moves. In reality this loop will never terminate except for not handled exceptions (like list index out of range). The reason is of course that the loop variable is an unsigned int, so the exit condition is never reached (i will always be greater or equal to 0).

The correct way of coding that would be

unsigned int i;

for (i=ml->moveCnt; i --> 0; )

{

  // do something

}

The "i --> 0" looks also very cool, but somehow those loop statements are a bit harder to read. So I use signed int and classical loop statements wherever possible.

Interestingly enough the C++ compiler I use does not warn about the first incorrect statement, even in the highest warning level. It warns however when it encounters a while (true) statement. But then it suggests to use a never ending for loop ( for (;;) )instead. Probably this is the reason why never ending for loops don't raise a compiler warning in Visual C++.

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.