Wednesday, 02 May 2007

Move ordering

If there is one thing in chess programming that cannot be overstressed then it is coffee. Without coffee all is lost... No really, the difference move ordering can have to an engine cannot be overstated. After resolving a few nasty bugs, Vicki now boasts the following move ordering:

  1. The previous PV of iterative deepening is feed back into the search. This is been implemented for a while, but I fixed a bug here which caused the engine to hang. A slight difference is that the entire PV line is used, even if a better line is found the previous line is still investigated first. I was quite amazed by the speedup gained from this.
  2. Quiescence search now uses a Static Exchange Evaluation (SEE), which turned out far easier than I thought and to my surprise, caused a fair amount of speedup. The SEE I use also uses an early exit technique. Say for example, I have a pawn and queen attacking a bishop, while my opponent has two pawns protecting the bishop. The full SEE evaluation will result in a negative value: 3-1+1-9+1=-5 (I gain a bishop and a pawn for a queen and a pawn). With early exit I only realize that I can stop after capturing the knight, resulting in +2. A great move!
Vicki is playing a good game of chess already and I find it difficult to beat the engine with tight time controls (3 mins/less), but still beat the engine 80% of the time if I allow myself ample wetware processing time! ;)

I am now concentrating my efforts on the ordering of normals moves as part of alpha-beta (in conjunction with the PV-value). So far the results are very promising, but it still needs some work before being released.

5 comments:

Jonatan Pettersson said...

Vicki does not seem to report how many nodes it has searched (or nodes per second).

When starting to work on move ordering the number of nodes searched at a certain depth should drop and it is easy to spot the difference.

Remember to include nodes visited in quiescent search as well. (I didn't for a long time :)

Anonymous said...

Isn't this early exit in SEE the same thing as MVV/LVA?

Jaco van Niekerk said...

Hi Jonatan / Anonymous.

I've added the number nodes searched and it did not take 1 minute to do :) It is great to see even the tiniest bit of ordering significantly reduces this number!

My early exit in SEE is not the same as MVV/LVA. For example, assume I attack a knight with my rook and queen which is protected by the opponent's queen. SEE with early exit will not early exit here, after capturing with the rook, since recapturing with his queen will result in a loss. That is, 3-5+9=7 (knight – rook + queen). Good for me!

In the case where a pawn and queen attacks a rook, "protected" by two pawns, normal SEE (as I understand it) will report 5-1+1-9=-4 (rook – pawn + pawn – queen) which is regarded as "bad". SEE with early exit realises that capturing with the Queen will be a bad mistake, but that the rook capture is still good, resulting in 5-1=4.

Not only does this result in better move ordering for me, but the SEE function also gain a slight speedup. I don’t know if this has been tried before (I’ll be amazed if not!), but it definitely works for Vicki!

Anonymous said...

OK I see! :-) However, a standard SEE is not so dumb... here's how it works in the QP/RPP case. All captures are tried in order giving:

ME +5 (rook cap, cur target value = +1, pawn)
YOU -4 (pawn cap, cur target value = +1, pawn)
ME +5 (pawn cap, cur target value = +9, queen)
YOU +4 (queen cap, cur target value = +1, pawn)

But now there is a minimax phase where this capture stack is "rewinded" to see where the "real" capture sequence begins. First is +4 vs. +5: this is an advantageos capture so its value is propagated by the interested party (and negated). We have now:

ME +5 (rook cap, cur target value = +1, pawn)
YOU -4 (pawn cap, cur target value = +1, pawn)
ME -4 (value of YOU +4 is negated and overrides +5)

Now however ME sees the capture is not good, thus interrupts this "chain" and simply discards the entry.

ME +5 (rook cap, cur target value = +1, pawn)
YOU -4 (pawn cap, cur target value = +1, pawn)

YOU is still interested in capturing, since it gains a pawn at least, so again the value is negated and propagated:

ME +4

This is the last entry so the net SEE value is +4 (pawn cap rook, pawn cap pawn).

Jaco van Niekerk said...

anonymous

Who are you? ;-) Thank you for the help. While reading your post, I realized that my version of SEE will actually give a wrong value for the opponent (always assuming the opponent is "dumb" by capturing). It seems I'm back at the drawing board for SEE.

However, I'll postpone this part for now and focus my attention on normal move ordering as my version of SEE already cuts the nodes down by about 60% (I already incorporated SEE within the alpha-beta as well).

I will keep you all posted. Thank you so much!