Author: Ratko V Tomic
Date: 20:31:52 11/06/99
Go up one level in this thread
> YOU ARE RIGHT! The number of bits is not 2, but 1.95 as you wrote. Well, there are even more surprises in the bishops optimization (which appears less and less so). We have compared two approaches: 1) B Method (BM): where a single piece type (bishop) can be placed anywhere on the board (up to 64 squares available). Initially there are only 2 B pieces for each side, but promotions could increase this to 10. 2) LD Method (LDM): there are two types of this piece, light squared (L) and dark squared (D), each can be placed on at most 32 squares of given lightness. Initially there is only one of each type (for each side), but promotions could increase L+D to 9+1 r 1+9 LD pieces (for each side). This method is more accurate of the two. When we enumerate positions, we need to give (effectively) how many of each piece type are there (Material Content, MC) and how are this pieces placed on the board (Material Placement, MP). Thus, conceptually, the code for the piece consists of two parts, MC part and MP part. The saving of 1.95 bits, we were discussing, belongs only to the MP part -- it represents a reduction in the number of distinct placements of the given (and fixed) material if we switch from BM to LDM counting. When BM uses B pieces for a given MC state and places them anywhere on the board, that generally covers multiple MC states of the LDM. Namely if the BM MC state gives count of k for its B piece type, that represents k+1 MC states for the LDM, the states being different partitions of the k B pieces into k L+D pieces (0L,1L,2L,..,kL i.e. there are k+1 ways to break the k Bs between L and D). Therefore, the MC part of the full code specifying a position for the LDM will increase relative to the corresponding MC part of the BM. Depending on how many B pieces there are in a given MC-BM, the MC-LDM part will increase by different factors, negating much of the the gain made in the MP part of the full code. To get some idea how these two effects compare, I wrote a little program to enumerate all distinct legal MC states for one side (white or black), i.e. up to 8 pieces and 8 pawns, all legal promotions and captures counted. The MC states counts are for #MC_BM=8694 cases while #MC_LDM=26298 cases, i.e. on average (for one side material), the MC_BM gains 1.596861 bits in the MC part of the code. At the sme time, the bishops factors in the placement part (MP) were on average (over all MC states): MP_LDM=1.909271*10^8=27.50845 bits, while MP_BM=5.782313*10^8=29.107071 bits, i.e. in the MP part of the code, BM loses to LDM by 1.598625 bits. The total gain (for MC+MP parts) of the LDM over BM is therefore only 0.00176 bits. This gain is due to the slight overcounting of cases by the BM which ignores that in the initial position bishops are of two types (so it effectively counts LL+DD+LD cases of which only LD is legal). But once the promotions and captures are accounted for, as this tiny gain shows, this initial state difference gets entirely swamped by the arbitarily-colored bishop sets, where BM and LDM count the same thing, just in a different way.
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.