Author: Robert Hyatt
Date: 10:28:29 05/08/00
Go up one level in this thread
On May 08, 2000 at 11:09:25, Bas Hamstra wrote: >On May 08, 2000 at 10:04:50, Robert Hyatt wrote: > >>On May 08, 2000 at 08:57:49, Bas Hamstra wrote: >> >>>It seems that some (i.e. DarkThought) rotated BB programs use 1-at-a-time >>>movegeneration, that generate just the best MVV/LVA move. I don't understand >>>how they can make this work. >>> >>>Idea being that in many cases you only need the first capture, thus saving a >>>lot of work. On average. However for this to make sense, it should cost you >>AT LEAST fewer ticks to generate the 1 best capture than to generate them all >>>and do a sort. >>> >>>The point: I see NO way to fetch the 1 best capture substantially faster than >>>doing all captures. So how do you do it? >> >>You do it in two pieces. First, you find the most valuable opponent piece >>that is under attack (find-victim cycle). Then you find the least valuable >>piece of yours that is attacking this piece (find-aggressor cycle). If you >>have to do all moves, this is definitely slower than a full generate all-moves >>case. As a result, I think this is a 'break-even' proposition, since about >>1/2 of the nodes are full-width (odd ply search) and 1/2 of the nodes are one- >>move searches. Since I don't like MVV/LVA on general principle (it will try >>a move like QxR where the R is defended by a pawn, before it will try a move >>like BxP where the pawn is free.) > >About break-even: have you tried it? I did, and you have to do a good job to >generate 1 capture significantly faster than *all* captures... > >Example: after e4 e5 Nf3 Nf6 Nc3 Nc6 Bc4 Bc5 > >a) Build 10M times a combined white attack map: 8 seconds >b) Generate *AND* sort 10M all white captures: 12 seconds > >Note that with that 8 seconds you are not there yet. To find and push the best >capture 10M times might take you 10 or 11 seconds. See what I mean? > >>>a) Doing for each enemy piece an AttackTo is very expensive >>>b) Building a combined attackmap and finding the highest attacked victim >>> is basically the same as doing all captures. >>> >>>So: what am I overlooking here? >> >>Note that generating the bitmap (all squares I attack) is far simpler than >>generating the _moves_ from such a bitmap. > >Not *far*. See numbers in example above. And with that 8 seconds there still was >a lot of work to be done... In my code, producing an attack bitmap for a single piece takes almost no time, while turning this into a list of moves is very slow. That was what I meant by "far simpler". repeatedly finding the first 1 bit, adding that to a move, storing that move into a list, repeated N times, is really slow...
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.