Subject: Re: [stella] Thinking like a computer (harder than it sounds) From: slapdash@xxxxxxxxxxxx (Russ Perry Jr) Date: Mon, 31 May 1999 15:17:49 -0600 |
"Andrew Davie" <adavie@xxxxxxxxxxxxxxxxx> >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. Andrew is right, but one thing that should be pointed out is that this memory efficiency can come at the price of execution speed. I haven't programmed anything for the 2600 yet myself, but I think I can safely say that that's the "fun" of programming it -- memory vs speed. You gotta be tight on both! >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. Of course, Andrew doesn't have a perfect example to counter, as the mild packing I describe only takes 39 bytes for the deck, not much of a savings here. But perhaps it would do good to explain why... A card requires two bits of information to identify -- suit, and value. There are four suits, and we can encode them in 2 bits, with NO waste. There are 13 values, which we can encode in 4 bits, wasting 3 states. This is a "small" amount of waste (3 of 16); if we had 9 values, we'd waste 7 states (using 9 of 16). If our first identifier also had waste, combining the two would very likely add to our savings... >Other information can be added (and retrieved) in a similar bit-packing >fashion. It does work, though it looks strange. And implementation time required increases. >I think I just saved uh.... 15 bits ;) This is why this particular example isn't a good one to make Andrew's case. On the other hand, if you look at my UNcompressed scheme below, there are greater savings yet. The beauty of it is, with Solitaire we don't really NEED to worry about savings because with just the simple tricks that Erik brought up (the ace piles and build piles, up and down cards) save enough memory that we don't need to do much more, and can save cycles on the implementation by not having to unpack the card values. >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). Absolutely true... If we had 3 values to store, two with three states each and one with 7 states, each would require 2 bits, 2 bits and 3 bits respectively, or 7 bits total. But there are only 3x3x7 = 63 possible combinations, which we can store in 6 bits, wasting only 1 state (not 1 state per value). With 10 items, we've only saved 10 bits with mild compression, or 20 if we just went with a byte per item. BUT if we need to keep 100, the 100 (or 200) bits of savings really starts to add up. >Retrieval and modification of values is somewhat more difficult, but if >memory is tight, this is the way to go. Right, it may in fact be the only solution... And most packing routines should be somewhat generalizable and therefore reuseable. >I'd really advise a close reading of my posting from way-back. Well, right now, I'd say get coding Solitaire and/or Columns so a) we have a new game(s) and b) you get some 2600 coding that isn't too complicated, but then go back and read Andrew's post for your next game, which will undoubtedly require more memory because it'll be bigger and better. :-) //*================================================================++ || 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/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] Thinking like a comput, Andrew Davie | Thread | Re: [stella] Thinking... [nearly ot, Colin_Hughes |
[stella] Toner Supplies, art333 | Date | [stella] A question regarding games, Pete Holland |
Month |