How can I resist?!
Some time ago, I wrote about fractional bit resolution for storing values.
This method is rather applicable here, and I'd refer everyone back to my
earlier posting (about a year ago). Basically, it is quite possible (and
extremely efficient memory-wise) to store ranges of values in non-integer
bit widths.
Storing 52 cards (excluding joker) would require just 5.7005 (approx) bits
per card, or 296.43 bits (approx) to store an entire deck (randomly, with
every card uniquely identified). Each card identified by a unique number.
That is, each card requires log(2)52 bits of information, and there are 52
cards. That's just a tad over 37 bytes (37.052) to store the whole deck.
Other information can be added (and retrieved) in a similar bit-packing
fashion. It does work, though it looks strange.
I think I just saved uh.... 15 bits ;)
Russ has a good solution for this particular problem, but fractional bit
storage is good for ANY data you want to stor; you are guaranteed NO wasted
or unused bits, other than the ones not used on the very end of the last
byte (which, of course, you can use for other purposes). Retrieval and
modification of values is somewhat more difficult, but if memory is tight,
this is the way to go.
I'd really advise a close reading of my posting from way-back.
Cheers
A
----- Original Message -----
From: Russ Perry Jr <slapdash@xxxxxxxxxxxx>
To: <stella@xxxxxxxxxxx>
Sent: Monday, 31 May, 1999 5:35 AM
Subject: Re: [stella] Thinking like a computer (harder than it sounds)
> Pete Holland <petehollandjr@xxxxxxxxx> wrote:
> >The computer needs to keep track of, among other things, what all the
> >cards are in the deck of cards, the discard deck, the four stacks you
> >start with the aces, and the seven stacks you start the game with.
> >Take the last stack, the one with seven cards, one up, six down at the
> >start. I'm thinking I'll need a pair of memory cells for each card,
> >one to tell the denomination, the other to tell what suit it is.
>
> Erik Mooney gave some good advice, some things that hadn't occurred
> even to me, but I'm not sure I followed his math...
>
> So, here's a scheme that I THINK only uses 69 bytes -- it's a little
> wasteful, but doesn't require much "dynamic" adjustment. If you're a
> little more wasteful you can still do it in 85 bytes...
>
> Basically, since there are only four suits, you only need two bits
> to represent them. Example:
>
> 00 = hearts
> 01 = diamonds
> 10 = clubs
> 11 = spades
>
> Note that the first bit gives you the color, which might come in handy
> later.
>
> You've only got 13 cards per suit, so there's another four bits you need:
>
> 0001 = Ace
> 0010 = 2
> ...
> 1001 = 9
> 1010 = 10
> 1100 = Jack
> 1101 = Queen
> 1110 = King
>
> Each card is in the form SSNNNN (suit, number), which requires only
> 6 bits per card to uniquely identify it.
>
> Note that I've done some weird things here as far as the encoding...
> But, this way, you know a card is a face card if the first two bits
> are both 1s, and the number cards have values which are the actual
> numeric values. (Hmm, actually, this would work better for black-
> jack, wouldn't it?).
>
> So, we've wasted 3 combos (0000, 1011 and 1111 -- but we can use
> these later), and we've wasted two bits out of each byte (if we
> don't waste them we move from 85 bytes required down to 69), but
> we're far ahead of using two bytes per card!
>
> Now it comes to how to use the shortened space... (Erik gave some
> GREAT ideas about unseen cards).
>
> First, though it's a little wasteful, why not start out by writing
> the whole deck into memory randomly so we have a shuffled deck?
> The good thing is, this preserves the shuffled order for later.
> This uses either 52 bytes, or if we compress via the scheme below
> only 39 bytes:
>
> As we only need 6 bits of every byte, we can overlap the cards in
> memory, every four cards in three bytes:
>
> AAAAAABB BBBBCCCC CCDDDDDD EEEEEEFF FFFFGGGG GGHHHHHH
> IIIIIIJJ JJJJKKKK KKLLLLLL MMMMMMNN NNNNOOOO OOPPPPPP
> QQQQQQRR RRRRSSSS SSTTTTTT UUUUUUVV VVVVWWWW WWXXXXXX
> YYYYYYZZ ZZZZaaaa aabbbbbb ccccccdd ddddeeee eeffffff
> gggggghh hhhhiiii iijjjjjj kkkkkkll llllmmmm mmnnnnnn
> oooooopp ppppqqqq qqrrrrrr sssssstt ttttuuuu uuvvvvvv
> wwwwwwxx xxxxyyyy yyzzzzzz
>
> Once we've actually used a card from the pile, write back a 000000
> to indicate an empty spot (i.e. no card). (If we're wasting space
> we can use the leading bit to indicate card or no card, so we'd
> write 11001110 for the King of Hearts (KH) and 00000000 for an
> empty slot). We can skip these spots when going through the deck.
> If need be, you could compress the deck later on to save traversal
> time with a low number of cards in the deck, but it's probably
> unnecessary.
>
> Similarly, we need to keep 4 bytes for the ace piles, and
> we can comress this into 3 bytes if we desire:
>
> HHHHHHCC CCCCDDDD DDSSSSSS
>
> Actually, we can compress this to 2 bytes if you need the extra
> by merely making each pile in order represent a particular suit
> to begin with:
>
> (HH CC DD SS)
> HHHHCCCC DDDDSSSS
>
> Remember, this takes advantage of the fact that you ONLY have to
> keep track of the top card in each pile (or a 000000 if it's still
> empty) -- the cards below are out of play, and if you put in a
> cheat that allows the user to put the top card back into play, you
> KNOW what the card underneath it will be, so you don't have to
> store it.
>
> For the build piles, Erik pointed out that you can draw these out
> randomly from the deck at the point they are uncovered, instead of
> actually tracking them all along... This is sound thinking. Once
> they're drawn out of the deck, they're replaced by a 000000 there
> anyway, so they don't screw up the draw order.
>
> Now, we still need to keep track of the up cards... Another trick
> Erik mentioned was that we only need to keep track of the SUITS of
> the cards underneath the top. So, we need 7 bytes for the top
> cards if we waste space (only 6 bytes if we don't), and a further
> 21 bytes (as I'll describe below) for the rest of the up cards.
> The seven build piles are:
>
> 11111122 22223333 33444444 55555566 66667777 77XXXXXXX
>
> The Xs show that we've again wasted some space, but in truth, we're
> going to be using that somehow anyway. I would either use that
> space (or another byte in the uncompressed scheme) to be a pointer
> into the deck to indicate the card on top (if XXXXXX = 000000, there
> are no more cards in the draw pile and no more build pile down cards,
> so you can stop going through the deck anymore).
>
> Now, as to the up cards below the top... The largest a stack can ever
> be is 13 cards, and since we're already tracking the top card separately,
> we only need to store 12 suits underneath. Though it's more wasteful
> than doing this dynamically, let's just use 3 bytes for each stack.
> We go in order and terminate with a duplicated suit, or for a max stack,
> when we're at the end of those 3 bytes.
>
> For instance, if our stack was 7C, 6H, 5S, 4D, we have 010100 in the
> build pile top card array above, and an associated list of 11001010
> (that's SHCC, the CC -- clubs duplicated -- means you're at the bottom
> up card).
>
> The maximum stack KH, QS, JD, 10C, 9H, 8C, 7D, 6S, 5D, 4C, 3H, 2C, AH
> has 000001 in the build pile top card array, and a suit list of:
>
> 00110110 00100111 01100010
>
> If you put the ace on the ace pile, then it must be adjusted to have
> 100010 in the build pile top card array, and a suit list of:
>
> 00110110 00100111 01100000
>
> In this case, we've duplicated the 3H suit so we know that the list
> ends there. Let's say we now add the AD to the 2C. We change the
> top card to 100001 and we traverse our suit list until we come across
> the duplicated value and write the 2C back there (from the top card
> position) to give us:
>
> 00110110 00100111 01100010
>
> This assumes we've checked that it's a valid move first, of course...
>
> So, our byte counts are:
>
> wasteful compressed
> draw pile 52 39
> ace piles 4 3
> build piles 7 + 21 + 1 6 + 21
> ---------- ----------
> total bytes 85 69
>
> Not too bad, eh?
>
> I think either scheme gives plenty of room for other variables and
> a stack if we need it... Plus, all of our memory used in these
> schemes is static, so there's no need to waste cycles updating it
> dynamically.
>
> >That's the problem for Solitaire, and it gets more complicated
> >with a game like Columns. To make a long idea short, I am envisioning
> >a series of 208 registers, two spots for each square in the 8 by 13
> >well. One of the pair would tell if there is a jewel there, the other
> >will denote it's color.
>
> Won't go into much detail here, but as Erik pointed out, there's no
> need to waste memory to have a separate flag that a spot is empty --
> use a 0 color value to indicate there' no jewel there. How many colors
> are there in Columns anyway? If there are only 6, plus the flashing
> jewels, you can encode like this:
>
> 000 - empty
> 001 - blue
> 010 - red
> 011 - green
> 100 - yellow
> 101 - white
> 110 - purple
> 111 - flash
>
> You MAY have to go to 4 bits if you use more colors, but that's still
> two jewels per byte, so for a well of 8x13, we can do it in 104 spots =
> 52 bytes, or if 6x13 the way others have recollected, 78 spots = 39
> bytes; if you can encode the colors in 3 bits, you can compress further,
> similarly to the cards above, only this time 8 spots into 3 bytes, so
> our counts above would be 8x13 in 39 bytes, or 6x13 in <30 bytes:
>
> AAABBBCC CDDDEEEF FFGGGHHH
> ...
>
> (Hmm, 8 spots in three bytes... that's a 3 x 13 byte array, which makes
> bookkeeping mildly easy for the 8-spot-wide well; with 4-bit color, it
> doesn't matter if it's 6 or 8 spots wide, we can make a nice N x 13 array
> no matter what).
>
> Note that you'd keep track of the falling piece separately; this scheme
> only covers what's static in the well. Since the flashing jewels
basically
> take out colors as a "wild card", you probably don't need to encode the
> flash state in the scheme above, giving you an extra color if you need it.
> (To be more clear, the flash picks a color around it randomly when it
> stops, and at THAT point would have a real color value rather than the
> flash state).
>
> >Since the idea is to match the colors in three in a row or more, all I
> >can imagine is the computer comparing each individual square in each of
> >four directions by it (Starting with the left jewel on the row, it would
> >move right, comparing the jewel on the immediate right, right-down, down,
> >and down-left.) If it registers a match, it will check the next one in
> >that line to see if there are three of more in a row.
> > This has me concerned that it will slow the computer down as it
> >checks all the jewels.
>
> Yeah, that could be a slight bugger, though when a piece stops falling,
> at first you ONLY have to check (in eight directions) all the spots around
> it, not the whole board, as Erik also mentioned (though after that you do
> need to update it all; er, not quite... see below).
>
> >I'm also wondering how I would get the computer to keep it's directions
> >straight ("No, no! Go to the next in line, don't change direction!")
>
> This shouldn't be TOO hard...
>
> >and how it would tell what spots had matching jewels that need to be
> >removed.
>
> This is a little tougher... I think you'd make a list (on the stack)
> of all locations that need to be removed, and perhaps a second list of
> jewels left hanging (again by location). Start at the dropped piece's
> top jewel, and look up two locations (since if there were three, they'd
> be gone by now; also this is a trivial case, since we know there can't
> be anything above the top of the dropped piece, but it makes things
> easier later). If the second and first, or just first, match the dropped
> color, you'll need to note that and keep looking for more jewels of the
> same color; if the count is right, add them to the list of jewels to be
> deleted. Do this for upper-left, left, and lower-left; then repeat for
> the middle and bottom jewels in the dropped piece. Then erase all the
> pieces on the list (i.e. change their color values to 000 for empty).
>
> If you made a list of pieces left hanging, you can know drop all of
> these now and then do the "dropped piece" check for each of them. In
> this way you might not have to check the entire board -- it'll save
> some time when there are few pieces stranded, but it will possibly
> take MORE time with the list keeping when a lot of pieces are stranded.
>
> >I can't just blank those memory locations, because the scoring is
> >different if six jewels are removed (two sets of three) or six jewels
> >are removed (six of the same color).
>
> I think the scheme above let's you account for this, though I'm not
> giving much help as far as an actual implementation goes...
>
> >Of course, once those are removed, it checks for matches once the
> >jewels fall to fill in the holes.
>
> As above.
>
> >I'm having trouble seeing how to make this work for the Atari without
> >slowing it down, screwing up the count, whatever.
>
> Well, screwing up the count is a bug, slowing it down is a design issue.
> Slightly different issues.
>
> >Is this the best, most efficient way to do it?
>
> Well, most efficient isn't ALWAYS the best, since if the efficient route
> uses too much RAM, it'll never be best.
>
> >If not, what is?
>
> I don't know if we've come up with a really good way to do it yet or not,
> but you've got some more hints. Any more questions?
>
> file://*================================================================++
> || Russ Perry Jr 2175 S Tonne Dr #105 Arlington Hts IL 60005 ||
> || 847-952-9729 slapdash@xxxxxxxxxxxx VIDEOGAME COLLECTOR! ||
> ++================================================================*//
>
>
>
> --
> Archives (includes files) at http://www.biglist.com/lists/stella/archives/
> Unsub & more at http://www.biglist.com/lists/stella/
>
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
