micro-Max 4.8 has a slow move legality check?

[lealgo]

I forgot to list the timings here as they are very extreme even on AMD64, up to 4 minutes for the last move...

• With default hashsize: (time in ms)
  hash: 8388607
  a2a3: 0
  a7a6: 0
  b2b3: 0
  b7b6: 0
  c2c3: 0
  c7c6: 0
  d2d3: 0
  d7d6: 0
  e2e3: 0
  e7e6: 0
  f2f3: 1
  f7f6: 0
  g2g3: 0
  g7g6: 0
  h2h3: 0
  h7h6: 0
  a3a4: 0
  a6a5: 0
  b3b4: 0
  b6b5: 0
  c3c4: 0
  c6c5: 1
  d3d4: 0
  d6d5: 9
  e3e4: 4
  e6e5: 75
  f3f4: 9
  f6f5: 211
  g3g4: 55
  g6g5: 816
  h3h4: 170
  h6h5: 2673
  
  With hashsize = 1:
  hash: 1
  a2a3: 0
  a7a6: 0
  b2b3: 0
  b7b6: 0
  c2c3: 0
  c7c6: 0
  d2d3: 0
  d7d6: 0
  e2e3: 0
  e7e6: 1
  f2f3: 0
  f7f6: 0
  g2g3: 0
  g7g6: 0
  h2h3: 0
  h7h6: 0
  a3a4: 0
  a6a5: 0
  b3b4: 0
  b6b5: 1
  c3c4: 2
  c6c5: 8
  d3d4: 2
  d6d5: 75
  e3e4: 161
  e6e5: 2114
  f3f4: 266
  f6f5: 5299
  g3g4: 10025
  g6g5: 85274
  h3h4: 25451
  h6h5: 249194

[hgm]

Because micro-Max uses a normal search for the legality test, this includes QS. And the position with all Pawns on 4th/5th rank gives an enormous search explosion in QS. Especially with a small hash table, as the Pawn captures can be executed in a zillion different orders, and you cannot benefit from transpositions.

Such positions are not really representative, and if micro-Max would be actually playing its own preferred moves it would never get into such positions.

[Ras]

OR, drop the legality checking for two players and use 4.8 just for playing against the micro-controller.

How much flash-ROM do you have left over? Maybe you could just add a dedicated legality checker without engine behind it?

[hgm]

If you want a more efficient legality checker, you can disable QS during execution of a given move. For this you would have to replace the line

Code: Select all

 W&#40;d++<n||d<3||                                /* iterative deepening loop */

(W = while), which controls the number of IID iterations in every node, by

Code: Select all

 W&#40;d++<n||d<2+!&#40;K-I&#41;||                         /* iterative deepening loop */

The d<3 condition would normally force a d=1 and d=2 iteration in every node, where the d=1 identifies the MVV/LVA-wise best move, and d=2 is a captures-only search (i.e. QS). During a normal search K = I (I = INFINITE), so !(K-I) would be 1, and nothing changes. But when a the from-square of a move is fed to K for execution, !(K-I) would be 0, and the d=2 QS iteration would not be forced. The d=1 iteration will detect any King capture, and abort the node with a +I score in that case, so legality checking would not suffer.

Of course you could also just replace the 3 in d<3 by a new global variable that you would set to 3 during a normal search, but to 2 during legality checking. I guess that would be more efficient, as you would not have to calculate 2+!(K-I) on the fly in every QS node.

[lealgo]

It works like a charm.

I tested with your proposed line change and the timings went all down to 0 or 1ms, even with tiny hash. I didn't like the global var idea so I didn't try it. Now I'm running a little match vs original but everything seems normal, I don't see any impact in NPS, depth or something else. It seems that computing 2+!(K-I) is no big deal, it should not be more expensive than carrying out further iterations. Who knows, maybe it gained a liiittle bit ELO

Thank you very much
and best regards,
Leandro

[lealgo]

OR, drop the legality checking for two players and use 4.8 just for playing against the micro-controller.

How much flash-ROM do you have left over? Maybe you could just add a dedicated legality checker without engine behind it?

Oh plenty!

Device: atmega32u4
Program: 21558 bytes (65.8% Full)
Data: 916 bytes (35.8% Full)



Yeah definitely I could, but it would limit the stack that's critical for D()