Author: KarinsDad
Date: 17:25:06 08/18/99
Go up one level in this thread
On August 18, 1999 at 19:41:24, David Eppstein wrote: >On August 18, 1999 at 12:33:18, KarinsDad wrote: >>I dropped the number of failures from 47 out of 351 to 18 out of 351. >>I dropped the maximum number of bits required from 164 to 162. >>There are now 2 162 bit cases and 16 161 bit cases (based on work so far, but >>this is a fairly complex algorithm, so there is a chance of a mistake; I will >>have to do more work to verify these numbers). > >Doesn't 2 * 2^162 + 16 * 2^161 > 2^165? >So even ignoring the cases you can't handle, you still have 166 bits required. >Why do you say the maximum required is 162? The cases are not part of the same position, but rather templates of given position types. For example, you could split positions into 17 cases: ones with 16 pawns, one with 15 pawns, ..., ones with zero pawns. Any position that fell within that case would have to be handled by the algorithm for that case. I happened to split it up further beyond 17 cases and have 351 of them. 333 of the cases can be handled in 160 or fewer bits (worse case). 18 cases require either 161 or 162 bits (worse case). Several of my cases that require 161 bits are ones with zero pawns. The reason for this is that my algorithm cannot distinguish between a position with zero pawns and a position with one or more pawns (without adding another bit as a flag). Hence, these are cases that (worse case) can have 12 promoted pawns, 16 original pieces, and the algorithm can handle a pawn, but doesn't need to (hence, there are still 6 piece types that must be handled) and it requires about 3 or 4 more bits than it would if I could determine that a pawn does not exist. KarinsDad :)
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.