Illegal moves in SEE

735 views
Skip to first unread message

Stephane Nicolet

unread,
Sep 22, 2016, 4:53:39 PM9/22/16
to FishCooking
Try this in current master, just before the return statement at the end of the see() function (line 1056 of position.cpp), then run bench:

  occupied = pieces() ^ from;
  attackers = attackers_to(to, occupied) & occupied;
  stmAttackers = attackers & pieces(~color_of(piece_on(from)));
  nextVictim = type_of(piece_on(from));

  if (   nextVictim == KING 
      && stmAttackers != 0
  //  && swapList[0]    // uncomment to see all illegal captures by king with positive see
      )
  {
     std::cerr << *this << std::endl;
     std::cerr << "see(" << UCI::move( m , false) << ") = " << swapList[0] << std::endl;
  }

This shows all the bench positions with an illegal king move evaluated by SEE: most are illegal quiet moves evaluated as 0 by SEE, but there are some illegal captures by king with a positive SEE score, for instance:

  +---+---+---+---+---+---+---+---+
 | B |   |   |   |   | k |   |   |
 +---+---+---+---+---+---+---+---+
 | p |   | p | p | q | p |   |   |
 +---+---+---+---+---+---+---+---+
 |   | n |   |   |   |   | p |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   | p |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   | P |   | n |   |
 +---+---+---+---+---+---+---+---+
 |   |   | b |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | P | P | P |   |   | P | Q | r |
 +---+---+---+---+---+---+---+---+
 | R |   |   |   |   | R | K |   |
 +---+---+---+---+---+---+---+---+

Fen: B4k2/p1ppqp2/1n4p1/3p4/4P1n1/2b5/PPP2PQr/R4RK1 w - - 0 17
Key: E37BDDCDCEFF47DA
Checkers: 
see(g1h2) = 1285

The SEE sequence for g1h2 goes: "Kg1 takes Rh2, Ng4 takes Kh2, Qg2 takes Nh2", value of g1h2 is 1285.

I suppose this is known behavior that SEE can give a value to illegal moves, but then why does it change the bench (and hence the search) to give them a different value? The fact that my SPRT[-3..1] test fails when I try to fix this, would imply that the current search in SF relies on the SEE algorithm returning buggy values for illegal moves, which is a little bit strange to say the least: http://tests.stockfishchess.org/tests/view/57e40bcb0ebc59763f358ce8

Ronald de Man

unread,
Sep 22, 2016, 7:07:47 PM9/22/16
to FishCooking
On Thursday, September 22, 2016 at 10:53:39 PM UTC+2, Stephane Nicolet wrote:

I suppose this is known behavior that SEE can give a value to illegal moves, but then why does it change the bench (and hence the search) to give them a different value?

If an illegal move gets pruned before it is made, it gets counted in moveCount and ss->moveCount. Since some pruning decisions are based on SEE, a change in SEE will affect moveCount and that will affect the search.

See in particular lines 964-968 in search.cpp where moveCount is decremented (after the move was not pruned) if the move is illegal.

Ronald de Man

unread,
Sep 22, 2016, 7:24:38 PM9/22/16
to FishCooking
So to be "correct" you should not fix SEE, but you should fix the counting of legal moves tried.

That could be done by moving the legality check at the end of step 13 to before step 13, probably slowing down SF a bit.

A better solution seems to be delaying the ++moveCount operation until after the (positive) legality test. As far as I can tell, the incremented moveCount value is only used the calculation of lmrDepth and it would be trivial to replace "moveCount" in that line with "moveCount + 1".

It *might* be that the incremented ss->moveCount somehow plays a role / affects the singular extension search of step 12, but I almost don't think it does (see step 20, there is only a check on (ss-1)->moveCount). If it is important to increment ss->moveCount before doing the singular extension search, it would of course be easy to increment it immediately before and decrement it immediately after the singular extension search (together with setting ss->skipEarlyPruning etc.)

Moving ss->moveCount = ++moveCount to after the legality check seems more correct, but that does not mean it will result in better chess...

Stephane Nicolet

unread,
Sep 24, 2016, 8:16:04 AM9/24/16
to FishCooking
Thanks, Ronald.

Indeed it seems to me that the pruning strategies are a little bit fragile if the search tree
can change when MovePicker emits less illegal moves? And change again if the illegal moves
are emitted in a different order?

Ronald de Man

unread,
Sep 24, 2016, 2:31:03 PM9/24/16
to FishCooking
Yes, pruning strategies are very fragile. But they work pretty well.

I would say it is not worth it to "fix" this problem merely for the sake of "correctness". If "correctness" is the goal, I can give a list of "problems" in Stockfish that would bring you to despair. But making the search completely consistent would, without any doubt, cost 100s of Elo.

