writing a chess engine

[lucasart]

Hello everyone,

I am currently writing a chess engine in C++, and thought I should share some ideas, and ask for some guidance from those chess programming gurus like Robert Hyatt, Tord Romstad, Marco Costalba, Robert Houdart, and surely many others I don't know or forgot to mention.

At the moment it doesn't even play a game of chess, but here's what I have done:

Generally I coded everything from scratch, as I believe in self teaching by trial and error, rather than copying ready made solutions.

1/ Bitboards:
* I used my own implementation of rotated bitboards, adapted from my old code (BibiChess 0.5), just cleaned up a little.
* For bit looping and counting, I used the nice bit-tricks from StockFish.
* Nowadays people use magic bitboards, but since I don't understand them, I am not going to copy some code that I don't understand (imagine debugging it, lol). I might do it in the future, once I get down to understanding how it works.

2/ Board:
* Writing a bug-free and efficient Board class, and move generators, was quite a long and painful process. But using defensive programming techniques, as I learnt from reading SF for guidance, paid off (lots of assert, use encapsulation and limit side effects)
* my move generators generate directly legal moves, never pseudo-legal ones. It was somewhat simpler, and not very costly, although everyone else uses pseudo legal moves, since beta-cutoffs avoid checking legality of moves never searched.

3/ MoveSort:
* following the idea of the MovePicker class in SF, I did a MoveSort class. Much simpler, it allows reading moves in descending sort score in a nice encapsulated way.
* my sort works as follows: TT move first (if available), good captures (by descending SEE), non-captures (by History scores), bad captures.
* the problem I see is that many SEE!=0 moves have the same SEE, and they don't get sorted. For example if 5 moves score SEE=1 Pawn, then they are just sorted as they come from the move generator. Is there any simple way to improve this ?
* Also, I saw in SF that winning captures are sorted by MVV/LVA. It didn't seem that good in my test, so I stayed with my general SEE sorting.

4/ History
* I used the same history scoring as SF: add d*d when good and substract d*d when bad, scale down the history scores when we exceed a threshold. The impact of history scores in the move ordering are not increasing the search speed as I naively imagined they would.
* But if everyone else does it, it can't be bad, and must payoff in the long run (like in late move reductions, or history pruning)

5/ Quiescent Search
* moves considered: captures only, or evasions if in check.
* SEE pruning: don't search moves with < 0 SEE. First I wanted to exclude checking moves from this condition, but I realised that (in general) it didn't make much sense (since the checking piece is going to be captured anyway, although it can miss some forced mated in rare cases such as 1. f4 e5 2. fxe5 d6 3. exd6 Bxd6 4. Nc3? Qh4+ etc.)
* transposition table

6/ Search
* alpha-beta + PVS: At PV node, only the first move is search with full window, otherwise a zero window is tried first (if fails high, then re-search full window).
* transposition table
* razoring, at depth <= 3. I was quite sceptical about it, but it prunes a lot more than I thought, so for whatever it may miss the overall gain is probably significant.
* IID: when no TTable move available, and deph is big enough. Search depth/2 for a good move to start with. Use different min depth for PV and non PV nodes, following the idea of SF.
* For now I don't use: null move pruning, history pruning or late move reduction, futility pruning, aspiration, and surely many other tricks. I just want to make sure the little I have works robustly and harmoniously, before I start breaking it . Any suggestion what to begin with ?

7/ Eval
* I litteraly have no eval t the moment. The last thing I'm interested in. Only when the search is efficient and stable will I start doing one (if the former ever happens...)
* Using piece on square table material score only.
* I'm just wondering: what's the simplest way to make an eval that would be ok-ish ? I'm considering psq tables + mobility only, following the minimalistic approach of the earlier versions of Fruit.
* Generally, I'd much rather solve problems by search improvements than spending time doing speculative eval code to compensate the weakness of the search. Which is why I force myself not to write an eval for now.

Of course, what you take from the free software community, you must give it back. It's only fair. So if ever I make something decent and useable, it will be released under GNU GPL.

[mcostalba]

