movei hash report

[Uri Blass]

Movei still does not report mate scores correctly.

I was surprised to find that inspite of that problem movei never translated a mate position to draw by the 50 move rule or to repetition in 100 games that I played.

I tried to implement principle variation search and internal iterative deepening but for some reason they seem not work for me(I did not try in games and gave up when I did not get a significant positive change in results of test suites).

Uri

[Michael Sherwin]

Movei still does not report mate scores correctly.

I was surprised to find that inspite of that problem movei never translated a mate position to draw by the 50 move rule or to repetition in 100 games that I played.

I tried to implement principle variation search and internal iterative deepening but for some reason they seem not work for me(I did not try in games and gave up when I did not get a significant positive change in results of test suites).

Uri

PVS and IID do not work for RomiChess either.

Personally, I think that both ideas are 'break even' at best.

Can IID be anything on average other than a waste of time if there is a simple winning capture available?

Simple alpha-beta, if the move ordering is really good, seeks a null window very efficiently with out makeing them artificially and then having to do researches.

The only question for me is if they work together, synergisticaly much better than they work seperately. Have you tried adding them both at the same time?

[Uri Blass]

Movei still does not report mate scores correctly.

I was surprised to find that inspite of that problem movei never translated a mate position to draw by the 50 move rule or to repetition in 100 games that I played.

I tried to implement principle variation search and internal iterative deepening but for some reason they seem not work for me(I did not try in games and gave up when I did not get a significant positive change in results of test suites).

Uri

PVS and IID do not work for RomiChess either.

Personally, I think that both ideas are 'break even' at best.

Can IID be anything on average other than a waste of time if there is a simple winning capture available?

Simple alpha-beta, if the move ordering is really good, seeks a null window very efficiently with out makeing them artificially and then having to do researches.

The only question for me is if they work together, synergisticaly much better than they work seperately. Have you tried adding them both at the same time?

Yes

I tried them also together and no significant change in test suites so I simply even did not try in games.

Uri

[PK]

PVS and IID do not work for RomiChess either.

recently I have tried disabling PVS search in the last n plies of the search, where it can be less helpful. it seems to work, but there are some wild fluctuations. n=4 is better than both n=3 AND n=5 for the 8-9 ply search - which means only that it doesn't create terrible slowdowns in certain positions. the net gain is about 5% when using PVS together with aspiration window, which some people told me not to do.

[Dann Corbit]

IID gives a marvelous benefit if you have no move ordering whatsoever.
IID gives a modest benefit if your move ordering is poor.
IID gives no benefit if you already have excellent move ordering.

PVS should always be a benefit, if your pv node fail high percent is above 90 on average. If you have good move ordering, then it should be above 90%.

If you do not get a clear benefit from PVS, then you have a bug in your PVS implementation or your move ordering is sub-optimal. Logically, a zero window search has to be faster than a normal window search and -- if you almost never have to re-search (IOW: a good fail high percentage on the pv nodes) then it should be a clear win.

[ed]

I am surprised IID doesn't work for 2 chess programmers, I remember it gave me an average of 15% speed-up while my search efficiency was already far above 90%.

I don't iterate, but do a one time reduced search and then search again at full depth. Its pseudo code:

Code: Select all

if (no best_move_from_hash_table_present)  
 do { depth=depth-table[remaining_depth]; }

char table []= {  0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,  17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,  25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32 };

Which code basically means that the current depth is lowered with the remaining depth / 2.

I have tried to iterate, no improvement to the above simple formula.

I have tried to skip IID when there is an obvious winning capture, still the above formula remained superior.

I remember the 15% speed gain was heavily fragmented, in most positions the improvement was between 2-5-7% but some positions were peaking at 20% up to 40%.

The latter happened in positions with a steady best move that suddenly dropped in score and then the search is faced with many positions near the root that have no best_move_from_the_hash_table. Here IID works best.

Ed

[Roman Hartmann]

IID gives a marvelous benefit if you have no move ordering whatsoever.
IID gives a modest benefit if your move ordering is poor.
IID gives no benefit if you already have excellent move ordering.

PVS should always be a benefit, if your pv node fail high percent is above 90 on average. If you have good move ordering, then it should be above 90%.

