MCEC anyone?

[lithander]

What would the fans want me to do? (I'm really undecided here... as you can see)

The fans want a better MMC, they want TT and winning endgames

Your wish is my command! It's settled then: MMC isn't done just yet.

PST is indeed a trivial enhancement of having just material + centralization. But I would say tapering is just a small refinement, of which there would be dozens that would perhaps bring more playing strength.

Because I had no other evaluation terms it was impossible to make sure the King stays safe in the early game but assumes a more active role in the endgame. I assumed that tapered eval would easily fix that and it did.

If MMC exhibits strong positional play now until it bungles the endgame due to a lack of search depth (as amanj said) then it must already have a good evaluation function. And it's amazing for me to think that all this chess knowledge is encoded in two sets of PSTs and a 13th table for mobility-like dynamic bonuses. Everything it knows about king safety, pawn structure etc is implicitly encoded in these few hundred integer values. To me that was quite a surprise that it works so well. But I'm sure these good results wouldn't have been possible with non-tapered (e.g. 6 tables) PSTs only - or am I wrong there?

And I don't think the concept of a TT would even have to be explained to a non-programmer. Every chess player knows what a transposition is.

Good point. I didn't know the concept (not a chess player) and thought it's just another optimization trick. But reading more about it it seems I've accidentally omitted a rather critical component of any decent chess engine.

"Ease of understanding" is much more difficult to quantify. And, as this discussion shows, much less objective.

Absolutely. Turns out writing a "simple" engine isn't as easy as I thought. Maybe I should have learned the best practices first before challenging them but now it's too late to make MMC my 2nd engine!

I think micro-Max' algorithm would be quite easy to understand, even the TT (which is implemented through just a hand full of statements).

I'll have a closer look and maybe take inspiration because, even if MMC will receive a TT table now, I'm still inclined to make that as simple and minimal as possible, of course! I hope to stay below 1000 LOC for version 1.0. Which is just an arbitrary goal just as reaching 2k ELO was but still it's a goal. LOC means the number of instructions in the intermediate language the .Net Runtime executes. Visual Stuido counts it for you. So it's a bit like what looking at the size of the executable would be in C. It's also a somewhat objective metric for simplicity of a C# program. (Don't look at the actual size of my executable! It packs the whole runtime and all dependencies, making it ridiculously large.)

I'm looking forward to trying TT's now and feel convinced now that it's a feature within scope of what MMC tries to be. Thanks guys for helping me make that decision! My ignorance clouds my vision and so I'm truly grateful this community of chess programming veterans and excellent chess players exists

[mvanthoor]

Your wish is my command! It's settled then: MMC isn't done just yet.

But... how are you going to implement the TT?

Are you just adding a very simple TT for playing, with a fixed size, so it's very minimal? Are you going to just use entries, or make it more efficient by using buckets with 2-4 entries? Or are you going to add UCI-options to set the size in megabytes.... and maybe even the number of entries per bucket?