Generally I coded everything from scratch, as I believe in self teaching by trial and error, rather than copying ready made solutions.

In this case you should remove at least 2 names from the list of gurus (one being myself)


BTW Could you please anwser to my question in the "compiling stockfish" thread, I want to be sure we are not broken on any platform. Thanks.


Coming back to your post the main 2 things I'd suggest before to start (in case you are quite serious with your developing and not only an easy fun) are these:

1) Setup a proper revision control repository. We use git and we are very happy with this.

2) Setup a proper and standardized testing procedure. Probably at this time of development you _still_ don't need thousand of games to validate a change, anyhow it is a good practice to define a testing procedure and stick to it.

3) Do not commit any change if is not validated either with testing on real games if is a functionality-change pacth or with verification that is a "no functionality change" patch in case is a cleanup or an optimization. Corollary of this is to setup a benchmark() function like the one in SF, for instance, that you'd use to verify no-functionality changes by the mean that node counts before and after the change must remian the same.

[lucasart]

In this case you should remove at least 2 names from the list of gurus (one being myself)

Don't be hard on yourself. I know that Glaurung already had all the main features when you started StockFish. But I also know that your improvements on StockFish were significant and non trivial (ie. not just fine-tuning eval parameters and butchering the search like the so-called "improvements" of Toga over Fruit), and the search algorithm has done some large progress since you started StockFish. And if Tord preferred to fork on SF rather than him own Glaurung 2.2, then your changes can't have been silly ones!

Of course, Robery Hyatt is the founding father of modern computer chess Also, I would say that Fabien Letouzey later revolutioned computer chess, followed by Tord Romstad. And in the end, the morale is that (as usual) only free software promotes progress.

BTW Could you please answer to my question in the "compiling stockfish" thread, I want to be sure we are not broken on any platform. Thanks.

I did what you said, it works fine, and the file ./stockfish is created and works.

Coming back to your post the main 2 things I'd suggest before to start (in case you are quite serious with your developing and not only an easy fun) are these:

1) Setup a proper revision control repository. We use git and we are very happy with this.

2) Setup a proper and standardized testing procedure. Probably at this time of development you _still_ don't need thousand of games to validate a change, anyhow it is a good practice to define a testing procedure and stock to it.

3) Do not commit any change if is not validated either with testing on real games if is a functionality-change patch or with verification that is a "no functionality change" patch in case is a cleanup or an optimization. Corollary of this is to setup a benchmark() function like the one in SF, for instance, that you'd use to verify no-functionality changes by the mean that node counts before and after the change must remain the same.

1/ I'll be alone on this, so perhaps just piling up tar-balls with a date in the name or something like that. I'm sure that git is great for large projects, if shared by several developers. The very fact that Linus Torvaldes himself did it, and that the Linux kernel is being developed (by thousands of people) using git must mean that it's very good.

2 and 3/ You're right, it's worth spending a little time to code a benchmark function. I'll have a look at the one in SF and do something similar. I already do a 6 chosen positions perft test to validate changes in the Board class and move generation. Also I have a look at profiling results every now and then, but raw speed is not my main concern at this point (searching typically takes alpha.b^n time, so reducing b is the first step, and then I'll have a look at reducing alpha).

[michiguel]

Hello everyone,

I am currently writing a chess engine in C++, and thought I should share some ideas, and ask for some guidance from those chess programming gurus like Robert Hyatt, Tord Romstad, Marco Costalba, Robert Houdart, and surely many others I don't know or forgot to mention.

At the moment it doesn't even play a game of chess, but here's what I have done:

Generally I coded everything from scratch, as I believe in self teaching by trial and error, rather than copying ready made solutions.

1/ Bitboards:
* I used my own implementation of rotated bitboards, adapted from my old code (BibiChess 0.5), just cleaned up a little.
* For bit looping and counting, I used the nice bit-tricks from StockFish.
* Nowadays people use magic bitboards, but since I don't understand them, I am not going to copy some code that I don't understand (imagine debugging it, lol). I might do it in the future, once I get down to understanding how it works.