However, if this inconsistency can be removed without clear disadvantages, its removal might of course turn out to be an Elo win.

I think you have already tried moving the legality test to the front (and I think it was not successful on fishtest, probably because of the slowdown).

Have you tried moving the ++moveCount to after the legality check?

mcos...@gmail.com

unread,
Sep 25, 2016, 3:05:26 AM9/25/16
to FishCooking


A better solution seems to be delaying the ++moveCount operation until after the (positive) legality test. As far as I can tell, the incremented moveCount value is only used the calculation of lmrDepth and it would be trivial to replace "moveCount" in that line with "moveCount + 1".


This is inconsistent, what it would mean moveCount? You are mixing apple and oranges.

There are only 2 possible consistent meanings that both deserve a renaming:

1) moveCount -> legalMoveCount: In this case you update it after legality check but don't use the +1 in pruning becuase you still don't know if move is legal or not

2) moveCount -> PseudoLegalMoveCount: You do nothing and the renaming is enough.


Note that if you chose to go with the first approach you may want to increase lmr and pruning parameter values, for instance if after 10 moves out of movepicker there are only 7 legal, then you have a difference of 3 when calling

reduction<PvNode>(improving, depth, moveCount) and FutilityMoveCounts[] and the search is sensibly less selective (maybe enough to fail the tests).

mcos...@gmail.com

unread,
Sep 25, 2016, 3:08:51 AM9/25/16
to FishCooking
On Sunday, September 25, 2016 at 9:05:26 AM UTC+2, mcos...@gmail.com wrote:

2) moveCount -> PseudoLegalMoveCount: You do nothing and the renaming is enough.



Sorry the baove is wrong, you should also remove the ss->moveCount = --moveCount; if legality check fails

mcos...@gmail.com

unread,
Sep 25, 2016, 3:28:34 AM9/25/16
to FishCooking

Ralph Stoesser

unread,
Sep 25, 2016, 3:37:32 AM9/25/16
to FishCooking
"I can give a list of "problems" in Stockfish that would bring you to despair."

Please share in a new thread.

Ronald de Man

unread,
Sep 25, 2016, 7:38:33 AM9/25/16
to FishCooking


On Sunday, September 25, 2016 at 9:37:32 AM UTC+2, Ralph Stoesser wrote:
"I can give a list of "problems" in Stockfish that would bring you to despair."

Please share in a new thread.


That would not be so useful, because most of these logical inconsistencies cannot be removed without e.g. removing the hash table.

For example: pruning decisions are partly based on the current state of history tables etc. But if the search takes a TT cutoff, it will do that on the basis of an earlier search which was based on a different state of the history tables. This is not consistent, but fixing it would make no sense.

So my point is just that some inconsistencies or theoretical flaws, and in particular the fragility of pruning decisions mentioned by Stéphane, may just have to be accepted if they turn out not to hurt playing strength and cannot easily be fixed.

Ronald de Man

unread,
Sep 25, 2016, 8:27:55 AM9/25/16
to FishCooking

Indeed. So a next time you might want to leave the apples and oranges aside before disagreeing with someone's analysis.

Judging from your patch, it seems you now also agree that the +1 was (at least logically) necessary, because you shifted the Reduction[] and FutilityMoveCounts arrays by 1.

However, the shift in reduction[] seems to affect LMR in Step 15 too. This might be why your patch failed.

It might also be that SF after all tuning now relies on some pruned moves being illegal but counted in moveCount. Maybe one could collect statistics on this and then perhaps modify the FutilityMoveCounts[] formula a bit and tweak the lmrDepth formula.

