0x88 engines

[Uri Blass]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

I do not see how do you write evaluation without some board representation.

You may suggest not to spend time on optimization of board representation but you need some board representation.

Uri

[wgarvin]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

I like the idea, but I think perhaps it only works if you've written engines before. A lot of this stuff is not very intuitive and you don't figure out what questions you should be asking until AFTER you've got everything working. It's *then* that you have those "duh!" moments and say "Why didn't I think of that before?" For instance, most noob engines will happily trap their rook on h1 by playing Kf1 and Kg1, but humans never expect it because it's such an obviously stupid thing to do.

...

That was my thinking. Until you have something that works, and begin to study how to make it faster, it is hard for a first-timer to predict what needs to be done incrementally, what is done at point of use, and then which clever data structures will work best to make those things work well.

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy

You guys are all piling on Tord for some reason, but I think his comment does make a lot of sense. When you sit down to write a chess engine for the first time, you don't know exactly what info you need to have handy (read: incrementally available) to use in your evaluation function, or search extensions, or SEE, etc. So it makes some sense to try and write those first, before choosing and committing to, a complete board representation. Because that choice will affect how easy and fast it is to collect that information -- for example, are you going to maintain some sort of incremental attack tables like Diep? How would you decide that, without first writing some eval things and seeing how useful it is to have the info ?

So from that point of view, I think what Tord is saying is: Abstract out your board representation enough so that you can easily replace it later. It doesn't need to be stellar, it just needs to work well enough for you to write and test the eval and search. You won't know enough to choose the "best" board representation (including any incrementally-updated stuff that goes with it) until you know what info you need to have available in your eval and search.

Which in a way, is almost the same as what bob said earlier in the thread:

For a first cut, you need to pick a board representation that you understand, and can write readable code for.

[bob]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy

Actually he is talking top-down. You don't get to the details until the last minute.

[bob]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

I like the idea, but I think perhaps it only works if you've written engines before. A lot of this stuff is not very intuitive and you don't figure out what questions you should be asking until AFTER you've got everything working. It's *then* that you have those "duh!" moments and say "Why didn't I think of that before?" For instance, most noob engines will happily trap their rook on h1 by playing Kf1 and Kg1, but humans never expect it because it's such an obviously stupid thing to do.

...

That was my thinking. Until you have something that works, and begin to study how to make it faster, it is hard for a first-timer to predict what needs to be done incrementally, what is done at point of use, and then which clever data structures will work best to make those things work well.

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy

You guys are all piling on Tord for some reason, but I think his comment does make a lot of sense. When you sit down to write a chess engine for the first time, you don't know exactly what info you need to have handy (read: incrementally available) to use in your evaluation function, or search extensions, or SEE, etc. So it makes some sense to try and write those first, before choosing and committing to, a complete board representation. Because that choice will affect how easy and fast it is to collect that information -- for example, are you going to maintain some sort of incremental attack tables like Diep? How would you decide that, without first writing some eval things and seeing how useful it is to have the info ?

So from that point of view, I think what Tord is saying is: Abstract out your board representation enough so that you can easily replace it later. It doesn't need to be stellar, it just needs to work well enough for you to write and test the eval and search. You won't know enough to choose the "best" board representation (including any incrementally-updated stuff that goes with it) until you know what info you need to have available in your eval and search.

Which in a way, is almost the same as what bob said earlier in the thread:

For a first cut, you need to pick a board representation that you understand, and can write readable code for.

I was not attempting to pile on anyone. However, when I wrote Crafty, I first decided on the board representation. I then spent a month working on the details of just that. You can probably find discussions of this in late 1994 in r.g.c.c in fact where I wrote a move generator, posted it, got feedback, and did this several iterations. All the while, learning what was involved and how much of a full bitboard implementation I was going to do.

The board representation is a basic building block and will definitely influence how the rest of your code will look. You can write a basic search in 10 minutes. I used Ken Thompson's basic negamax to start with and was done in half that time. Without a board representation, you can't generate moves, make/unmake moves, determine if you are in check, evaluate positions, write a SEE, etc. All of those depend heavily on how you represent the board...

