Author: Michel Langeveld
Date: 15:12:35 11/20/01
Go up one level in this thread
On November 20, 2001 at 17:56:54, Koundinya Veluri wrote: >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 Thanks for your detailed anwer! My MVV/LVA moveordering was broken. Fixed it and now it works a lot faster and better. I'm searching 4 ply now and most of the positions. Tomorrow I've a day of and I'm going to work on: - hashing - incremental deepening - killers - time management. regards, Michel
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.