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.