If you also want to use the TT in perft (which would be a good idea to test if it's working), you would need to store different data than you'd need to store during play. To avoid implementing multiple TT's, you could make it generic like I did, so it accepts PerftData and HashData. Obviously you'd need to have some type of interface to the TT to make it polymorphic.

Then you're very close to also using it as a pawn hash TT, which makes implementing pawn-based evaluations much faster.

Or you could just implement a single, fixed-size TT.

Hope this helps



(I'm just kidding. A TT is definitely not minimal. A tapered implementation is a simple enhancement of having only PST's, but the tuner is not minimal. Still, the tuner adds nothing to the engine itself. IMHO, MinimalChess 0.4.1, or _maybe_ the version with the dynamic component should become 1.0, and the next version should be a different engine. For people who have some experience, and especially the ones who wrote multiple engines, a TT is doable and understandable, but for someone wanting to write a new engine, it's one of the very hardest things to get right. Explanations are often sketchy, especially with regard to mate scoring and saving of the alpha/beta bounds.)

[mvanthoor]

If MMC exhibits strong positional play now until it bungles the endgame due to a lack of search depth (as amanj said) then it must already have a good evaluation function.

Against an engine that is faster and sees deeper (i.e., Rustic), MinimalChess can also sometimes be axed by a tactical shot. I've seen several positions where MinimalChess is clearly better (but not yet winning), and then it plays a move that is completely obvious from a positional standpoint, but which doesn't work tactically. Often I myself don't immediately see that the move is a mistake until Rustic sacrifices some a bishop and a pawn, plays a few forced moves, and then MinimalChess has the choice of being mated or lose its queen due to a knight fork. Then it's downhill from there. The chance of this happening becomes greater as the game progresses.

On the other hand, I've seen Rustic being steam-waltzed positionally, forced back against the last two ranks with no obvious way of getting counterplay. But... then MinimalChess often can't find the tactical shots in the position, and grinds Rustic down positionally in a 175 move game. (An overwhelmingly good position -must- have tactical shots available. It's inevitable. Tactics come from good positions and piece activity on your side, or passivity on the side of the opponent.)

And it's amazing for me to think that all this chess knowledge is encoded in two sets of PSTs and a 13th table for mobility-like dynamic bonuses. Everything it knows about king safety, pawn structure etc is implicitly encoded in these few hundred integer values. To me that was quite a surprise that it works so well. But I'm sure these good results wouldn't have been possible with non-tapered (e.g. 6 tables) PSTs only - or am I wrong there?

You're correct. What is correct positioning for pieces is different int he endgame as opposed to the opening and middle game. Therefore you need two sets of PST's.

I'll have a closer look and maybe take inspiration because, even if MMC will receive a TT table now, I'm still inclined to make that as simple and minimal as possible, of course!

Until you need it for perft and pawn hashing and material hashing and then for hashing the hashes of your minimal cryptominer, which by then will have learned to play chess by e-mailing back and forth with MinimalChess

I'm looking forward to trying TT's now and feel convinced now that it's a feature within scope of what MMC tries to be. Thanks guys for helping me make that decision! My ignorance clouds my vision and so I'm truly grateful this community of chess programming veterans and excellent chess players exists

If you're now around 2000 Elo, expect to hit 2150 or so. I wonder what tapering and tuning is going to bring for Rustic in the coming weeks. I _hope_ to fix the last part of the new build script (for the raspberry) just in time for an Alpha 3.0.0 release before I'm away for part of the weekend.

[amanjpro]

Against an engine that is faster and sees deeper (i.e., Rustic), MinimalChess can also sometimes be axed by a tactical shot. I've seen several positions where MinimalChess is clearly better (but not yet winning), and then it plays a move that is completely obvious from a positional standpoint, but which doesn't work tactically. Often I myself don't immediately see that the move is a mistake until Rustic sacrifices some a bishop and a pawn, plays a few forced moves, and then MinimalChess has the choice of being mated or lose its queen due to a knight fork. Then it's downhill from there. The chance of this happening becomes greater as the game progresses.

Not sure why do you think Rustic is faster and sees deeper than MMC, at least not in ZaTour. MMC sees as deep or deepr than Rustic (maybe because I use the latest dev version?)

This is their last decisive game in ZaTour Season one, MMC's depth is similar (if not better) than Rustic:

[pgn]
[Event "ZaTour - Test Run - Season 1"]
[Site "?"]
[Date "2021.06.15"]
[Round "65.3"]
[White "rustic-alpha-2"]
[Black "MinimalChessEngine"]
[Result "0-1"]
[ECO "A09"]
[GameDuration "00:27:53"]
[GameEndTime "2021-06-16T03:41:09.381 UTC"]
[GameStartTime "2021-06-16T03:13:16.025 UTC"]
[Opening "Reti"]
[PlyCount "57"]
[Termination "adjudication"]
[TerminationDetails "TCEC resign rule"]
[TimeControl "1500+2"]
[Variation "advance variation"]

{WhiteEngineOptions: Protocol=uci; Hash=256; Threads=1; CPU=1;, BlackEngineOptions: Protocol=uci; Hash=256; Threads=1; CPU=1;}
1. Nf3 {book, mb=+0+0+0+0+0,} d5 {book, mb=+0+0+0+0+0,}
2. c4 {book, mb=+0+0+0+0+0,} d4 {book, mb=+0+0+0+0+0,}
3. e3 {book, mb=+0+0+0+0+0,} Nc6 {book, mb=+0+0+0+0+0,}
4. exd4 {book, mb=+1+0+0+0+0,} Nxd4 {book, mb=+0+0+0+0+0,}
5. Nxd4 {book, mb=+0+1+0+0+0,} Qxd4 {book, mb=+0+0+0+0+0,}
6. Nc3 {book, mb=+0+0+0+0+0,} Nf6 {book, mb=+0+0+0+0+0,}
7. d3 {book, mb=+0+0+0+0+0,} c6 {book, mb=+0+0+0+0+0,}
8. Be3 {book, mb=+0+0+0+0+0,} Qd7 {book, mb=+0+0+0+0+0,}
9. Be2 {d=10, sd=28, mt=45672, tl=1456328, s=5988366, n=273494672, pv=Be2 e5 d4 Bd6 c5 Bc7 dxe5 Bxe5 Qxd7+ Bxd7 O-O, tb=null, h=94.1, ph=0.0, wv=0.30, R50=48, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
g6 {d=11, sd=11, mt=34358, tl=1467642, s=1141571, n=39219845, pv=g6 O-O Bg7 Bf3 O-O Rc1 Ng4 Bg5 Ne5 Be4 Ng4, tb=null, h=0.0, ph=0.0, wv=0.33, R50=50, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
10. Qa4 {d=9, sd=25, mt=57040, tl=1401288, s=6020788, n=342360064, pv=Qa4 e5 O-O Bd6 Ne4 Nxe4 dxe4 c5 Qc2, tb=null, h=99.9, ph=0.0, wv=0.60, R50=49, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
Bg7 {d=10, sd=10, mt=21995, tl=1447647, s=1157114, n=25450736, pv=Bg7 O-O-O O-O h3 Qc7 Rhe1 Rd8 Kb1 Bf5 Qc2, tb=null, h=0.0, ph=0.0, wv=0.15, R50=49, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
11. Qa3 {d=9, sd=30, mt=31599, tl=1371689, s=6825393, n=215675592, pv=Qa3 e5 O-O-O Qf5 f3 Bf8 g4 Qe6 Qb3, tb=null, h=99.9, ph=0.0, wv=0.60, R50=48, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
Qc7 {d=10, sd=10, mt=63261, tl=1386386, s=1164060, n=73639631, pv=Qc7 O-O O-O Rfe1 Bf5 Rad1 a6 Qb3 Ng4 Bxg4, tb=null, h=0.0, ph=0.0, wv=-0.13, R50=48, Rd=-21, Rr=5, mb=+0+0+0+0+0,}
12. Bxa7 {d=9, sd=27, mt=30714, tl=1342975, s=6379963, n=195947794, pv=Bxa7 Nd7 c5 Bd4 Bb6 Rxa3 Bxc7 Bxc3+ bxc3 Nxc5, tb=null, h=99.9, ph=0.0, wv=0.65, R50=50, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
O-O {d=9, sd=9, mt=15908, tl=1372478, s=1184846, n=18847352, pv=O-O O-O Be6 c5 Rfd8 Bb6 Qe5 Qb4 Rd4, tb=null, h=0.0, ph=0.0, wv=-0.92, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
13. O-O {d=9, sd=26, mt=61248, tl=1283727, s=6442227, n=383254528, pv=O-O Nd7 c5 Bd4 Bb6 Rxa3 Bxc7 Ra6 Ne4 Nxc5 Nxc5 Bxc5, tb=null, h=100.0, ph=0.0, wv=0.55, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
Be6 {d=10, sd=10, mt=32917, tl=1341561, s=1328042, n=43715182, pv=Be6 c5 Nd5 Rae1 Qf4 g3 Qf5 Nxd5 Bxd5 b4, tb=null, h=0.0, ph=0.0, wv=-0.71, R50=48, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
14. c5 {d=10, sd=29, mt=61970, tl=1223757, s=6717872, n=407371776, pv=c5 Nd7 Rac1 Bd4 Ne4 Qe5 Rc2 Bd5 Bf3 e6, tb=null, h=100.0, ph=0.0, wv=0.30, R50=50, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
Nd5 {d=9, sd=9, mt=18768, tl=1324793, s=1323050, n=24829693, pv=Nd5 Bf3 Nf4 Rad1 Qd7 Qa4 Nxd3 h3 Qd8, tb=null, h=0.0, ph=0.0, wv=-0.89, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
15. Nxd5 {d=10, sd=30, mt=62748, tl=1163009, s=6883939, n=419954688, pv=Nxd5 Bxd5 Rab1 Bd4 b3 Qb8 Bxb8 Rxa3 Bf4 Rxa2, tb=null, h=100.0, ph=0.0, wv=0.10, R50=50, Rd=-21, Rr=5, mb=+1+1+0+0+0,}
Bxd5 {d=10, sd=10, mt=26998, tl=1299795, s=1387625, n=37463104, pv=Bxd5 f4 e6 Rae1 Rfe8 Kh1 Qe7 Bf3 Bxf3 Rxf3, tb=null, h=0.0, ph=0.0, wv=-0.95, R50=50, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
16. Rab1 {d=9, sd=26, mt=63588, tl=1101421, s=7613456, n=483393536, pv=Rab1 Be5 h3 Bd4 Kh1 Bxa2 Ra1 Bd5 Kg1, tb=null, h=100.0, ph=0.0, wv=-0.05, R50=49, Rd=-20, Rr=5, mb=+1+0+0+0+0,}
Qf4 {d=10, sd=10, mt=34829, tl=1266966, s=1328101, n=46256458, pv=Qf4 g3 Qh6 Rfe1 Be5 Bf3 Bb8 Bxd5 cxd5 Rxe7, tb=null, h=0.0, ph=0.0, wv=-1.46, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
17. g3 {d=10, sd=28, mt=64498, tl=1038923, s=6925302, n=442499072, pv=g3 Qf5 g4 Qf4 Rfd1 f5 Rdc1 fxg4 Rf1 e5, tb=null, h=100.0, ph=0.0, wv=-0.80, R50=50, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
Qf5 {d=10, sd=10, mt=32617, tl=1236349, s=1309962, n=42727045, pv=Qf5 Qa4 Qh3 f3 Be5 Rfe1 Bb8 Bf1 Qd7 Qg4, tb=null, h=0.0, ph=0.0, wv=-2.41, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
18. Rbe1 {d=10, sd=28, mt=65494, tl=975429, s=6955194, n=452984832, pv=Rbe1 Bd4 g4 Qf4 Bd1 e6 Qa5 Be5 Rxe5 Qxe5, tb=null, h=100.0, ph=0.0, wv=-1.55, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
Bd4 {d=12, sd=12, mt=94790, tl=1143559, s=1399063, n=132615835, pv=Bd4 Bd1 Qh3 Re4 f5 Qb4 e5 Bb3 Kh8 Bxd5 fxe4 Bxe4, tb=null, h=0.0, ph=0.0, wv=-3.87, R50=48, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
19. Bd1 {d=10, sd=25, mt=66588, tl=910841, s=6587997, n=426770432, pv=Bd1 Qh3 Re4 f5 Bf3 fxe4 dxe4 Bxb2 Qxb2 Rxa7 exd5 Rxf3, tb=null, h=100.0, ph=0.0, wv=-3.05, R50=48, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
Qh3 {d=11, sd=11, mt=24534, tl=1121025, s=1344270, n=32980339, pv=Qh3 Re4 f5 Bb3 fxe4 dxe4 Be6 Qa4 Bxc5 Bxe6+ Qxe6, tb=null, h=0.0, ph=0.0, wv=-4.35, R50=47, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
20. Re4 {d=11, sd=28, mt=49805, tl=863036, s=6574288, n=327425857, pv=Re4 f5 Bb3 fxe4 dxe4 Bxb3 Qxb3+ e6 Qxb7 Qg4 e5 Bxe5, tb=null, h=100.0, ph=0.0, wv=-3.50, R50=47, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
f5 {d=11, sd=11, mt=26907, tl=1096118, s=1388161, n=37351265, pv=f5 Bb3 fxe4 dxe4 Rxf2 Rxf2 Rf8 Bxd5+ cxd5 exd5 Bxf2+, tb=null, h=0.0, ph=0.0, wv=-4.64, R50=50, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
21. Bb3 {d=10, sd=26, mt=70604, tl=794432, s=6621760, n=460324864, pv=Bb3 fxe4 dxe4 Rxf2 Rxf2 Bxf2+ Kxf2 Qxh2+ Kf1 Rf8+ Ke1 Qxg3+ Kd1 Qd3+ Kc1 Qxe4, tb=null, h=100.0, ph=0.0, wv=-4.20, R50=49, Rd=-21, Rr=5, mb=+1+0+0+0+0,}
fxe4 {d=11, sd=11, mt=20431, tl=1077687, s=1384275, n=28282132, pv=fxe4 Bxd5+ cxd5 Qa4 Bxc5 Qb3 Bxa7 Qxd5+ e6 Qxe4 Bc5, tb=null, h=0.0, ph=0.0, wv=-6.86, R50=50, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
22. Bxd5+ {d=10, sd=24, mt=72176, tl=724256, s=6403495, n=449839104, pv=Bxd5+ cxd5 Qa4 Bxf2+ Rxf2 e3 Rxf8+ Rxf8 Qf4 Rxf4 gxf4 Qg4+ Kh1 Qd1+ Kg2 Qxd3, tb=null, h=100.0, ph=0.0, wv=-7.55, R50=50, Rd=-21, Rr=5, mb=+1+0+1-1+0,}
cxd5 {d=11, sd=11, mt=28171, tl=1051516, s=1296113, n=36511505, pv=cxd5 Qa4 Rf5 Qxd4 Rh5 Rd1 Qxh2+ Kf1 Qh1+ Ke2 Qf3+, tb=null, h=0.0, ph=0.0, wv=-6.93, R50=50, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
23. Qb3 {d=10, sd=25, mt=63884, tl=662372, s=7284754, n=465371928, pv=Qb3 Qf5 c6 Rxa7 cxb7 Bxf2+ Kg2 Qf3+ Kh3 Qxd3 Qxd3 exd3, tb=null, h=100.0, ph=0.0, wv=-8.20, R50=49, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
Rf5 {d=11, sd=11, mt=26979, tl=1026537, s=1308370, n=35298526, pv=Rf5 c6 Rh5 Qxd5+ Rxd5 cxb7 Rad8 b8=Q Rxb8 Bxb8 exd3, tb=null, h=0.0, ph=0.0, wv=-9.81, R50=49, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
24. c6 {d=11, sd=26, mt=77260, tl=587112, s=5870727, n=451411968, pv=c6 b6 Bb8 Rxb8 dxe4 Rh5 Qxd5+ Rxd5 exd5 Rd8 c7 Rxd5, tb=null, h=100.0, ph=0.0, wv=-9.30, R50=50, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
Rh5 {d=11, sd=11, mt=20364, tl=1008173, s=1400566, n=28521140, pv=Rh5 Qxd5+ Rxd5 cxb7 Rad8 b8=Q Rxb8 Bxb8 Rh5 g4 Qxg4+, tb=null, h=0.0, ph=0.0, wv=-11.62, R50=49, Rd=-21, Rr=5, mb=+1+0+0-1+0,}
25. Qxd5+ {d=11, sd=28, mt=79842, tl=509270, s=6300686, n=493879296, pv=Qxd5+ Rxd5 cxb7 Rad8 b8=Q Rxb8 Bxb8 e3 Bf4 exf2+ Rxf2 Bxf2+ Kxf2 Qxh2+ Ke3 Qxb2, tb=null, h=100.0, ph=0.0, wv=-10.30, R50=50, Rd=-21, Rr=4, mb=+2+0+0-1+0,}
Rxd5 {d=12, sd=12, mt=14591, tl=995582, s=1384663, n=20203620, pv=Rxd5 cxb7 Rad8 b8=Q Rxb8 Bxb8 e3 Bf4 exf2+ Rxf2 Rf5 Be3, tb=null, h=0.0, ph=0.0, wv=-11.26, R50=50, Rd=-21, Rr=5, mb=+2+0+0-1-1,}
26. cxb7 {d=11, sd=22, mt=15140, tl=496130, s=6485676, n=96993280, pv=cxb7 Rb8 Bxd4, tb=null, h=100.0, ph=0.0, wv=-13.33, R50=50, Rd=-21, Rr=3, mb=+3+0+0-1-1,}
Rad8 {d=11, sd=11, mt=17917, tl=979665, s=1287353, n=23065518, pv=Rad8 b8=Q Rxb8 Bxb8 e3 Bc7 Rh5 g4 exf2+ Rxf2 Qxg4+, tb=null, h=0.0, ph=0.0, wv=-12.13, R50=49, Rd=-21, Rr=5, mb=+3+0+0-1-1,}
27. b8=Q {d=10, sd=20, mt=15246, tl=482884, s=7282286, n=104333312, pv=b8=Q Rxb8 Bxb8 Bxf2+ Rxf2 Rxd3 Rf7, tb=null, h=100.0, ph=0.0, wv=-11.88, R50=50, Rd=-21, Rr=2, mb=+2+0+0-1+0,}
Rxb8 {d=12, sd=12, mt=23182, tl=958483, s=1408712, n=32656779, pv=Rxb8 Bxb8 e3 Bf4 Rh5 g4 Rh4 Bg3 Rxg4 a3 exf2+ Rxf2, tb=null, h=0.0, ph=0.0, wv=-13.07, R50=50, Rd=-21, Rr=5, mb=+2+0+0-1-1,}
28. Bxd4 {d=9, sd=18, mt=15356, tl=469528, s=8079843, n=117440512, pv=Bxd4 Rxd4 Rb1 Rxd3 b3, tb=null, h=100.0, ph=0.0, wv=-14.13, R50=50, Rd=-21, Rr=1, mb=+2+0+1-1-1,}
Rh5 {d=11, sd=11, mt=7671, tl=952812, s=1266513, n=9715423, pv=Rh5 dxe4 Rxb2 Bxb2 Qxh2#, tb=null, h=0.0, ph=0.0, wv=-M1, R50=49, Rd=-21, Rr=5, mb=+2+0+1-1-1,}
29. Rd1 {d=9, sd=20, mt=15472, tl=456056, s=8162025, n=122683392, pv=Rd1 Rxb2 Bxb2 e3 Rd2 exd2 f4 Qxh2+ Kf1 d1=Q#, tb=null, h=100.0, ph=0.0, wv=-M10, R50=49, Rd=-21, Rr=0, mb=+2+0+1-1-1, Black wins by adjudication: TCEC resign rule}
0-1
[/pgn]

I do agree if you say Rustic sees wider, but that is not necessarily a good thing

[hgm]

A non-obfuscated version of micro-Max' TT code could look like this:

Code: Select all

typedef struct {
  int signature;
  int score;
  short int move;
  char depth;
  char flags
} TTentry;

int hashKeyH, hashKeyL;
TTentry tt[hashMask+1];


// In Search():

// hash probe
TTentry *e = tt + (hashKeyL + (128 + stm)*epSquare & hashMask);
iterDepth = e->depth;
bestScore = e->score;
bestMove  = e->move;
if(ply == 0 ||                                  // node is root
   e->signature != hashKeyH ||                  // hash miss
   score < beta  && !(e->flags & UPPERBOUND) || // fails low or PV is not an upper-bound
   score > alpha && !(e->flags & LOWERBOUND)    // score that fails high is not a lowe bound
  ) iterDepth = bestMove = 0; // if hash miss or unusable bound, start IID at depth 0

...

// hash store
  e->signature = hashKeyH;
  e->score = bestScore;
  e->move  = bestMove;
  e->depth  = iterDepth;
  e->flags = (bestScore > alpha)*LOWERBOUND | (bestScore < beta)*UPPERBOUND;

This is not entirely correct, because it does ignore castling rights in the hash key. (It could afford that, because castlings cannot be hash moves anyway in micro-Max.) also, the side to move and the e.p. square are worked into the hash key in a bit of a quirky way. The hash key is spit into two parts, one used to derive the index, the other used as signature. If you want these could be two halves of a uint64_t, which you shift to get the signature part. (The index part is already masked, with hashMask, which must be a power of 2 minnus 1.)

So basic idea is that it just stores (best) score, move and depth, and that a revisit would then use these as start values to continue where the previous visit left off. The trickiest part is the if statement, which decides when the retrieved values should not be used. That obviously should include the case of a hash miss, where the hash entry contained values for a different position. (I.e the signature did not match). In that case the node will behave like there was no bestMove, and starts iterating the depth from scratch to find one cheaply.

Then there are also the cases when the retrieved score is a bound that is not usable for the current search window. Micro-Max treats that the same as a hash miss.

Update of the hash key is not included in the shown code. You might already have that for repetition detection. For the purpose of repetition detection micro-Max has the entire hash store code secion inside an if(e->depth != MAXDEPTH+1), i.e. it refuses to overwite entries that report a depth of MAXDEPTH+1, which cannot have resulted from normal search. When a move is played at game level, it sets the depth field of the TT entry for the root to this value, the score to 0, and the flags to UPPERBOUND|LOWERBOUND, so that the game record gets 'frozen' in the hash table as an exact draw score of maximum depth, which will satisfy any hash request.

[mvanthoor]

Not sure why do you think Rustic is faster and sees deeper than MMC, at least not in ZaTour. MMC sees as deep or deepr than Rustic (maybe because I use the latest dev version?)

...

I do agree if you say Rustic sees wider, but that is not necessarily a good thing

Rustic has TT-move ordering, MinimalChess has PV-move ordering, which are basically the same thing. That makes them about equal in the middle game. MinimalChess also gains some speed because it has staged move generation, which Rustic doesn't. They both have killer moves. MinimalChess has a tapered and tuned evaluation, which Rustic doesn't; but Rustic has PVS.

In the middle game they can see to about equal depth, but as I said in my post, Rustic's chances come in the endgame, precisely because of the fact that MinimalChess does not have a TT. The more sliders that disappear from the baord, the more often Rustic will see deeper, and win the game purely on tactics, or by exploiting positions in pawn endings. See below:

[d]3r2k1/5ppp/p7/1p6/2b5/P4B1P/1P3PP1/4R1K1 w - - 0 1

MinimalChess 0.4.1 can see to depth 9 in 17 seconds:


Rustic reaches this depth in about one second:


And Rustic reaches depth 11 in 21 seconds:


I didn't bother to wait before MinimalChess reaches depth 10, let alone 11.

This is purely because of the TT. The larger the TT is, and the longer the time control is, the more often Rustic 2.2.100 can defeat MinimalChess 0.4.1 on tactics. (There are obviously diminishing returns.)

MinimalChess will gain a massive amount of strength after it adds a TT; if all is well, I'd expect it to add 140-150 Elo on top of the rating the dev version may now already have.

To become equal in features, Rustic needs to add:
- Tapered and tuned evaluation
- Dynamic evaluation (variant of Mobility)
- Staged move generation

MinimalChess needs to add:
- PVS
- Transposition table

At that point, the only difference will be the speed difference between Rust and C#, and the difference between an 8x8 mailbox move generator and bitboards. If everything is equal except programming language and type of move generator (which was the case between MinimalChess 0.3 and Rustic Alpha 1), I expect Rustic to be about 80-100 Elo stronger because it is roughly 3-4 times as fast.

The CCRL rating of MinimalChess 0.3 is 1570, where Rustic is 1675... which is exactly to my expectation.

If the current dev-version of MMC is now at around 2000, adding a TT will lift it to 2150, because it will be able to actually convert much more its good positions due to being able to see deeper.

PS: Both engines should see equally wide. AFAIK, MinimalChess has no pruning yet, and Rustic doesn't either.

PS II: In the above example, you can also see that MMC is positionally superior due to its tapered and tuned eval. 1. Re7 is the better move as it's much more active than 1. b4.

[lithander]

The version that is playing in Amanj's tournament is 0.4.4 while the last public release is 0.4.1. (of course everyone could just build 0.4.4 from source)

0.4.4 has something akin to PVS search (nullwindow-sized scouting before full-width search if distance to leaf is >= 4) and it has null move pruning with depth reduction. That's why it searches deeper now than Rustic. Sorry for the confusion but I wanted to submit the strongest version I had.

For people who have some experience, and especially the ones who wrote multiple engines, a TT is doable and understandable, but for someone wanting to write a new engine, it's one of the very hardest things to get right. Explanations are often sketchy, especially with regard to mate scoring and saving of the alpha/beta bounds.

You make it sound incredibly hard...

A non-obfuscated version of micro-Max' TT code could look like this:

...and Harm Geert makes it sound almost trivial.

I'm curious what my own experience will be.

[amanjpro]

The version that is playing in Amanj's tournament is 0.4.4 while the last public release is 0.4.1. (of course everyone could just build 0.4.4 from source)

0.4.4 has something akin to PVS search (nullwindow-sized scouting before full-width search if distance to leaf is >= 4) and it has null move pruning with depth reduction. That's why it searches deeper now than Rustic. Sorry for the confusion but I wanted to submit the strongest version I had.

For people who have some experience, and especially the ones who wrote multiple engines, a TT is doable and understandable, but for someone wanting to write a new engine, it's one of the very hardest things to get right. Explanations are often sketchy, especially with regard to mate scoring and saving of the alpha/beta bounds.

You make it sound incredibly hard...

A non-obfuscated version of micro-Max' TT code could look like this:

...and Harm Geert makes it sound almost trivial.

I'm curious what my own experience will be.

If you have ever done dynamic programming, then it should be fairly easy to implement. But to make sure you have no bugs, it might be hard. The concept is super simple, but it is super easy to make mistakes (brains fart)

[mvanthoor]

0.4.4 has something akin to PVS search (nullwindow-sized scouting before full-width search if distance to leaf is >= 4) and it has null move pruning with depth reduction. That's why it searches deeper now than Rustic. Sorry for the confusion but I wanted to submit the strongest version I had.

If you have something akin to PVS, we can scrap that advantage for Rustic, and null move is a massive search depth booster with two, sometimes even three ply (depending on position and engine speed), even measured without TT. No wonder MMC now searches deeper than Rustic. I'll either wait for your official release, or build 0.4.4 myself someday.

MMC is a good stable engine to have around in several versions when testing. (I hope Rustic was/is going to be the same for others with the next 2-3 releases.)

You make it sound incredibly hard...

It's not incredibly hard to build, but if you're going at this for the first time, the hardest thing is getting correct, complete information, especially if you're not reading code from "known good engines" (I'm implementing everything without reading code). It's the reason why I'm writing that book/tutorial: because I'm not satisfied with lots of the sources of information I found. (Obviously, there are good ones, too.)

Because of mistakes in sources of information or wonky implementations you may find, It is incredibly easy to make a simple mistake which will cause you to not gain the Elo you expect. If you have additional other functions, errors in the TT might even kill those functions as well.

See this topic where it happened to me, because I understood one of the (actually correct) sources the wrong way because of a non-optimal implementation:
http://talkchess.com/forum3/viewtopic.php?f=7&t=76887

You actually participated in it

I'm curious what my own experience will be.

You'll implement the TT, and if you make no mistakes, it's actually somewhat trivial.

If you have an error somewhere, you'll not notice it, except for the fact that you don't gain enough Elo, or your strength even decreases. Debugging the TT can be very hard, so I'd make sure that it's correct before you do something new after it.

[mvanthoor]

And make sure you look into "mate score handling" for the TT, or you'll find that your engine suddenly forgets how to mate with KQ vs. K. It'll SEE the mate, report it, and then NOT execute it. Fun