Perft speed and depth questions

[ajaxuk]

minor addition... each "bucket needs to have the low order 6 bits of the address as 000000, which makes each bucket lie on an address that starts a 64 bit block of memory that gets read in in one cache fill cycle. If it spans a 64 bit address break, it will take two cache fill cycles which is bad for speed and also kicks out an extra cache entry that might be useful.

Thank you bob, I have bookmarked this tip for when I implement buckets.

[mvanthoor]

Well, its a basic implementation of hash tables and no buckets as of yet. Also, I am a little surprised at how much slower everything is running now I have included incremental hashing of posiitons.

Obviously, doing incremental updates slows down make_move and unmake_move. However, recalculating everything from scratch after each move is even slower, obviously. In my case, I also keep incremental material counters while making the moves, which slows down perft, but I need those later, so I don't have to recalculate them from scratch each time the evaluation function runs.

Relative times in seconds are below for Perft(7) of initial posiion run on my laptop (bit of a coach potatoe..)

Vanila Perft = 235 seconds
Perft + Bulk Counting = 94 seconds
Perft + Hash table = 65 seconds
Perft + Hash Table + Bulk Counting = 31 seconds

So my current implementation of the Hash table sped up by approx. 3.5 times.

I think I will put buckets on the todo list and move onto the next stage.

Your time needed when using the hash, as compared to not using it, is 65 / 235 & * 100 = 26.7%. The hash table therefore yields a 73.3% speed gain. That is not super ultra fast, but it's in the expected ball park. My first implementation of a hash table gained me about 70% or so, and after optimization, it gains up to 85% in some positions. So yes, you could gain some speed by more/better optimization, but the hash table is not slow.

What would be the next step? I assume it will be to start evaluating or scoring a Board position in isolation?

Keep evaluation extremely simple, just like a beginner does. There are engines around that have almost no evaluation, such as PeSTO:

PeSTO @ CCRL Blitz

It stands for PiecE SQuare Table Only. This engine has, as far as I've been able to gather from the forums, no evaluation beside counting material, and highly optimized Piece Square Tables. So, you could reach 3100 by having almost no evaluation, and just using specialized PSQT's.

Therefore, keep evaluation extremely simple in the beginning. Write a function that counts material when you start the engine (using piece values), and then keep that value incrementally updated. That will be the base for your evaluation. Then add the terms from the PSQT's, so the engine knows what would be good squares for a piece. (Otherwise, your evaluation would be 0.00 for every move, and the choice is essentially random.)

Then write the search (this is the point where I'm now at, after a pause of almost 5 weeks): create a super clean alpha/beta function without any bells and whistles, that uses this simple evaluation function. (You will then need to add iterative deepening and some time management to be able to actually play.)

If you want to test your engine without having to implement UCI first, you could implement a small console-based interface, so you can play against it by manually putting in moves such as 'e2e4', etc.

Then add UCI and/or XBoard, and you'd be done. (If you want your engine to run under XBoard/WinBoard, start with XBoard. If you want it to run in a ChessBase GUI, implement UCI first. For some GUI's, it doesn't matter because they support both.)

Then, you'd be finished, and you'd have a bare-bones chess engine.

By the way: you stated you never programmed before. I wonder how you can just jump right in and start writing a chess engine in C++. Many programmers, even experienced ones, have tried to write and finish a chess engine, and failed. (But granted; the cases I know of where from before the time of a plethora of information on the internet, free for the taking. Since engines such as Fruit became open source, writing a chess engine became a lot 'easier'; not straight forward or trivial per se, but with much more and better information out there, greatly increasing the chances of success, and decreasing the chances of getting permanently stuck.)

[ajaxuk]

Great help, thank you for the tips on PeSTO, I will look more into it.

It's not that I have never programmed before, just that I am not a programmer by profession and so all i have learned is from books and practice. If a professional programmer looked at my code they would cringe. My first experiences with programming go back to the very early eighties when I had a PCC2000 and access to a friends TRS-80. I would get the latest computer magazine and spend 30 minutes typing in the code for a simple game and then 3 hours trying to debug it... Unfortunately I have never really advanced past this BASIC knowlegde and only relatively recently given a look at C++, which is a steep learning curve in comparrison.

[alessandro]

The one thing I'm curious about... [...] Is AdaChess experimental? What I mean is: are you implementing "non-standard" features/your own idea's, or implementing standard features in a different way, to see if they work, or work better?

AdaChess is not experimental but yes, the idea behind the engine is implementing many custom features also when they have a negative impact on the playing strength. My philosophy is: is a cool things to implement? If so, then I want to implement it