# ex: set ts=8:

pizza
Fri Mar 31 01:43:14 EST 2006


8x8 board = 64 positions = 2^6
6 types of pieces:
	King
	Queen
	Bishop
	Knight
	Rook
	Pawn

assuming that we're dealing with permutations (i.e. that only piece type, and
not ID matters)...

assuming storage of permutations of 3 pieces...

type: 2^3
position: 2^6

  config        two bytes
  byte          per piece
    |              |
  --+--     -------+------
 /     \   /              \
[01234567][0123456789ABCDEF][ ... ]
           \ /\    /
            +  -+--
	    |   position
	    type

we really only need 9 bits, but since bytes are 8 we need that extra byte...

NOTE: the configuration byte would be stored on disk to let the app know how
long that record is... of course, if you separated the different
piece-permutations by arity...

3_piece_perms.dat
4_piece_perms.dat

then you could omit it completely...

also, since we're using 16 bits anyways, let's align them to 8 bit boundaries
to make our life better; also it should hopefully make the code faster with
fewer shifts...

     two bytes
     per piece
        |
  ------+------
 /             \
[0123456789ABCDEF][ ... ]
 \      /\      /
  --+---  --+---
   type    position


so by using 16 bits to store each piece/position you'll use
2*pieces*permutations bytes of storage; for 3 pieces...

2 * 3 * (64 * 63 * 62) bytes
  6   * (249984) bytes
     1499904 bytes
       ~1.5MB

in C:

enum {
	KING = 0,
	QUEEN,
	BISHOP,
	KNIGHT,
	ROOK,
	PAWN
};

struct piece_pos {
	unsigned char type;
	unsigned char position;
};

/* if you want to store the struct directly, you'll probably want the
 * non-standard GCC extension __attribute((packed))__ in the struct decl,
 * google for it if you want it
 */

struct piece_pos __attribute((packed))__ {
	unsigned char type;
	unsigned char position;
};


of course i could be missing something here, but check it out.