Tuesday, 08 May 2007

Re-engineering...

OK, I realised that this early exit strategy (in SEE) of mine is actually pretty dumb. I replaced it with a very elementary minimax search to evaluate the entire capture sequence for both sides. The results were rather good. I search on average a ply deeper with only SEE in quiescence search (no ordering in the alpha-beta). By adding the improved move ordering in alpha-beta as well I get another ply deeper with longer time controls.

Although Vicki is no push-over any more, a significant amount of work still lies ahead. In order of implementation this is:
  1. A long, hard look at the evaluation function of end-games. Vicki struggles with KQ vs. K (never mind KR vs. K).
  2. Move ordering within alpha-beta can still be improved.
  3. Killer-moves, history heuristics and null moves (I may implement transposition tables before null moves though).
  4. Transposition tables.
  5. Hash tables (evaluation, pawns, etc.).
  6. Opening books (adaptive?) and perhaps even end-game databases.
  7. Pondering.
  8. Learning.
  9. Factor X.
Factor X is basically that element in Vicki that makes it unique. I don't think I'll be happy with "just-another-chess-engine.". What is factor X? I don't have any idea...(yet!)

Version 0.031alpha an now be downloaded at Vicki's home.

5 comments:

Jonatan Pettersson said...

I thought I needed special treatment for KQvK and KRvK as well, but I put it off and when I was going to implement it it wasn't needed anymore. :)

The reason was a deeper search depth combined with my piece tables including bonus for king in the center in end games.

So basically Mediocre understands that pushing the king to the edges is a good thing, and the searchdepth in such endings is very deep so it handled itself.

KBNvK and KBBvK might still need special treatment though, but I haven't even looked at that yet since it happens so rarely.

Sparky said...

At this point my evaluation focusses on opening\middle game and not on the endgane.

It's good to get confimation from you on this as I were of the opinion that better evaluation (for endgame, specifically) will negate the need for any special treatment.

I need to look into this as well.

Anonymous said...

2. 3. 4.
1. happens because of bugs.
...the rest is not that important at this stage.

Sparky said...

I don't agree though. My evaluation function works well in openings/middle-games, where mobility of pieces is important and moving the king should be avoided (king moves are sorted just before losing captures).

In the end-game where the king should be activated the current evaluation function does not work well. It is not because of bugs, but because of poor endgame knowledge.

Anonymous said...

I was mostly referring to the KQK and KRK endgames. In this situation:

7Q/8/8/3k4/8/8/8/K7 w - - 0 1

white will mate very quickly. Basically any move will either bring the queen or the king closer to the center, any piece/square table will give that. After a couple of moves, the mate should be in sight so the endgame is "automatically" won. If this does not happen, there might be a bug somewhere. You can setup other position but the idea is the same: king and queen try to gain some advantage by moving to the center, and soon this brings the mate within the horizon. May take some extra moves for the rook but not too much!