2/ Board:
* Writing a bug-free and efficient Board class, and move generators, was quite a long and painful process. But using defensive programming techniques, as I learnt from reading SF for guidance, paid off (lots of assert, use encapsulation and limit side effects)
* my move generators generate directly legal moves, never pseudo-legal ones. It was somewhat simpler, and not very costly, although everyone else uses pseudo legal moves, since beta-cutoffs avoid checking legality of moves never searched.

3/ MoveSort:
* following the idea of the MovePicker class in SF, I did a MoveSort class. Much simpler, it allows reading moves in descending sort score in a nice encapsulated way.
* my sort works as follows: TT move first (if available), good captures (by descending SEE), non-captures (by History scores), bad captures.
* the problem I see is that many SEE!=0 moves have the same SEE, and they don't get sorted. For example if 5 moves score SEE=1 Pawn, then they are just sorted as they come from the move generator. Is there any simple way to improve this ?
* Also, I saw in SF that winning captures are sorted by MVV/LVA. It didn't seem that good in my test, so I stayed with my general SEE sorting.

4/ History
* I used the same history scoring as SF: add d*d when good and substract d*d when bad, scale down the history scores when we exceed a threshold. The impact of history scores in the move ordering are not increasing the search speed as I naively imagined they would.
* But if everyone else does it, it can't be bad, and must payoff in the long run (like in late move reductions, or history pruning)

5/ Quiescent Search
* moves considered: captures only, or evasions if in check.
* SEE pruning: don't search moves with < 0 SEE. First I wanted to exclude checking moves from this condition, but I realised that (in general) it didn't make much sense (since the checking piece is going to be captured anyway, although it can miss some forced mated in rare cases such as 1. f4 e5 2. fxe5 d6 3. exd6 Bxd6 4. Nc3? Qh4+ etc.)
* transposition table

6/ Search
* alpha-beta + PVS: At PV node, only the first move is search with full window, otherwise a zero window is tried first (if fails high, then re-search full window).
* transposition table
* razoring, at depth <= 3. I was quite sceptical about it, but it prunes a lot more than I thought, so for whatever it may miss the overall gain is probably significant.
* IID: when no TTable move available, and deph is big enough. Search depth/2 for a good move to start with. Use different min depth for PV and non PV nodes, following the idea of SF.
* For now I don't use: null move pruning, history pruning or late move reduction, futility pruning, aspiration, and surely many other tricks. I just want to make sure the little I have works robustly and harmoniously, before I start breaking it . Any suggestion what to begin with ?

7/ Eval
* I litteraly have no eval t the moment. The last thing I'm interested in. Only when the search is efficient and stable will I start doing one (if the former ever happens...)
* Using piece on square table material score only.
* I'm just wondering: what's the simplest way to make an eval that would be ok-ish ? I'm considering psq tables + mobility only, following the minimalistic approach of the earlier versions of Fruit.
* Generally, I'd much rather solve problems by search improvements than spending time doing speculative eval code to compensate the weakness of the search. Which is why I force myself not to write an eval for now.

Of course, what you take from the free software community, you must give it back. It's only fair. So if ever I make something decent and useable, it will be released under GNU GPL.

Do not use a super simple eval. Most of the margins you will use in your search will be completely misleading. In Chess programming wiki there is one description of how to make a minimalistic eval that may not be too incomplete.

Miguel

[michiguel]

In this case you should remove at least 2 names from the list of gurus (one being myself)

Don't be hard on yourself. I know that Glaurung already had all the main features when you started StockFish. But I also know that your improvements on StockFish were significant and non trivial (ie. not just fine-tuning eval parameters and butchering the search like the so-called "improvements" of Toga over Fruit), and the search algorithm has done some large progress since you started StockFish. And if Tord preferred to fork on SF rather than him own Glaurung 2.2, then your changes can't have been silly ones!

Of course, Robery Hyatt is the founding father of modern computer chess Also, I would say that Fabien Letouzey later revolutioned computer chess, followed by Tord Romstad. And in the end, the morale is that (as usual) only free software promotes progress.

BTW Could you please answer to my question in the "compiling stockfish" thread, I want to be sure we are not broken on any platform. Thanks.

