Re: [stella] Thinking like a computer (harder than it sounds)

Subject: Re: [stella] Thinking like a computer (harder than it sounds)
From: slapdash@xxxxxxxxxxxx (Russ Perry Jr)
Date: Sat, 5 Jun 1999 23:21:18 -0600
Erik Mooney <emooney@xxxxxxxxxxxxxxxx> wrote:
>Ronald A. Laski, Jr. <rlaski@xxxxxxxxxxx> wrote:
>>Russ Perry Jr <slapdash@xxxxxxxxxxxx> wrote:
>> >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.

You're sort of working backwards to figure out how to process things...
In more general terms, the game itself is oriented toward the piles, not
the cards themselves.  It's much easier to run a comparison of the active
card compared to where the user is trying to put it than to have to first
figure out what the user is pointing at, then where it's going, then find
what is there.

On the other hand, a scheme like you propose may indeed be quite useful
in other situations.

>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.

Actually, at first I thought you were forgetting build pile up cards,
but those you can figure out if you search the whole deck for the lowest
value with that stack's pointer.  Ugly, though.

>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.

Hm, yeah, a bit on the tiny side...  But a wholly academic exercise here,
since there's really no NEED to compress so far.

//*================================================================++
||  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