[diep]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy

Actually he is talking top-down. You don't get to the details until the last minute.

Indeed it qualifies for top-down nonsense.
See also Uri's reply. Uri has read it correct.

Without datastructure nothing works yet until it all has been designed unto the datastructure; in short that's bottom-up design. If you first make a datastructure you can test things by slowly adding functionality, which is the definition of top-down design.

Thanks,
Vincent

[bob]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

You're advicing to do some sort of bottom-up form of design of source code rather than top-down?

Oh dear.

Well, what else could we expect from a math guy

Actually he is talking top-down. You don't get to the details until the last minute.

Indeed it qualifies for top-down nonsense.
See also Uri's reply. Uri has read it correct.

Without datastructure nothing works yet until it all has been designed unto the datastructure; in short that's bottom-up design. If you first make a datastructure you can test things by slowly adding functionality, which is the definition of top-down design.

Thanks,
Vincent

I agree with how you think it ought to be developed, but your definition of "top down" is simply backward. In a classic top-down design, you write the main program. For every procedure you want to call, you write a dummy (aka a "stub") that does nothing. You then get the main program to function as intended. Then you take the layer of stubs right below the main program and you start to flesh those in. But whatever procedure you call you do not write, you just supply a stub. But now you are one layer deeper into the design and the code is getting more specific. You continue this until you reach what we would call the "tips" in a tree search. This is where the real work is done, and this is where it is necessary for all the basic data structures to be finalized.

But that design approach is difficult for chess, because so much of what is done at high-level code still depends on the capabilities of the data structures you end up with. I personally believe that the basic "operations" need to be written first, in conjunction with defining the data structures you are going to use. I wrote make/unmake/movgen as I designed the bitboard data structures. That's how I discovered that a bishops/queens or rooks/queens bitboard was helpful for generating moves.

Once you have the data structure and the code to update it properly, you need an evaluation, which is data structure dependent, and then the rest of the code which is pretty independent of the board representation.

The way I wrote Crafty was a hybrid approach. Bottom up for the make/unmake/movgen/data structure stuff, top down for the rest of the code.

[MattieShoes]

I wasn't trying to pile on anybody He obviously knows more about chess, programming, and chess programming than me. But I think that's exactly why his suggestion wouldn't have worked for me.

I really didn't know what to put INTO eval (still don't, actually). It started as piece values only. Once I had it *playing*, I added pcsq tables to value central pieces and keep the king tucked away. Then I could see it wasn't defending against passed pawns and making a shambles of its pawn structure because it wasn't paying any attention to it, so I added some pawn structure eval. Then I added a separate endgame pcsq table for kings, then bishop pair bonus, and so on. I needed it playing *first* though so I could see what it's doing wrong, where it's playing stupid.

I understand the point though -- If I start off with some strong opinion about what should be in eval, I could let eval dictate board representation.

[bob]

I wasn't trying to pile on anybody He obviously knows more about chess, programming, and chess programming than me. But I think that's exactly why his suggestion wouldn't have worked for me.

I really didn't know what to put INTO eval (still don't, actually). It started as piece values only. Once I had it *playing*, I added pcsq tables to value central pieces and keep the king tucked away. Then I could see it wasn't defending against passed pawns and making a shambles of its pawn structure because it wasn't paying any attention to it, so I added some pawn structure eval. Then I added a separate endgame pcsq table for kings, then bishop pair bonus, and so on. I needed it playing *first* though so I could see what it's doing wrong, where it's playing stupid.

I understand the point though -- If I start off with some strong opinion about what should be in eval, I could let eval dictate board representation.

Correct. and that is how you will do your second program, and your third, etc. But for the first one, it is hard to know what you are going to need until you reach the point where you actually need it.

[Tord Romstad]

I don't feel that anyone is trying to pile on me, but I must admit that I am surprised my little remark caused so many replies.