I did what you said, it works fine, and the file ./stockfish is created and works.

Coming back to your post the main 2 things I'd suggest before to start (in case you are quite serious with your developing and not only an easy fun) are these:

1) Setup a proper revision control repository. We use git and we are very happy with this.

2) Setup a proper and standardized testing procedure. Probably at this time of development you _still_ don't need thousand of games to validate a change, anyhow it is a good practice to define a testing procedure and stock to it.

3) Do not commit any change if is not validated either with testing on real games if is a functionality-change patch or with verification that is a "no functionality change" patch in case is a cleanup or an optimization. Corollary of this is to setup a benchmark() function like the one in SF, for instance, that you'd use to verify no-functionality changes by the mean that node counts before and after the change must remain the same.

1/ I'll be alone on this, so perhaps just piling up tar-balls with a date in the name or something like that. I'm sure that git is great for large projects, if shared by several developers. The very fact that Linus Torvaldes himself did it, and that the Linux kernel is being developed (by thousands of people) using git must mean that it's very good.

USE GIT!!!!!

I am also alone and my productivity skyrocketed with GIT.

2 and 3/ You're right, it's worth spending a little time to code a benchmark function. I'll have a look at the one in SF and do something similar. I already do a 6 chosen positions perft test to validate changes in the Board class and move generation. Also I have a look at profiling results every now and then, but raw speed is not my main concern at this point (searching typically takes alpha.b^n time, so reducing b is the first step, and then I'll have a look at reducing alpha).

Implement an epd test function, and you can change you test set anytime. Besides, it has other important functions.

Miguel

[lucasart]

Implement an epd test function, and you can change you test set anytime. Besides, it has other important functions.
Miguel

Oh yes, that's true. For now my razoring and IID use margins based on the static eval... I'll have a look and makr a simple eval.

[lucasart]

Do not use a super simple eval. Most of the margins you will use in your search will be completely misleading. In Chess programming wiki there is one description of how to make a minimalistic eval that may not be too incomplete.
Miguel

Oh yes, that's true. For now my razoring and IID use margins based on the static eval... I'll have a look and makr a simple eval.

[Milos]

Marco's advices are really the essence.
Two more things to add.
1. Carefully choose benchmark positions for functionality validation. You have to be sure that any change in functionality, even the smallest one is caught with your benchmark, otherwise you could be in trouble.
2. Regrading testing the golden rule is: it's always better more fast then less slow games if total testing time is equal.

[lucasart]

Hello everyone,

That's it, my chess engine played its first game without crashing or bugging. And my prey was Pychess 0.10rc1, which is a lame 1500 elo-ish (just guessing ?) program written in Python:

Code: Select all

[Event "Local Event"]
[Site "Local Site"]
[Round "1"]
[Date "2010.12.13"]
[White "Lucas"]
[Black "PyChess 0.10rc1"]
[Result "1-0"]

1. Nf3 d5 2. d4 Nf6 3. Nc3 Ne4 4. e3 Nxc3 5. bxc3 Nd7 6. Bd3 e6 7. O-O c6 8.
Bd2 Ba3 9. e4 dxe4 10. Bxe4 f6 11. Qb1 O-O 12. Qb3 Qe7 13. Rae1 Bd6 14. Bf5 Nb6
15. Bxe6+ Bxe6 16. Rxe6 Qf7 17. Rxd6 Nc4 18. Bf4 Kh8 19. Nd2 Nxd6 20. Bxd6 Qxb3
21. Nxb3 Rfd8 22. Bf4 Rg8 23. Nc5 b6 24. Ne6 Rae8 25. Re1 Re7 26. Bd6 Rf7 27.
h3 Re8 28. Re4 Rg8 29. Re3 b5 30. Kf1 Rc8 31. Bf4 Kg8 32. Ke2 Kh8 33. Kd3 Rd7
34. Nc5 Rd5 35. Re7 g5 36. Ne4 Rf8 37. Bd2 a5 38. Re6 c5 39. Nxc5 Kg8 40. f3 a4
41. Rb6 Rfd8 42. Ne4 Kh8 43. Nxf6 R5d6 44. Rxd6 Rxd6 45. Bxg5 Re6 46. Ne4 Kg7
47. d5 Rg6 48. g4 Kg8 49. Bf4 h6 50. Nd6 Rf6 51. Ke3 Kh7 52. Nxb5 Kg6 53. d6
Kf7 54. Nc7 Rg6 55. h4 Kf8 56. h5 Rg8 57. g5 hxg5 58. Bxg5 Rxg5 59. Ne6+ Ke8
60. Nxg5 Kd7 61. h6 Kxd6 62. h7 Ke5 63. h8=Q+ Kf5 64. Qg7 a3 65. Qh6 Ke5 66.
Qe6# 1-0

