Monday, July 09, 2007

Babylon Vs Fritz, SEE now implemented, threefold repetition, more on q search

Some results: Babylon easily beats Fritz set to a rating of 1350 (lowest possible). It became a threefold repetition at rating 1500 (with big advantage for Babylon), and another threefold repetition when Fritz was set to 1596 (with equal position, endgame). I claimed some time ago that one goal was to beat Fritz set to 1350, so that is now achieved. Of course, I don't know what this rating means in relation to other scales (other than that it's much inflated compared to elo), but it ranges from 1350 to 2150. (It's btw an old free version of Fritz, and the personality used was Reckless.)

I will soon have to something about those threefold repetitions. It's a well known problem with chess computers and something all engines need to deal with one way or the other. Most implement hash tables (to remember positions) sooner or later. I probably will too, but not anytime soon. Instead I will do the following: Always save the two best moves (instead of one), and never play the same move that was played two moves ago (assuming the position is good enough, and that the second best move is good enough). That will not stop all threefold repetitions, but at least the most common one, like 14.Rba1 Rab8 15. Rab1 Rba8 16. ... it will break the potentially repetitions pattern here by not playing Rba1). Also, by saving two moves I will be able to create some randomness, by giving it a certain chance of playing the second best move (if it's good enough). However, for testing purposes it is better having it playing deterministically, that way I can more easily spot errors (by detecting deviation from previous play when it should play the same).

I've discovered that having a quiescence search not only helps in the middle of tactical sequences, but also plays an important role in making the engine play positional. The reason is that without it, the computer will always think that it can take a piece at the end of the search (or that the opponent can do so, depending on whether it's an even or odd search depth), near the horizon beyond which it cannot see. And it will adapt its move choice to that and play more non-positional, even in a completely quiet position with no immediate captures possible. Well, I just find that interesting, but not so relevant now that I have a fully functional quiescence search.

And I've also implemented SEE to improve the move order (and therefore search speed) for the q search. The result is impressive: one position that earlier took over 600 seconds to analyze now takes only 21s. Usually the difference isn't that dramatic, but it's always faster. However, I still can't go deeper than 3 (complete) plies within reasonable time, so I haven't gained anything strength-wise by using SEE, but it's faster with three plies and also pretty close to being playable at 4 plies. I consider anything lesser than 10 seconds per move in average to be "within reasonable time" (then it can play 2 12:s, with some margin). (Btw, 3 and 4 plies may not sound like much, but with q search it can still play pretty decent chess. The q search often makes it go deeper than 20 plies into the position when analyzing captures.)

Next stop is iterative deepening (again, but this time I'll make it right and not give up easily.) That'll speed up things a lot I think, maybe even get me 5 plies deep.


Loomis said...

I had my engine playing on FICS before I implemented Q-search and this led to people accusing me of cheating by having a human play for the engine! Well, that's certainly different than the typical way of cheating.

Basically what was happening is that the computer would do a 6 (or 4) ply search and decide it was losing a piece by force (because the opponent can capture at the end of the line). The computer would find that the best idea is to sac the piece on move 1 for some tiny positonal benefit. Then you get the response from your opponent that no computer would ever hang a piece to a 1 ply tactic, so it must not be an engine playing.

The engine was occasionally very tactically adept in a complex position (this I think was a little luck). One guy berated me quite a long while because the computer could play all these great tactics at one point and then hang a piece for nothing on the next. He didn't think it was possible to program an engine to play like that.

XY said...

People often think they know things they don't, especially when they can back it up with pseudo-logic of some kind.

I think you should blog about your chess engine. Anything at all would be interesting (what's implemented, how, its performance, etc).

I've implemented collecting the principal variation now, so iterative deepening isn't far away. But it has caused a memory leak I haven't been able to find (which is driving me insane).

Locations of visitors to this page