John's Chess Playground

Number of chess diagrams and positions

In a 2006 posting to newsgroup rec.games.chess.computer, Will Entriken proved an upper bound of 23937533792747905898433845980097921846050276105440 on the number of chess diagrams (roughly 2^164). The following Haskell program improves this to 45193640626062205213735739171550309047984050718 (less than 2^155) for the number of positions.

import Control.Monad
import System(getArgs)
import Array
 
-- given a maximum number of pawns (normally 8, but 7 with fixed en-passant)
-- and maximum number of initial rooks (normally 2, but 1 or 0 with castling)
-- to choose, return list of possibly armies, where each army is summarized
-- as a tuple of <#pieces, #pawns, #promotions, #factorial_product>
armies np ir = do
  q <- [0..1+np]
  let prom1 =         max (q-1) 0
  r <- [0..ir+np-prom1]
  let prom2 = prom1 + max (r-ir) 0
  b <- [0..2+np-prom2]
  let prom3 = prom2 + max (b-2) 0
  n <- [0..2+np-prom3]
  let proms = prom3 + max (n-2) 0
  guard $ proms <= np
  p <- [0..np-proms]
  return (q+r+b+n, p, proms, fac q*fac r*fac b*fac n*fac p)
 
-- precompute first 65 factorials into array for efficiency
fac :: Int -> Integer
fac n = fac64!n where fac64 = listArray (0,64) (scanl (*) 1 [1..64])
 
-- given a number of pawns to fix for each color (1 for en passant)
-- and amount of space available for pawns
-- and number of white and black rookks fixed by castling
-- return number of possible positions
count fixp pspace fixwr fixbr = sum $ do
  let np = 8-fixp
  (wpcs,wp,wproms,wprod) <- armies np (2-fixwr)
  let wpx = np-wp-wproms                 -- white p captured
  (bpcs,bp,bproms,bprod) <- armies np (2-fixbr)
  let bpx = np-bp-bproms                 -- black p captured
  let caps = 30-2*fixp-fixwr-fixbr-wp-bp-wpcs-bpcs
  guard $ wproms <= bpx + caps
  guard $ bproms <= wpx + caps
  let space = 62-4*fixp-fixwr-fixbr-wp-bp
  return $ (fac pspace `div` fac (pspace-wp-bp)) *
           (fac space `div` fac (space-wpcs-bpcs)) `div` (wprod * bprod)
 
count0 (mul,ek) = mul * count 0 (46+ek) 0 0
 
-- Diagrams
-- there are 212 configurations of kings on ranks 1&8
-- there are 1448 configurations of one king on ranks 1&8, and the other on 2-6
-- there are 1952 configurations of kings on ranks 2-6
main0 = print . sum $ map count0 [(212,2),(1448,1),(1952,0)]
-- 22124621884617108585387385940828998876019391612
 
-- given a multiplier, number of edge (first or last rank) kings,
-- fixed white and fixed black rooks
-- return number of possible positions
-- this assumes that side-to-move is known, say white
-- each of the squares a5-h5 can have a black pawn en-passent
-- capturable by 2 white pawns, except a5/h5, which could only
-- be captured by 1 white pawn
countep (mul,ek,fwr,fbr) = mul *
  (count 0 (46+ek) fwr fbr + (8*2-2) * count 1 (42+ek) fwr fbr)
 
-- Positions
-- the first seven tuples count configurations
-- of kings that can castle in various ways
-- and where the other king is either on ranks 1&8 or 2-6
-- The factor (* 2) counts for either side-to-move
main = print . (* 2) . sum $ map countep
  [(1,2,2,2),(4,2,1,2),(4,2,1,1),
   (2*9,2,0,2),(2*43,1,0,2),(4*11,2,0,1),(4*44,1,0,1),
   (212,2,0,0),(1448,1,0,0),(1952,0,0,0)]
-- 45193640626062205213735739171550309047984050718