Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move Generation

Author: Tord Romstad

Date: 08:53:39 02/22/05

Go up one level in this thread


Hi Guillaume,

Some advice below.

On February 22, 2005 at 10:25:22, Guillaume MOYA wrote:

>Hi,
>
>I write in my spare time, a little chess program, I just have done the move
>generation and I play with alpha beta algorithm. My move generator is coded
>using the rotated bitboard stuff, it works well but I got very bad speed result.
>
>As an example, with this fen :
>
>r4rk1/p2q1ppp/n1pb4/1p1p3Q/3P2NB/P3P2P/1PP3P1/2R2R1K w - - 0 1
>
>when searching only at depth 4, with the simpliest eval function (just piece
>value count), it takes 3094 ms to compute the PV.

If you need 3094 ms to complete depth 4 at this position, the speed of move
generation is not your main problem.  The problem is that you search too
many nodes.  You should concentrate on improving your search, not your move
generator.

When your program is very young, there isn't any point in profiling, looking
for bottlenecks, and doing low-level optimisation.  Before you have a complete
and reasonably strong program, it is impossible to know where the bottlenecks
are.  When you improve your search and move ordering, the shape of your search
tree will change dramatically, and it is very likely that different functions
will dominate your profiler output.

It is often claimed that premature optimisation is the root of all evil.
This is just as true in chess programming as in programming in general.
At the moment, the best thing you can do is to spend your time trying to
implement a simple, complete, bug-free, flexible and readable chess program
with a reasonably efficient search and good move ordering.  Don't worry
about optimisation until later.

>Here's how my program proceed
>:
>
>1) Generate all moves
>2  Order move, using memory heuristic
>3) Expand tree, test if the king is in check, remove the node if yes
>
>and I use plain alpha beta with no funny stuff. When profiling my program, main
>time is consummed in the function that's computed attaqued square (called after
>a move is done to test if the king is in check).

For most moves, you can be 100% sure that the move doesn't leave the king in
check, even without doing any attack computations.  If the king is not in
check before the move is made, you only have to do the test for king moves
and for moves for which the 'from' square is on the same rank, file or diagonal
as the king.  For instance, if the white king is on g1 and is not in check,
the move c2-c4 will always be legal.  Note that this can also be done
*before* the move is made, saving some time.

But again, it is probably better not to worry about this at the moment.  In
fact, your current problem is a good example of why profiling and optimising
your program at such an early stage is not a good idea.  It is very likely
that the expense of move legality checking will be much smaller when your
program is more mature.  When your move ordering improves, the average number
of moves searched at every node will decrease.  As a consequence, your
function to verify move legality will be called less often.

>Is there another method? Is this kind of performance right without a hashtable
>or something else?

No, this kind of performance is not right, even without a hash table.  You
need to improve your search.  I suspect that you have a bug somewhere.

Here is the output for my program in your position, when I disable the hash
table and all sorts of pruning except alpha/beta cutoffs:

2 +82 0 156 Bf6 h6
3 +71 1 1516 Bf6 Kh8 Ne5 Bxe5 Bxe5
3 +82 2 3490 Rf5 Kh8 Rg5
4 +38 4 6936 Rf5 f6 Rcf1 Kh8
4 +96 7 16165 Bf6 Qe6 Qg5 g6
5 +300 23 64217 Bf6 Be7 Qg5 Qxg4 Qxg4 Bxf6
5 +431 33 91425 Nf6+ gxf6 Bxf6 Bf4 Rxf4 h6 Qxh6
6 +660 98 325992 Nf6+ gxf6 Bxf6 Bf4 Rxf4 Rfc8 Rg4+ Qxg4 Qxg4+ Kf8
7 +832 562 2059277 Nf6+ gxf6 Bxf6 Rfd8 Qh6 Qg4 hxg4 Bf8
8 +1357 3795 14613055 Nf6+ gxf6 Bxf6 Bf4 Rxf4 Qxh3+ gxh3 Rfb8 Qg5+ Kf8 Qg7+ Ke8
Qf8+ Kd7 Qxf7+ Kc8 Qxh7

Here is the output when I enable everything:
2 +82 0 156 Bf6 h6
3 +71 1 1433 Bf6 Kh8 Ne5 Bxe5 Bxe5
3 +82 1 2712 Rf5 Kh8 Rg5
4 +57 2 3637 Rf5 Kh8 Rg5 h6
4 +96 4 8207 Bf6 Qe6 Qg5 g6
4 +431 5 10615 Nf6+ gxf6 Bxf6 Bf4 Rxf4 h6 Qxh6
5 +660 6 12358 Nf6+ gxf6 Bxf6 Bf4 Rxf4 Rfc8 Rg4+ Qxg4 Qxg4+ Kf8
6 +832 9 21616 Nf6+ gxf6 Bxf6 Rfd8 Qh6 Qg4 hxg4 Bf8
7 +867 14 35899 Nf6+ gxf6 Bxf6 Qxh3+ Qxh3 Rfb8 Qg4+ Kf8 Qd7 Bg3 Qxc6
8 +1124 46 127124 Nf6+ gxf6 Bxf6 Qf5 Qxf5 Rfc8 Qd7 Bxa3 Qg4+ Kf8 Qg7+ Ke8 bxa3
h5
9 +1171 88 254936 Nf6+ gxf6 Bxf6 Qf5 Qxf5 Rfc8 Qd7 Be7 Qxe7 Rc7 Qd6
10 +9983 212 656226 Nf6+ gxf6 Bxf6 Bf4 Rxf4 Qxh3+ Qxh3 Rfc8 Rg4+ Kf8 Qxh7 Ke8
Qg8+ Kd7 Qxf7+ Kd6 Be5#
11 +9989 238 730560 Nf6+ gxf6 Bxf6 Bf4 Rxf4 Qxh3+ Qxh3 Rfc8 Qh6 Rc7 Rg4#


Good luck, and have fun!

Tord



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.