micro-Max 4.8 has a slow move legality check?

[lealgo]

Hi:

I'm using micro-Max 4.8 as a move legality checker and I noticed it is getting really slow in *some* places. A quick way of reproducing the issue is by making many pawn moves in the opening. Here I link the source of micro-Max 4.8 code with just the main function rewritten to trigger the issue.

https://gist.github.com/lealgo/1cd58860 ... 41b7f1c268

The effect is much worse with small hash table sizes. Any ideas?

Regards,
Leandro

[Kotlov]

MicroMax is 2048 bytes engine. What do you want him for?

[lealgo]

I'm using it on Arduino. But the issue has nothing to do with the hardware constraints as it's present on AMD64 also.

[Sven]

I'm using micro-Max 4.8 as a move legality checker and I noticed it is getting really slow in *some* places. A quick way of reproducing the issue is by making many pawn moves in the opening. Here I link the source of micro-Max 4.8 code with just the main function rewritten to trigger the issue.
[...]
The effect is much worse with small hash table sizes. Any ideas?

What is "the effect" for you, which unusual behaviour do you observe? You say you are using uMax as a move legality checker but what you do in your main() function is that you call the recursive minimax function D() with a search depth of 3 for each move of your "test game" and that appears to be a bit more than just legality checking for me.

[Sven]

I'm using micro-Max 4.8 as a move legality checker and I noticed it is getting really slow in *some* places. A quick way of reproducing the issue is by making many pawn moves in the opening. Here I link the source of micro-Max 4.8 code with just the main function rewritten to trigger the issue.
[...]
The effect is much worse with small hash table sizes. Any ideas?

What is "the effect" for you, which unusual behaviour do you observe? You say you are using uMax as a move legality checker but what you do in your main() function is that you call the recursive minimax function D() with a search depth of 3 for each move of your "test game" and that appears to be a bit more than just legality checking for me.

I can imagine that D(), before returning, makes the *best* move on the board that it finds during search. That would mean that the game you are actually playing on the board is very different from your expectation. Just setting K and L ("from" and "to") seems not sufficient to make that move on the board.

To receive more information you should initialize Ticks to GetTickCount() and Post to 1.

[hgm]

Micro-Max does a 1-ply search plus QS for legality checking, which is aborted through an 'exit on the first floor' after the input move has been searched (but not unmade) and scored better than -INF (showing that QS was not able to capture the King). This is indeed slower than necessary, because the input move in general will not be the first move it searches, and all moves it tries before are also tested for legality. And doing a complete QS is not the most efficient way to determine if you can capture the King either.

[Sven]

Micro-Max does a 1-ply search plus QS for legality checking, which is aborted through an 'exit on the first floor' after the input move has been searched (but not unmade) and scored better than -INF (showing that QS was not able to capture the King). This is indeed slower than necessary, because the input move in general will not be the first move it searches, and all moves it tries before are also tested for legality. And doing a complete QS is not the most efficient way to determine if you can capture the King either.

I can confirm the observation of the OP that *with his posted version*, the last few moves in his test game take several seconds per move that is checked for legality. After adding code to print the board and setting Post=1 it looks like this (node counter N is *not* reset after each move):

Code: Select all

 r n b q k b n r
 + + + + + + + +
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 * * * * * * * *
 R N B Q K B N R
K=96 L=80
-1     -1        0        136 a2a3
 0      0        0        137 a2a3
a2a3: 0
 r n b q k b n r
 + + + + + + + +
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 * . . . . . . .
 . * * * * * * *
 R N B Q K B N R
K=16 L=32
-1     -2        0        154 c7c6
 0      0        0        155 c7c6
a7a6: 0
 r n b q k b n r
 . + + + + + + +
 + . . . . . . .
 . . . . . . . .
 . . . . . . . .
 * . . . . . . .
 . * * * * * * *
 R N B Q K B N R
K=97 L=81
-1     -1        0        198 d2d3
 0      0        0        199 d2d3
b2b3: 0
 r n b q k b n r
 . + + + + + + +
 + . . . . . . .
 . . . . . . . .
 . . . . . . . .
 * * . . . . . .
 . . * * * * * *
 R N B Q K B N R
K=17 L=33
-1     -2        0        236 d7d6
 0      0        0        237 d7d6
b7b6: 0
 r n b q k b n r
 . . + + + + + +
 + + . . . . . .
 . . . . . . . .
 . . . . . . . .
 * * . . . . . .
 . . * * * * * *
 R N B Q K B N R
K=98 L=82
-1     -1        0        278 e2e3
 0      0        0        279 e2e3
