What is best possible with minimal programming

[Dann Corbit]

Well, a lot of programs are the best program for their size. In fact, probably every program is, as no two sizes are exactly the same. (Clones exempted. )

So no doubt you are right. But without a theoretical framework for size dependence, that would allow us to compare programs of different sizes, this does not mean a thing.

I don't think that the fact that some large programs are weak means there is no relation between size and strength. There are also programs that are weak even in the face of being allowed to think very long, and yet there is a very general relation between thinking time and strength for the same engine. To discover a relation between size and strength, one should also first look to different versions of the same engine, during their development.

A strong program is not necessarily best.
Sometimes I want to play against a weaker program, and sometimes I want to hurl myself against the rotating knives that calls itself "Rybka".

I think that there is a certain elegance and beauty in writing compact chess programs. There is also an arcane 'wizard' element when it gets compacted enough (I do, for instance, admire your program).

As far as strength goes, I think that writing clear, bug-free code is important. The most important thing of all is to use efficient O(f(n)) algorithms.

Since Thinker is not open source, we cannot say exactly what it looks like inside. But Lance has shown us fragments of his code. I considered the fragments I saw to be very beautiful. When I see code like that, I know that the program is going to do well.

I think that there is room for every sort of chess program. I don't particularly enjoy FRC, but I understand that many people get great enjoyment out of it. Some of my favorite programs are probably at the bottom of other people's lists. I just love Golem. Something about the way it plays is very human (If you put it behind a closed door I don't think I could tell you if I was playing Golem or my sister Julie). It's not a terribly strong program but I enjoy playing against it. There are other weaker programs that I don't really like playing. I will have to give the winner of the "Mr. Irrelevant" tournament a shot to see if it is suitable for young children to play against.

I guess that {in the near term, at least} we could learn more from looking at Thinker's code than Rybka's. The reason I say that is because it is so compact and yet (from what I have seen) clearly written that we would grasp the concepts instantly. When you get a giant N-Reactor machine like Crafty {or any other program with over a megabyte of code} it takes a long time to absorb things because of the detail.

Another author with really beautiful code was Bas Hamstra. I am sorry that he stopped development on his engine, because I think it was definitely headed in the right direction.

I admire the coding style of Fabien too, because of his masterful use of asserts.

Quite frankly, I think I have enjoyed going over every open source program that I have ever examined, except one {which shall forever remain nameless}.

[H.G.Muller]

Well, good thing that Joker is not open source then, for by now it is such a mess that even I am appalled by it.

I went into this issue of size because the way power depends on size is actually a thing that interests me, and in fact was what inspired the micro-Max project. The idea was that if programs were just linear sequences of instructions, their power would grow proportional to size, but that the possibility to call subroutines makes the power grow exponentially. To do twice as much, you only have to include the code for it once, and call it twice. And the calls hardly take any space. Just pass an extra argument that accounts for the difference of what you want done the first and the second time. Or break it up into parts that were the same, and parts that were essentialy different, and put these in a new layer of subroutines. By collapsing the code this way, you can do very much more with only marginally more code. In fact, your subroutines are defining ever more powerful new languages, that help you to write programs on a higher level more efficiently by drawing on the routines of the lower levels, rather than having to specify the task fully themselves.

As to the size of Chess programs: I don't really think that playing good Chess requires a lot of code. Chess programs are large only because they use space-wasting techniques that perform only marginally better than compact techniques, because anything helps, and size is for free. But art cannot be judged by performance alone.

[Uri Blass]

Well, good thing that Joker is not open source then, for by now it is such a mess that even I am appalled by it.

I went into this issue of size because the way power depends on size is actually a thing that interests me, and in fact was what inspired the micro-Max project. The idea was that if programs were just linear sequences of instructions, their power would grow proportional to size, but that the possibility to call subroutines makes the power grow exponentially. To do twice as much, you only have to include the code for it once, and call it twice. And the calls hardly take any space. Just pass an extra argument that accounts for the difference of what you want done the first and the second time. Or break it up into parts that were the same, and parts that were essentialy different, and put these in a new layer of subroutines. By collapsing the code this way, you can do very much more with only marginally more code. In fact, your subroutines are defining ever more powerful new languages, that help you to write programs on a higher level more efficiently by drawing on the routines of the lower levels, rather than having to specify the task fully themselves.

As to the size of Chess programs: I don't really think that playing good Chess requires a lot of code. Chess programs are large only because they use space-wasting techniques that perform only marginally better than compact techniques, because anything helps, and size is for free. But art cannot be judged by performance alone.

I think that you can expect diminishing strength from size.

It is clear that out of all possible programs with size of at most x bytes one program has the best rating.

Denote this rating f(x).

I suspect that we may have something like the following:

1)f(1024)=1500
2)f(2048)=2300(micromax is weaker than it but there is no reason to think that you wrote the best possible program with less than 2 mbytes)
3)f(4096)=2800
4)f(8192)=3100

