Author: Koundinya Veluri
Date: 14:56:54 11/20/01
Go up one level in this thread
On November 20, 2001 at 16:55:13, Michel Langeveld wrote: >On November 20, 2001 at 05:04:42, Michel Langeveld wrote: > >>Hello all, >> >>I implemented qsearch in my program nullmover, but got a problem for it back. >> >>When I search with a depth 1 (just testing at the moment) my program thinks that >>after the openingmove 1. d4, ... h6! is the best move. >> >>After h6 the qsearch starts. >> >>[D]rnbqkbnr/ppppppp1/7p/8/3P4/8/PPP1PPPP/RNBQKBNR w KQkq - 0 2 >> >>The qsearch evaluates _only_ captures now. The program thinks white HAS to take >>on h6 then (is only capture in that position) and black can win a bishop after >>gxh6 or Rxh6. So score is about +2 for black then. This is incorrect of >>course.... >> >>I'm thinking about ways to solve this. One way is to implement a null move so >>that beside capturing there's always a doing nothing option. But I was curious >>how you guys solve this thing. >> >>Regards, >> >>Michel Langeveld > >Ok, > >Fixed the qsearch with a no move situation >Debugged it and tested it. It works very well at the moment. > >I also implemented a better move ordening. >My search sometimes BOOMS already at ply 1 in tactical positions. >How can I fix this? Can I stop qsearch at an centain depth? > >history: >(d2-d4 e7-e6 c1-e3 f8-d6 d4-d5 e8-f8 e3xa7 d6xh2 a7xb8 h2xg1 h1xh7 > a8xa2 b8xc7 g1xf2 e1xf2 d8xc7 d5xe6 a2xb2 e6xf7 h8xh7 f7xg8B b2xb1 > d1xb1 f8xg8 b1xb7 c7xc2 b7xd7 c2xe2 f1xe2 c8xd7 ) Hey Michel, There are a lot of strange captures in that line. Something is not right, and I think it's your capture move ordering. Do you use MVV/LVA to order captures? For example, consider the position after 1. d2-d4 e7-e6 2. c1-e3 f8-d6 3. d4-d5 e8-f8: [D]rnbq1knr/pppp1ppp/3bp3/3P4/8/4B3/PPP1PPPP/RN1QKBNR w KQ - 0 4 Assuming that qsearch starts here, say the first capture it sees is e3xa7. So far, assume that the window is (-INFINITY, INFINITY). A material-only eval here would give 0. So alpha = 0, therefore window is (0, INFINITY). Now make 4. e3xa7 and call qsearch with window (-INFINITY, 0). Eval here is -100 (say pawn = 100). So alpha = -100, therefore window is (-100, 0). If you use MVV/LVA, 4... a8xa7 will be ordered before 4... d6xh2. So make 4... a8xa7 and call qsearch with window (0, 100). Eval here is -200. Alpha is still 0, and further captures from here won't improve alpha. So after searching the rest of the captures from here, qsearch will return 0. Here, window is (-100, 0) so beta cutoff occurs and qsearch will return 0. Here, window is (0, INFINITY), but searching 4. e3xa7 is now complete. In the end, 4... d6xh2 didn't even need to be searched! I got some similar problems though when I first did qsearch. It was way too slow. For me, using a regular eval was much faster. But that's before I optimized my program (I was getting approx. 5 kn/s), before I added hash tables or null more or many other common search techniques. I'm not sure exactly what I fixed, but as I improved other parts of the program, this effect slowly died away and qsearch started to show more improvement than a regular eval. Currently I search all captures, promotions, and check escapes until there are no more. Forward pruning greatly helped though, but it requires a fast SEE. Although writing an accurate SEE was a pain, the gain from it was very noticable. Regards, Koundinya
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.