(I'm just wondering: is there a strong reason why move pruning is based on lmrDepth and not on a similar but perhaps different formula?)

Ronald de Man

unread,
Sep 25, 2016, 8:59:43 AM9/25/16
to FishCooking
I have submitted a test similar which should not modify LMR:
http://tests.stockfishchess.org/tests/view/57e7c7380ebc59763f358e53

If this fails, it will be interesting to collect statistics and see how to move the pruning curves back to what they are now. It is difficult for me to believe that this particular inconsistency cannot be cured.

zamar

unread,
Sep 25, 2016, 9:24:00 AM9/25/16
to FishCooking

(I'm just wondering: is there a strong reason why move pruning is based on lmrDepth and not on a similar but perhaps different formula?)

I wrote that logic *a long time ago*.

The original idea was that we want to prune moves that are going to fail with high probability. Because the first search that we run is often heavily reduced (using LMR depth), then we want to use this depth as a reference point.

But things are not so black & white, and there is definitely room for experimenting!

Ronald de Man

unread,
Sep 25, 2016, 9:26:59 AM9/25/16
to FishCooking

Ah, the reason why this will probably fail is that now the LEGAL pruned moves are no longer counted in moveCount.

It makes sense not to count ILLEGAL pruned moves in moveCount, but the legal ones probably should be counted. But counting them requires either doing a relatively expensive legality test, which we would like to avoid, or counting them together with the illegal pruned moves.

In any case, there is something strange about the way current master deals with illegal moves:
- if they are pruned, they are included in moveCount and increase LMR reductions for later moves;
- if they are not pruned, they are excluded from moveCount and therefore do not increase LMR reductions for later moves.

If it is not easily possible to fix the "legal move count" then it might be "better" to simply switch to counting pseudo-legal moves. (The question is if this could hurt mate / stalemate detection.)

Ronald de Man

unread,
Sep 25, 2016, 9:53:27 AM9/25/16
to FishCooking

When I posed the question I was incorrectly thinking that "fixing" moveCount only affected the pruning decisions for later moves, so that it could make sense to have a different reductions[] array to calculate lmrDepth (which then should be renamed obviously).

But things are a bit more complicated :-)

SF is now basing reduction depth (and corresponding pruning decisions) on the number of pseudo-legal pruned moves and legal non-pruned moves. This is a bit funny (even though it works very well - or SF is simply very well tuned for this).

Other possibilities:

* number of pseudo-legal moves, pruned and non-pruned.
This is easy and cheap to implement but is still a bit funny. Why should illegal moves returned by next_move() influence the search?

* number of legal moves, pruned and non-pruned.
This makes a lot of sense, but it is probably too expensive.

* number of non-pruned legal moves.
This is easy and cheap to implement and I think the test I am running now does this. But the test will most likely fail (and very quickly it seems, which is good) because it reduces pruning and reductions.

Would it make sense to try to recalibrate pruning and reductions to "number of non-pruned legal moves"?

zamar

unread,
Sep 25, 2016, 11:02:36 AM9/25/16
to FishCooking
Logically it would make a lot of sense.

What works in practice is another story though.

Ronald de Man

unread,
Sep 25, 2016, 11:02:49 AM9/25/16
to FishCooking
On Sunday, September 25, 2016 at 3:53:27 PM UTC+2, Ronald de Man wrote:
* number of pseudo-legal moves, pruned and non-pruned.
This is easy and cheap to implement but is still a bit funny. Why should illegal moves returned by next_move() influence the search?

Even though a bit funny, I've queued a test for this. The first move counted should still be legal to keep (stale)mate testing correct.

Although it makes moveCount a bit more consistent (instead of adding pseudo-legal pruned apples to legal non-pruned oranges as current master does, it counts mostly all pseudo-legal moves, pruned or not), I consider it more a parameter tweak than a "bug fix". So I picked [0,4].

Ralph Stoesser

unread,
Sep 29, 2016, 4:54:49 PM9/29/16
to FishCooking
Is someone still working on this issue?

Ronald de Man

unread,
Sep 29, 2016, 7:21:35 PM9/29/16
to FishCooking
On Thursday, September 29, 2016 at 10:54:49 PM UTC+2, Ralph Stoesser wrote:
Is someone still working on this issue?

It's still in the back of my mind, but at the moment I'm not working on it.

For now these are my thoughts.

Current SF is essentially adding apples to oranges when keeping track of moveCount, which is a bit ugly. BUT it works well. Illegal moves that happen to be generated and pruned increase pruning and reductions of later moves a bit, but the noise that this generates does not seem to cost much Elo if at all. The current approach, although a bit ugly, might be unbeatable.

If I am not mistaken, Stéphane has tested the only "correct" fix that only removes this noise and does not otherwise affect pruning and reductions, namely by doing the legality check before all pruning. This failed, most likely because of the small slow down. (I.e. skipping the legality check for moves that get pruned is a speed up.)

Mainly out of curiosity I have tried making moveCount a bit more consistent by counting essentially all legal and illegal moves. It did not seem to be significantly worse than what SF is doing now, but it was not an improvement.

The best way to get a moveCount that does not mix up legal and illegal moves seems to be by counting only legal non-pruned moves. But that significantly affects pruning and reductions, so it requires a recalibration of pruning and reduction to stand a chance.

It might be interesting to try such a recalibration. The best approach would seem to be first collecting statistics, for each value of k, on the number of pruned moves among the first k moves. Then try to recalculate the futilityMoveCount and reduction arrays such that the effect of not counting the pruned moves is more or less cancelled out.

I have no idea if this might work. The number of pruned moves in a particular position *might* be important information that should be used in determining the reductions for later moves. Or maybe it is the other way around and pruned moves (which have not been searched at all) should best be disregarded when deciding how to treat later moves. Or maybe some mixture is best, e.g. pruned moves could be counted for half (which would reintroduce the couning of illegal moves, but oh well if it works...).

Feel free to try this or other ideas...

Reply all
Reply to author
Forward
0 new messages