It's quite pathetic to see how long it took to win, wasting time manoeuvering to gain a pawn or whatever, instead of going for a crushing with King+central pawns. But this is expected, as I have NO eval yet, just interpolated piece on square table (in particular the psq for king at endgame made it advance the king, otherwise it might have stayed on forever and drawn a winning game by 50 move or sth like that).

Perhaps its time to extend 7-th rank threats

[lucasart]

I've made some big improvements. Mainly bugfixes and more efficient and precise search pruning. Now it seems to beat Gnu Chess 5.07 consistently, which is probably around 2200 elo. Here's an example game, as you can see it only wins by tactics and its positional knowledge is almost zero (piece on sq tables + bishop pair for material, and my own "innovative" measure of mobility using an sqrt(nb of squares) idea). Quite encouraging anyway, as my previous enging never beat Gnu Chess

Code: Select all

[Event "Local Event"]
[Site "Local Site"]
[Round "1"]
[Date "2010.12.18"]
[White "GNU Chess 5.07"]
[Black "Lucas"]
[Result "0-1"]

1. d4 Nf6 2. c4 e6 3. Nf3 d5 4. Bg5 Nc6 5. Nc3 Bb4 6. Qa4 h6 7. Bxf6 Qxf6 8.
cxd5 exd5 9. Rc1 O-O 10. e3 Rd8 11. Bb5 a5 12. O-O Bf5 13. a3 Be7 14. Ne2 Bg4
15. Nd2 Bd6 16. Rfe1 Qh4 17. g3 Qg5 18. Bxc6 bxc6 19. Qxc6 Rab8 20. Qc3 Re8 21.
Nf4 Rb5 22. h4 Qd8 23. f3 Bf5 24. Kf2 g5 25. Ng2 Qf6 26. Qc6 Reb8 27. b3 Qd8
28. Ra1 gxh4 29. gxh4 R8b6 30. Qc3 Qf6 31. Rec1 Rb7 32. Ke2 c5 33. f4 Rc7 34.
dxc5 Qg6 35. Kf2 Rbxc5 36. Qb2 Rc2 37. Rxc2 Rxc2 38. Qd4 Bd3 39. Rd1 Qg4 40.
Qxd3 Qxd1 41. Kg3 Rxd2 42. Qa6 Qc2 43. Qf1 Bxa3 44. Qf3 Bd6 45. Qg4+ Kf8 46.
Kh3 Ke7 47. h5 Qxb3 48. Qh4+ Ke6 49. Qg4+ Ke7 50. Qh4+ Kd7 51. Qg4+ Kd8 52. Qf5
Ke7 53. Kg3 Qd1 54. Qh3 Qg1 55. Qh4+ f6 56. Qh3 Rf2 57. Qh2 Rf3+ 58. Kxf3 Qxh2
59. Kf2 a4 60. Kf1 a3 61. Ne1 a2 62. Ng2 a1=Q+ 63. Ke2 Qxg2+ 64. Kd3 Qb1+ 65.
Kd4 Qd2# 0-1

Amongst other things, I noticed a huge increase in tactical precision when I refined the SEE pruning in the QS to exclude: the TT move + PV nodes + Checking moves.

And of course no SEE pruning when the node itself is in check, although SF seems to do it with success by pruning certain non capture evasions, I'll probably test something that later).[/list]