Uri

[H.G.Muller]

Well, this is an unproven conjecture. Future pruning tricks might give an enormous improvement in playing strength, without adding too much size. It is just that you have to have somthing usefull to add. As long as the tricks have not been discoverd, the only thing you could use extra space is by adding inferior and marginally useful stuff, and that of course gives deminishing returns.

[Vegan]

There has not been that much research into pruning of late for some reason.

[Dann Corbit]

There has not been that much research into pruning of late for some reason.

Late move reductions is fairly recent.

[Vegan]

Is there a page on it anywhere? I would be interested in seeing some new ideas.

[NaltaP312]

Hi All,

I'm new and try to do chess engine.
I have read than "The way of move generation is usually totally irrelevant for the speed, and hence strength of a program. Bitboard is usually slower than mailbox. "

So i don't understand why it is faster to use mailbox and not bitboard for move generation.
If i consider a lot of chess engine, they implement bitboard.
What is the best way ?

For my part, i have used KoggeStone and some tips and all is fine, i have about 1 000 000 000 moves in 30 seconds.
is it good ?
What is the advantage to use bitboards if it is not speed ?

regards
NaltaP312

[H.G.Muller]

The advantage of bitboards is that they can also speed up evaluation. (E.g. mobility counting, detecton of pinned pieces.) For te move generation and tree-walk alone(e.g. caculating perft) mailbox (+piece list) is usually faster. Mainly because MakeMove() and UnMake() are usually slow.

So it depends a bit on how advanced your evaluation is whether you will be able to earn back the hit you take on convering your search to bitboard, or not. And on how clever you are to make your evauation work through differentially updated auxiliary tables when you use mailbox.

[NaltaP312]

Hi,

thanks for this response H.G Muller.
At this time i have implemented move generation.

I use the langage C, it is time to retrieve my students course
I test the speed like this :
int moves[64*256];
int x = 0;
long total = 0;
int i=0;
clock_t start, stop;
double elapsed;
start = clock();

for (i=0; i<loop; i++) {
total = total + generateLegalMoves(moves, x);
}
stop = clock();
elapsed = ((double)stop - start) / CLOCKS_PER_SEC;
printf("Time elapsed : %f for %d nodes generated.\n", elapsed,total);

Regards
NaltaP312

[H.G.Muller]

Well, this is not the entire story, for several reasons:

In a complete engine there is a kind of speed trade-off between generating moves (which is what you measure) and performing the moves. The more information on the board state you store, the easier (and thus faster) it becomes to generate moves. But pdating that extra information when you actualy perform the moves will slow you down there. The extreme example to this would be a differentialy updated move list or attack table (which is essentially a move list sorted by to-square). Generatng moves takes zero time there, but when you move a piece, you need a quite complicated algorithm to update the list. So much, that it is hardly competative.

A second point is that your test program generates moves for the same position all the time. This is very misleading. Some methods (e.g. magic bitboard) use huge tables, which likely overflow the cache (and definitely overflow the L1 cache). But any single position draws ony on a sall part of these tables, that easily fits in L1. So once the needed table entries are cached, generating moves from that same position again and again is lightning fast, while in a real search the memory accesses to new table elements needed for new moves in new positions are the dominant slowdown.

A more realistic test for speed is a so called perft: not only generate the moves, but also prform them, and then recursively generate all moves from the new positions and do those, etc., N levels deep. (Usually N=6, 7 or 8, when starting from the opening position.) This calls the move generator for many different positions, and also includes the time for making the moves. By counting the leave nodes, you also immediately see if your move generator is bug free.

[NaltaP312]

Hi,

thanks a lot H.G for this clarification.
I'm really a newbie in this room and i really appreciate your help.
So now, i will try to implement the do and undo move and test it with perft.

I think i will go back when i will finish this step.

Regards
NaltaP312