c2c3: 0
 r n b q k b n r
 . . + + + + + +
 + + . . . . . .
 . . . . . . . .
 . . . . . . . .
 * * * . . . . .
 . . . * * * * *
 R N B Q K B N R
K=18 L=34
-1     -2        0        316 e7e6
 0      0        0        317 e7e6
c7c6: 0
 r n b q k b n r
 . . . + + + + +
 + + + . . . . .
 . . . . . . . .
 . . . . . . . .
 * * * . . . . .
 . . . * * * * *
 R N B Q K B N R
K=99 L=83
-1     -1        0        358 f2f3
 0      0        0        359 f2f3
d2d3: 0
 r n b q k b n r
 . . . + + + + +
 + + + . . . . .
 . . . . . . . .
 . . . . . . . .
 * * * * . . . .
 . . . . * * * *
 R N B Q K B N R
K=19 L=35
-1     -2        0        394 f7f6
 0      0        0        395 f7f6
d7d6: 0
 r n b q k b n r
 . . . . + + + +
 + + + + . . . .
 . . . . . . . .
 . . . . . . . .
 * * * * . . . .
 . . . . * * * *
 R N B Q K B N R
K=100 L=84
-1     -1        0        444 a3a4
 0      0        0        445 a3a4
e2e3: 0
 r n b q k b n r
 . . . . + + + +
 + + + + . . . .
 . . . . . . . .
 . . . . . . . .
 * * * * * . . .
 . . . . . * * *
 R N B Q K B N R
K=20 L=36
-1     -2        0        464 e7e6
 0      0        0        465 e7e6
e7e6: 0
 r n b q k b n r
 . . . . . + + +
 + + + + + . . .
 . . . . . . . .
 . . . . . . . .
 * * * * * . . .
 . . . . . * * *
 R N B Q K B N R
K=101 L=85
-1     -1        0        476 a3a4
 0      0        0        477 a3a4
f2f3: 0
 r n b q k b n r
 . . . . . + + +
 + + + + + . . .
 . . . . . . . .
 . . . . . . . .
 * * * * * * . .
 . . . . . . * *
 R N B Q K B N R
K=21 L=37
-1     -2        0        498 f7f6
 0      0        0        499 f7f6
f7f6: 0
 r n b q k b n r
 . . . . . . + +
 + + + + + + . .
 . . . . . . . .
 . . . . . . . .
 * * * * * * . .
 . . . . . . * *
 R N B Q K B N R
K=102 L=86
-1     -1        0        510 a3a4
 0      0        0        511 a3a4
g2g3: 0
 r n b q k b n r
 . . . . . . + +
 + + + + + + . .
 . . . . . . . .
 . . . . . . . .
 * * * * * * * .
 . . . . . . . *
 R N B Q K B N R
K=22 L=38
-1     -2        0        536 g7g6
 0      0        0        537 g7g6
g7g6: 0
 r n b q k b n r
 . . . . . . . +
 + + + + + + + .
 . . . . . . . .
 . . . . . . . .
 * * * * * * * .
 . . . . . . . *
 R N B Q K B N R
K=103 L=87
-1     -1        0        548 a3a4
 0      0        0        549 a3a4
h2h3: 0
 r n b q k b n r
 . . . . . . . +
 + + + + + + + .
 . . . . . . . .
 . . . . . . . .
 * * * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=23 L=39
-1     -2        0        576 h7h6
 0      0        0        577 h7h6
h7h6: 0
 r n b q k b n r
 . . . . . . . .
 + + + + + + + +
 . . . . . . . .
 . . . . . . . .
 * * * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=80 L=64
-1     -1        0        588 a3a4
 0      0        0        589 a3a4
a3a4: 0
 r n b q k b n r
 . . . . . . . .
 + + + + + + + +
 . . . . . . . .
 * . . . . . . .
 . * * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=32 L=48
-1     -2        0        600 a6a5
 0      0        0        601 a6a5
a6a5: 0
 r n b q k b n r
 . . . . . . . .
 . + + + + + + +
 + . . . . . . .
 * . . . . . . .
 . * * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=81 L=65
-1     -1        0        622 b3b4
 0      0        0        623 b3b4
b3b4: 0
 r n b q k b n r
 . . . . . . . .
 . + + + + + + +
 + . . . . . . .
 * * . . . . . .
 . . * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=33 L=49
-1     72        0        640 a5b4
 0      0        0        641 a5b4
b6b5: 0
 r n b q k b n r
 . . . . . . . .
 . . + + + + + +
 + + . . . . . .
 * * . . . . . .
 . . * * * * * *
 . . . . . . . .
 R N B Q K B N R
K=82 L=66
-1     73        0        992 a4b5
 0      0        0        993 a4b5
