Friday, April 22, 2005

The need for a book update

I have to admit: I'm not really a good programmer. I still program in plain C, have no idea about object-oriented programming and new developments like Java have passed me by. Good practices like documenting code, using CVS and the like are not on my skills list either. Why do I mention this? My programs are usually "work in progress". Often, I know better but don't bother to fix certain things. The book generator is such an example. As a small excuse, I wrote it at a time where I didn't have the 8pc database yet and didn't ever expect to generate opening databases with millions of positions. But now that this has happened, some rather obvious flaws in the design of the book generator have appeared. The basic problem is that with the 8pc database and a huge book (meaning lines are searched very deeply), most openings turn out to have the value 0 - the book generator manages to more or less find a path directly from the 3-move starting position into the endgame database. It also turns out that in most positions, there are a number of moves that all have value 0 - all of these moves draw. However, typically one of these moves might leave you in a strong position, and the opponent has to play accurately to draw, while another of these moves could leave you struggling for the draw. Of course, I would want Cake to choose the move that leaves it in what is called a strong draw. But how do you do this? The solution I envisaged at the time I wrote the book generator works as follows: In every position, the opening database contains the values of all moves as they were computed when this position was first examined, plus the values that come from propagation of further expansion. The propagated values are the true values, but if two or more of these are the same, I want Cake to choose the move which looked better on a shallower search. That's just what it does right now. Does all of this make sense? Doesn't this sound like a sensible approach? Well, there is a flaw: When I started generating the opening database, I used a beta version of Cake Sans Souci for the first approximately 90'000 moves. Then I switched to Cake Sans Souci, and much later, already after over 1 million positions, I switched to Cake Manchester. At the same time, I upgraded the hardware from an Athlon XP 1600+ to a XP2400+ and later to an Athlon64 3000+. All of this means that the first positions examined - the most important ones! - were searched with a clearly weaker machine+engine-combination than what I have today. The first positions are the most important ones, because that's where you decide how to play - at later stages things are often forced or simply a draw. Therefore, the most important decisions in the opening are not made by Cake Manchester, but by Cake Sans Souci beta, and I'm not happy about that! I'm in the process of computing a small opening book with Cake Manchester, which I will then import into the full opening database, which should improve things. There are many other details that are not good in my book generator, but this post is already too long to write about them now!

2 comments:

Nelson Castillo said...

> I have to admit: I'm not
> really agood programmer.

I don't agree. Your source code
is nice. The source code of
Damas99 sucked. Its good to
know it's lost forever :)

> I still program in plain C

Me too. I cannot say I'm a great
programmer but I like to program a lot.


I converted from C++ to C. I switched to
C++ because I didn't know how to use C in
the first place.

> I have no idea about
> object-oriented programming
> and new developments like Java
> have passed me by.

OOP is pure hype (at least C++ and Java).
The most important part of Java is the
API. Well, a few features of interpreted
languajes make them suitable for some
tasks. C++ templates can be nice, and
also the Standar Template Library.

On the other hand, Garbage collection
really helps!

I used plain C in Tamal
and it uses objects. You don't need
C++ or Java to use objects.

Right now I'm planning to mix
functional programming and plain C
in new developments.

> Good practices like documenting code

You shouldn't really have to document
much if your code is readable enough.
In fact, I avoid writting comments.
Instead, I focus on writing readable
code. You only need comments when you
want to say what you're gonna do, not
HOW you're going to do it. The source
code should talk about that.

I peeked at cake 1.20 and I found it
_very_ easy to read.


> using CVS and the like are not on my
> skills list either.

You really should use subversion or
another version control system. I think
it frees your mind. Sometimes
(even unconsciously!) you don't try
things to avoid the burden of tracking
changes. With a version control system,
you can take a fresh snapshot, and
let it flow with no fear. If
it's nice, you commit what you have
to commit.

tortoisesvn is easy to use. It will
use a local repository in harddisk
of you don't want to create the
suvbersion repository.

http://tortoisesvn.tigris.org/

(I think you use Windows).

> Why do I mention this? My programs are usually "work in progress".

Cool :)

> Often, I know better but don't bother to fix certain things.

It's ok :)

> The book generator is such an example.
>As a small excuse, I wrote it at a time
>where I didn't have the 8pc database yet
>and didn't ever expect to generate
>opening databases with millions of
>positions.

Cool. Early optimization is no good :)
Is better to rewrite something that
doesn't suit you anymore than writting
code that MAY be useful.

> But now that this has happened, some
> rather obvious flaws in the design of
> the book generator have appeared.

You'll fix them someday if it's important.

> I would want Cake to choose the move
> that leaves it in what is called
> a strong draw. But how do you do this?

Your solution is not obvious. I guess
that choosing the one that looks better
with a shallower search makes you feel
safer.

> Therefore, the most important
> decisions in the opening are not made
> by Cake Manchester, but by Cake Sans
> Souci beta, and I'm not happy about
> that!

I understand now.

> this post is already too long to write about them now!

Thanks a lot. Great post.

Bob said...

If the source for Damas99 is lost, that is actually a shame, as that program is one of the strongest "simple" programs around. It was and is a very good piece of work.