micro_shogi_count.c

#include <stdio.h>
#include <locale.h>

/* estimate the endgame tablebase size of micro shogi */

enum {
	/*
	 * number of ways to place the kings such that they don't check
	 * each other. This assumes that the Sente king is always placed
	 * on the right half of the board, we can cut the number of
	 * positions in half by observing this symmetry.
	 */
	KING_COUNT = 3 * (20 - 9) + 5 * (20 - 6) + 2 * (20 - 4) /* 135 */
};

static void do_piece(int cohort, int shift, unsigned long long *size, unsigned *pieces)
{
	switch (cohort >> shift & 3) {
	case 0:
		break;

	case 1:
		++*pieces;
		*size *= 2; /* account for promotion */
		break;

	case 2:
		*size = 0;
		break;

	case 3:
		*pieces += 2;
		*size *= 2; /* account for promotion (*4), account for indistinguishability (/2) */
	}
}

/*
 * compute the number of ways for one cohort.  A cohort is characterized
 * by the pieces that are on the board.  For each pair of pieces of the
 * same kind, both, one, or none can be on the board, so there are
 * 3 ** 4 = 81 cohorts.  For simplicity, we compute all 256 cohorts but
 * throw out those where the high piece is on the board but the low
 * piece isn't.
 *
 * the size starts out at KING_COUNT * 256 as each piece can be owned
 * by sente or gote and there are 256 pieces.  We could discount the one
 * duplicate ownership for when both pieces are not on the board, but it
 * turns out that doing so makes the code more complicated at a very
 * small size reduction, so we don't do that.
 */
unsigned long long do_cohort(int cohort)
{
	unsigned long long size = KING_COUNT * (1 << 8);
	unsigned i, pieces = 0;

	do_piece(cohort, 0, &size, &pieces); /* bishops */
	do_piece(cohort, 2, &size, &pieces); /* golds */
	do_piece(cohort, 4, &size, &pieces); /* silvers */
	do_piece(cohort, 6, &size, &pieces); /* pawns */

	if (size == 0)
		return (0);

	/* number of squares */
	for (i = 0; i < pieces; i++)
		size *= 18 - i;

	return (size);
}

extern int main()
{
	unsigned i;
	unsigned long long size, accum = 0;

	setlocale(LC_ALL, "");

	for (i = 0; i < 0x100; i++) {
		size = do_cohort(i);
		printf("0x%02x: %'21llu\n", i, size);
		accum += size;
	}

	printf("total %'21llu\n", accum);

	return (0);
}

/*
 * ideas for making this feasible:
 *
 * - we can save each bunch of positions with the same pieces on the
 *   board, the same onwership, and promotion into one file, called a
 *   cohort.  One cohort has the following sizes:
 *
 *     8 pcs:  14 GB
 *     7 pcs:   2 GB
 *     6 pcs: 451 MB, 226 MB
 *     5 pcs: 138 MB,  69 MB, 34 MB
 *     4 pcs:  10 MB,   5 MB,  2 MB
 *     3 pcs: 661 kB, 300 kB
 *     2 pcs:  41 kB,  21 kB
 *     1 pcs:   2 kB
 *     0 pcs: 135  B
 *
 * - from each cohort, moves can reach into the same cohort and up to
 *   16 assoziated cohorts. The maximum is reached when all pieces are
 *   on the board and 4 pieces are owned by Sente. Then each Gote piece
 *   can be captured with a different Sente piece, yielding 4 * 4 = 16
 *   associated cohorts.
 *
 * - an 8 pcs cohort is associated with up to 16 cohorts with 7 pieces,
 *   but a 7 pcs cohort where Sente owns the piece in hand is associated
 *   with two 8 pcs cohorts.  This would indicate memory usage of up to
 *   2 * 14 GB + 12 * 2 GB = 52 GB.  This is a lot of memory.  Perhaps
 *   we can only load one associated cohort at a time at some loss of
 *   speed.
 *
 * - for associated cohorts, we only need to store win/loss information;
 *   this is two bits of information. Thus for the worst casse 8 pcs
 *   cohort we need 14 GB + 16 * 2 GB / 4 = 22 GB and for the worst case
 *   7 pcs cohort we need 2 GB + 2 * 14 GB / 4 + 12 * 2 GB / 4 = 15 GB.
 *   This memory usage is quite feasible.
 *
 * - I hope to reach a compression factor of 4 with stock compression.
 *   perhaps more is possible with custom compression.
 */