c3c4: 0
 r n b q k b n r
 . . . . . . . .
 . . + + + + + +
 + + . . . . . .
 * * * . . . . .
 . . . * * * * *
 . . . . . . . .
 R N B Q K B N R
K=34 L=50
-1     72        0       1014 a5b4
 0      0        0       1087 a5b4
c6c5: 0
 r n b q k b n r
 . . . . . . . .
 . . . + + + + +
 + + + . . . . .
 * * * . . . . .
 . . . * * * * *
 . . . . . . . .
 R N B Q K B N R
K=83 L=67
-1     73        0       2212 b4c5
 0      0        0       2213 b4c5
d3d4: 0
 r n b q k b n r
 . . . . . . . .
 . . . + + + + +
 + + + . . . . .
 * * * * . . . .
 . . . . * * * *
 . . . . . . . .
 R N B Q K B N R
K=35 L=51
-1     72        0       2412 a5b4
 0      0        0       2413 a5b4
d6d5: 15
 r n b q k b n r
 . . . . . . . .
 . . . . + + + +
 + + + + . . . .
 * * * * . . . .
 . . . . * * * *
 . . . . . . . .
 R N B Q K B N R
K=84 L=68
-1     73        1      10711 c4d5
 0      0        1      10810 c4d5
e3e4: 16
 r n b q k b n r
 . . . . . . . .
 . . . . + + + +
 + + + + . . . .
 * * * * * . . .
 . . . . . * * *
 . . . . . . . .
 R N B Q K B N R
K=36 L=52
-1     72        3      14570 c5b4
 0      0        3      14673 c5b4
e6e5: 93
 r n b q k b n r
 . . . . . . . .
 . . . . . + + +
 + + + + + . . .
 * * * * * . . .
 . . . . . * * *
 . . . . . . . .
 R N B Q K B N R
K=85 L=69
-1     73       12      87194 c4d5
 0      0       12      90282 c4d5
f3f4: 0
 r n b q k b n r
 . . . . . . . .
 . . . . . + + +
 + + + + + . . .
 * * * * * * . .
 . . . . . . * *
 . . . . . . . .
 R N B Q K B N R
K=37 L=53
-1     72       12      96835 c5b4
 0      0       14     104077 c5b4
f6f5: 250
 r n b q k b n r
 . . . . . . . .
 . . . . . . + +
 + + + + + + . .
 * * * * * * . .
 . . . . . . * *
 . . . . . . . .
 R N B Q K B N R
K=86 L=70
-1     73       37     303036 c4d5
 0      0       37     309291 c4d5
g3g4: 47
 r n b q k b n r
 . . . . . . . .
 . . . . . . + +
 + + + + + + . .
 * * * * * * * .
 . . . . . . . *
 . . . . . . . .
 R N B Q K B N R
K=38 L=54
-1     72       42     356008 c5b4
 0      0       45     378736 c5b4
g6g5: 905
 r n b q k b n r
 . . . . . . . .
 . . . . . . . +
 + + + + + + + .
 * * * * * * * .
 . . . . . . . *
 . . . . . . . .
 R N B Q K B N R
K=87 L=71
-1     73      132    1158600 c4d5
 0      0      135    1186334 c4d5
h3h4: 187
 r n b q k b n r
 . . . . . . . .
 . . . . . . . +
 + + + + + + + .
 * * * * * * * *
 . . . . . . . .
 . . . . . . . .
 R N B Q K B N R
K=39 L=55
-1     72      151    1326337 c5b4
 0      0      159    1400965 c5b4
h6h5: 2808
 r n b q k b n r
 . . . . . . . .
 . . . . . . . .
 + + + + + + + +
 * * * * * * * *
 . . . . . . . .
 . . . . . . . .
 R N B Q K B N R

[lealgo]

For calling D() I took the values of z and n from the original xboard code belonging to the user move. Because that's what I'm doing, telling micro-Max to execute a user move, albeit from both sides an on. I tried your suggested values of 9 and 2 and they give invalid moves.

[Sven]

For calling D() I took the values of z and n from the original xboard code belonging to the user move. Because that's what I'm doing, telling micro-Max to execute a user move, albeit from both sides an on. I tried your suggested values of 9 and 2 and they give invalid moves.

You are right, initially I did not realize that there are big differences between the code inside HGM's documentation on his website and the code of the most recent MicroMax version you used.

So the problem must be somewhere else.

[lealgo]

So it's not a bug, it's a feature!

All right, as I dare not to modify D() myself I guess I'll keep using the weaker umax 1.6 that doesn't have this issue. OR, drop the legality checking for two players and use 4.8 just for playing against the micro-controller.

Thank you and best regards,
Leandro