Mar 19, 2007

[Plan] Mediocre in WBEC and some planning

The 15th edition of the WBEC (http://wbec-ridderkerk.nl/) starts at the beginning of April and Mediocre is going to play in the 5th (last) division.

I am very much looking forward to it and I hope to have Mediocre v0.25 ready by then.

After getting SEE and LMR working I am now attempting a sorely needed reconstruction of the sort prodecures.

So far I have separated the generatePseudoMoves() method into gen_caps and gen_noncaps. Where the first generates only pseudo legal captures, and the other only pseudo legal non-captures.

Not only does this save some time when generating quiescent moves (ordinary moves does not benefit from this since it has to use both gen_caps and gen_nocaps anyway), but it also makes it possible to generate moves 'as we go along'.

In Mediocre v0.241 I introduced a way to pick the hash move before generating any moves at all, my plan is to elaborate on this. The prodecdure will look something like this:
  1. See if we have a hash move and search it
  2. Generate the captures and search all that are not losing material (checked by SEE) one by one
  3. Get the two killer moves and do a quick verification if they can be played on the board, if they can, search them. We need the verification since the killer moves are based on depth and not position, so a killer move may not be possible to play in some positions
  4. Generate all non captures and search the one by one
  5. And finally only the losing captures are left so search them one by one
The assigning of ordering values and sorting is integrated in each step. So if we get an early cutoff not only do we save the work of generating moves we have no use for, we also save the time of needless assigning of ordering values and sorting.

Also, since gen_caps and gen_noncaps generates pseudo legal moves, we need to verify if the move is legal (not leaving the king in check) before it is searched. This saves time as well since we only have to verify moves we are actually going to use, and not a whole list of moves that might get pruned by the alpha-beta.

Since we have to wedge this part right into the alpha-beta method there are a lot of things to keep track of. And it will probably take some time before it is all finished.

Hopefully I will get it all together before WBEC 15 though.

3 comments:

Anonymous said...

Are you doing fractional depth? That's probably more powerful than all the recent bells and whistles (aside from SEE, perhaps).

For example, if you're at depth d and you're about to search a capture, you search that capture *also* at depth d. So captures "change the depth by 0". Similarly, a check may "change the depth by 1/4 (a quarter). You're already doing this to some extent with your late moves. All the commercial engines use fractional depth.

Perhaps the easiest is to leave the depth parameter as an int, but view it as "centidepth" rather than integer depth. Thus searching into a check would change the depth by 25; searching a (non-losing SEE-verified) capture changes it by 0; searching a regular move changes is by 100; and you may even penalise SEE-losing-captures by having them change the depth by 125, or 150 or something.

A more intelligent form of this "selective search" is obtained by deciding on your depth-change according to contextual features such as whether or not this is a killer move, etc.

Good luck!

Jonatan Pettersson said...

I've been looking at fractional plies for extensions, to make it possible to extend less interesting things with a little bit until many of them results in one ply extra depth.

The way you describe it pretty much all moves get extended or reduced. I can see its merit but I wonder how hard it is to make it all balanced.

After the divided move-generation change I have all the things needed to try it out atleast.

Anonymous said...

LMR != bells and whistles