> >24 bytes = cards in our draw pile
> >21 bytes = down cards in the build piles
> > 7 bytes = top up card in the build piles
> >(that's 52 bytes for 52 cards so far)
> >14 bytes = up cards below the top card in the build piles
> > 4 bytes = ace piles (unordered; in order only 2 bytes)
> >--------
> >70 bytes
> >
> Why not use 52 bytes to point to where the card is located? (the order of
> the mem would be the order of the deck, ie the card value itself) but the
> data points to it's location (drawn, not drawn, face up, face down and in
> which column, or the ace pile) you could adjust the shuffling routine to
> shuffle the pointers into the initial deal.. (of course i may be missing
> something altogether here)
Where this falls down is in processor time. To get the top card of any
stack, you have to look through all 52 pointers and make note of the
lowest one that's in the state of that stack. But let's analyze anyway:
Well, mathematically, there are 24 (deck) plus 21 (facedown) plus 7
(stacks) plus 1 (ace pile) = 53 possible states for a card to be in, so
we could theoretically keep track of the entire game in 6 bits per card,
or 52 * 6/8 = 39 bytes. We could then cheat and use only one state for
facedown: when the player flips over a facedown card, just randomly pick
one of the cards in the state of "face down"; this would also need
counters for number of facedown cards - 4 bits each, so 3 extra bytes.
This'd compress it to 33 states for the cards, plus 3 bytes.
That's still 6 bits per card, though, so we're wasting almost half our
states, so let's use Andrew Davie's packing scheme. Andrew, stop me if I
get this wrong. We need log2 (52^33) bits for the card states, times
2*3*4*5*6*7 states for number of cards in each of the face-down piles.
log2 (52^33 *2*3*4*5*6*7) = log2 (2.1406264e60) = 200.41 bits, round up to
201 bits or 25.125 bytes. Use the rest of that last byte for a counter
indicating where in the deck the current position is, for 26 bytes. Not
too shabby.
Even here there's still room for improvement; many states are impossible.
A card can only be on an ace stack if the immediately next lower card in
it's suit is or if it's an ace; no two cards of the same value can be on a
stack, and building downward must alternate suits; only 24 cards can be in
the deck and 21 face-down. Wonder what the theoretical lower limit is;
one could enumerate all possible states of the game and pack them with the
fractional bit-encoding thing, but I'd have no idea how to go about that
enumeration.
/me grabs a pair of oars and stops drifting away from the topic
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
