Tuesday, July 03, 2007

Clash of the dilettantes -- game and quiescence search

Later in this post: a new game by my chess computer, against another chess computer. But first some boring techno-talk.

I've finally implemented what is called a quiescence search. It's a basic search algorithm that improves any chess computer greatly. I tried to implement it weeks ago, but there was a bug I couldn't find and I gave up knowing I would return to the task. Now I did, with success this time.

So, what's a quiescence search? A chess computer suffers from the horizon effect. It doesn't see beyond the assigned number of plies. So if it stops searching in the middle of a tactical sequence the evaluation of the position becomes very wrong. For example, white may just have taken a knight with its queen. Great, a knight up! Easy win! But, what the search algorithm didn't see is that black the next move can take the queen with a pawn. The computer didn't search deep enough to notice. But, that's with the ordinary search algorithm. Quiescence search to the rescue! Q-search is basically a search algorithm that searches only captures, so at the end of the ordinary search the q-search takes over and searches all the captures (as deep as needed), and evaluates the position as soon as no captures are left (technically it actually evaluates the position during the search too, for reasons I won't go into). No more searches that run out of depth in the middle of a tactical sequence.

Having a q-search makes the chess computer much more difficult to out-tactic (and it makes it more likely to out-tactic you!). And it is noticeable. My program was finally able to draw (with the better position) against its old nemesis The Thinking Machine. The Thinking Machine is basically a dilettante chess computer, but my chess computer isn't ready to take on Rybka just yet so I have go for easier competition for now.

The Game:



My chess computer (got to give it a name soon) is only thinking 3 ordinary plies deep (the q-search can be really time consuming) and was analyzing 34090 positions/s in average, and was thinking 3.11s per move average. It does play some funny moves, but not as funny or frequent as in earlier games. (It actually plays better now, with q-search, going only 1 ordinary ply deep, than it did before going 5 ordinary plies deep).

(And BTW, I was wrong in my post on null move pruning. It was wrongly implemented, and the branching factor and plies didn't get that boost. I'm not sure whether it improved anything at all, but it will when I get it right... but it's not a priority right now.)

3 comments:

Temposchlucker said...

I don't know what you want to accomplish with your chessengine, but if you search for an extra goal, here might be one or two:
There is a big hiatus in the chess world. The chess game isn't "sexy" enough for the average spectator. So it is difficult to get a lot of spectators and hence it is difficult to get sponsors. The difficulty is that you can only enjoy the game when you are a good chessplayer. Which is very unlike soccer, or the funny games they use to play in the US, where the spectators who have never touched a ball still can enjoy the game.

The FIDE tried to fill this hiatus by making the game SHORTER. Which doesn't make sense because it only makes it MORE difficult for the spectator to see what is going on in the position and not easier.

In a way commentary by a grandmaster can fill that gap. But isn't it more logical to use a computerprogram for that nowadays? Showing you graphically wich squares are under attack, which combinations threaten?

Besides that there is an analysis- tool needed for research. A lot of the parameters that are used by evaluating a position with a chess engine are interesting for the analist too. How does the kingsafety evolve? How does the piece activity develop during the game? In order to discover new trends.

A commercial engine doesn't let you peek into the kitchen.

Blue Devil Knight said...

I really appreciate you updating us on these algorithms. They are very interesting.

XY said...

Temposchlucker,

I don't have any well defined goals, but I have some (rather non-specific) ideas. Mostly I will just keep developing the program and see where it ends up.

It's already more than a just a chess engine, since it has its own interface. And the idea is to make it a useful chess tool rather than a strong chess computer (though I will make it as strong as I can, within the limits of time). I intend it to be highly configurable, and intuitive to use.

BDK,

OK good to know. The q-search sometimes takes the search as deep as 30 half-moves. That's pretty fascinating. Almost every game has its share of searches going 20-25 half-moves deep. (Obviously the branching factor is very low when it goes this deep.)

 
Locations of visitors to this page