Being a non-programmer, I am not sure how the terms "top-down" and "bottom-up" are generally understood in programming, but both of them make some sense when describing my approach: The program is designed from the top down, but if one wants to write and test the code piece by piece, it would probably be most practical to do this from the bottom up. I usually don't write and test code this way, though. More about this below.

I agree with how you think it ought to be developed, but your definition of "top down" is simply backward. In a classic top-down design, you write the main program. For every procedure you want to call, you write a dummy (aka a "stub") that does nothing. You then get the main program to function as intended. Then you take the layer of stubs right below the main program and you start to flesh those in. But whatever procedure you call you do not write, you just supply a stub. But now you are one layer deeper into the design and the code is getting more specific. You continue this until you reach what we would call the "tips" in a tree search. This is where the real work is done, and this is where it is necessary for all the basic data structures to be finalized.

I don't recall ever having written such stub functions, but the approach you describe resembles a technique I often use in Lisp (the language I use in my day job). Lisp allows me to compile and run code which calls undefined functions (the compiler will emit a warning, though). I often do this intentionally. When the undefined function gets called, the program enters a break loop where I can choose between several actions, including manually supplying a return value for the undefined function, selecting some other function to call instead, or defining the function before continuing.

When writing a chess engine in C, I do it differently: I write the entire program (in top-down style) on paper before I type a single line of code at the computer. I don't start typing the code before I'm 100% sure the program is correct (which, of course, it never quite is, even though I am 100% sure). When everything is ready, I need a day or two typing everything and fixing all the silly little errors that have crept in everywhere. I write everything at once, rather than one little piece at the time. This is boring work, but it doesn't take a lot of time, and at the end I have a complete, working, stable and clean-looking chess engine.

Previously, I used to work more like most other participants in this thread seems to do. I started writing a board representation, a move generator (without "advanced" stuff like castling or promotions at first), an SEE function, and so on, and tested each of them with a few ad-hoc, non-rigorous tests. As I proceeded to more and more high-level parts of the program, I invariably found that the low-level parts didn't fit together as well as I had hoped, and I had to throw in ugly little hacks everywhere to make things work as intended.

Moreover, there were always bugs. Segmentation faults, non-terminating loops, pieces which suddenly changed color for no good reason, search bugs, hash table bugs, mysterious non-reproducible losses on time with ponder on, and so on. I spent countless hours in the debugger, or inserting output commands everywhere in the code to find out why something didn't work as intended. I usually managed to fix the problems, but the process was unbearably painful, and the code looked more and more messy.

In the end, I decided that life is just too short to debug C/C++ code. The endless edit-compile-test-debug cycle is sheer torture. I only write code I know is correct, and the easiest achieve this is working top-down. It requires some mental discipline, but I end up with much cleaner code. Even more importantly, working with pencil and paper in a park or café is infinitely preferable to sitting in front of a computer and staring at a debugger.

Matt has a point, though: This style of working really only works when you already have a good understanding of the problem domain. If I were a beginner wanting to start chess programming, I would have started out with a more interactive programming language, and consider switching to C/C++ only when I had a satisfactory prototype.

Vincent also makes a good point: I am a mathematician, not a programmer, and this certainly has an impact on how I prefer to work.

Tord

[Dann Corbit]

The first step is to come up with a workable design that you are happy with. Which starts with board representation. Then a functional search and evaluation that plays chess.

I would recommend the opposite order: Write the search and evaluation function first, and do the board representation later. Starting with the board representation is a form of premature optimization: Before you have decided what sorts of questions you want to ask about the position in the search and evaluation, you can't know what board representation suits your needs.

Tord

If you write in abstract terms, you do not need any representation.

So (for instance) like this:

Code: Select all

Evaluation(ChessGame &game)
{
...
blockedPawnPenalty = game.CountOfBlockedPawns() * blockedPawnMultiplier;
}

As you can see, we do not need any specifics to code our evaluation function. It relies on the underlying methods to return the wanted values.



I do not see how do you write evaluation without some board representation.

You may suggest not to spend time on optimization of board representation but you need some board representation.

Uri