Oct 13, 2011

[Info] Another breakthrough, maybe

I spent the evening dabbling with root move ordering. I had a general idea of what I wanted to do. Something like:

  1. Break out the first ply from the alphaBeta-method so it's possible to add some unique logic to it (examining a few open source engines it seems fairly common that this is done incorporated in the main search method, which I don't quite understand since it adds both complexity to the code and a bunch of extra if-statements).

    This also allows us to make sure the best move is always obtainable (as I mentioned some posts ago I suspect there were some losses where the best move was overwritten in the hash).

    And finally output the currently examined move to UCI, which is kinda nice.

  2. 2. Add an extensive move ordering algorithm to the root moves. Doesn't matter how expensive since it will be done at most like 30-50 times, compared to to the millions of ordinary nodes.

    Having read quite extensively about it, without actually finding any concrete evidence of the "best" approach I settled for trying a couple alternatives.

    * Do a quiescence search on all moves and order by the values it returned, but bringing the PV move up front if not there already.

    * Count the nodes each move caused and order by that.

    * A combination of the above (quiescence score with some scale for lower plies, and node counts deeper depths)

I tried all kinds of combinations, having a rather unreliable but good enough set of 50 positions to try it on, which with no modifications took slightly over 2 minutes with a fixed depth of 8.

I was hovering around that result for all my attempts. A second over or a second under. It seemed my search was immune to root ordering, or rather the ordering obtained by just calling the alphaBeta-method directly was good enough and my attempts at improving it were futile.

Finally I decided to test something else. Instead of using quiescence search I used a one ply ordinary alpha-beta search, combined with the node counts. Obviously this is not something new, I seem to remember some years ago that this was the way to go, but many have moved on to better things (which didn't work out for me).

So I tried it on the test set again. 30 seconds?! Down from above 2 minutes. First reaction was look for bugs, but couldn't find any.

Have a test going again, we'll see where it lands. Looks promising though.


Thomas Petzke said...

Hi, nice to see you back in the ring. Your old blog inspired me to start my own chess engine project (iCE) and maybe one day our engines will meet in a tournament. (In Oliver Devills Chesswar im still fighting in the current divison G, so mediocre is far ahead in E).


Jonatan Pettersson said...

Hi Thomas, I'm glad to hear that. Always fun to know people are inspired by my blog, that's its main purpose. (especially now that the chessprogramming wiki by far outclasses my little programming guides)