If you do not get a clear benefit from PVS, then you have a bug in your PVS implementation or your move ordering is sub-optimal. Logically, a zero window search has to be faster than a normal window search and -- if you almost never have to re-search (IOW: a good fail high percentage on the pv nodes) then it should be a clear win.

I tried PVS last year and it didn't help. I assumed that bad move ordering must be the reason. I improved the move ordering since then a bit.

Anyway, just recently I tried PVS again and there is a rather big difference. I didn't invest too much time to figure out how much better PVS works for me than pure AB but it's at least 5-10%.

Regarding IID I made the same experience and although it doesn't seem to help my engine (in testsuites) I still do use it as I think it might help in actual play to avoid some blunders but that's only a guess and I didn't do much testing to confirm that.

I also tried aspiration AB in combination with PVS but that didn't work for me.

Roman

[Uri Blass]

IID gives a marvelous benefit if you have no move ordering whatsoever.
IID gives a modest benefit if your move ordering is poor.
IID gives no benefit if you already have excellent move ordering.

PVS should always be a benefit, if your pv node fail high percent is above 90 on average. If you have good move ordering, then it should be above 90%.

If you do not get a clear benefit from PVS, then you have a bug in your PVS implementation or your move ordering is sub-optimal. Logically, a zero window search has to be faster than a normal window search and -- if you almost never have to re-search (IOW: a good fail high percentage on the pv nodes) then it should be a clear win.

I tried PVS last year and it didn't help. I assumed that bad move ordering must be the reason. I improved the move ordering since then a bit.

Anyway, just recently I tried PVS again and there is a rather big difference. I didn't invest too much time to figure out how much better PVS works for me than pure AB but it's at least 5-10%.

Regarding IID I made the same experience and although it doesn't seem to help my engine (in testsuites) I still do use it as I think it might help in actual play to avoid some blunders but that's only a guess and I didn't do much testing to confirm that.

I also tried aspiration AB in combination with PVS but that didn't work for me.

Roman

my move ordering certainly can be improved but I think that the same is for all engines.

Note that I use a lot of other original secret tricks
and it is possible that changing what I do does not work well with other tricks(it is also possible that I have bugs in what I did).

Note that I cannot change and say easily that something is 5-10% faster based on some positions because often I am not going to get the same score's and pv's when I change my search because of factors like late move reductions that are not the same with different trees.

Uri

[Stan Arts]

After the Wcrcc tournament I finally got myself to sit down and totally rewrite my engine's search. (that's the closest I'll get to a total rewrite, for which I do not have the motivation) In the process I'm also doing some experiments with IID again, things like that are much easier to implement for me now.

What I'm seeing is little to no gain in some positions (for example when the move to play is clear and the engine doesn't change it's mind about the main move) , but an impressive gain in positions where there are fail low's and high's and changing it's mind about the main move to play. Here I'm seeing impressive drops in nodes.

These type of positions occur often enough in games for me to keep the code in.

Imho even when there's an easy capture, you give the next depths below the capture the chance to come up with good moves (storing them in the hashtable, etc.) and then researching even the easy capture with full depth can be refuted even faster in some cases.

Stan

[hgm]

I completely agree. IID is like an insurance. Most of the time it was not needed, but then it also costs very little. And now and then it saves you big time.

Of course the lousier your basic move ordering, the more you benifit. But then it can be really spectacular, to the point where a program like micro-Max (which does have no move ordering at all, not even a move list, and can only search moves as it generates them) is able to compete with 'serious' engines. IID really works miracles there.

One thing still on my to-do list is to investigate if even more drastic IID would not even be better. I am thinking of situations where a previously best move in a PV node experiences a dramatic drop in score (or even any decrease in score) at high search depth. If that move has been best move for many ID or IID iterations, you will know next to nothing about the other moves. They have always been scoring below alpha, all their hashed scores are upper bounds, and in many cases the upper bounds are no longer usable. (With hard fail they would never be usable!) Disastously poor moves might very well have the highest upper bounds. To prevent wasting lots of time on such a disastrous move at high search depth, it would make sense to start searching for moves that might beat the new alpha at small depth first, resetting the IID depth back to 1 in PV nodes each time the value of alpha after search of the previous best move drops compared to the previous iteration.