Another improvement:
[id="split-FCC-improvement"]
Update: The split-FCC improvement
----------------------------------
First of all see
link:split-fully-connected-components-based-solver-planning.asciidoc[the split
fully connect components ("FCC") spec]. Thereby we keep a fingerprint of the
game state using 52 enums of three states (= { ORIG_POS = 0,
ABOVE_PARENT_CARD_OR_EMPTY_SPACE = 1, IN_FOUNDATIONS = 2 } ) each.
Now, if card is at ORIG_POS or IN_FOUNDATIONS then its deBondt encoding is
already known. If it is at ABOVE_PARENT_CARD_OR_EMPTY_SPACE then it can be of 4
different states:
1. In a Freecell.
2. The lowest card of the stack.
3. On a parent of either Hearts or Clubs.
4. On a parent of either Diamonds or Spades.
So we need at most 2 bits for each card, so 52*2 = 104 bits and 13 octets.
We can improve on that by noting that a King card is only at #1 or #2 (thus
requiring only one bit) while an Ace card requires 0 bits due to
https://groups.yahoo.com/neo/groups/fc-solve-discuss/conversations/messages/1300[Horne
automove] so we can shave off 8 + 4 bits for a total of 92 bits or 11½ octets.
One option would be to pack two such encodings into three consecutive 64-bit
quadwords.
One can notice that we can merge/unify option 1 and option 2 because we can
determine if there are any cards on top of the card based on the other cards,
and, as a result, king cards degenerate to zero bits as well.
So we get:
log2(3)*(52-4-4) = log2(3) * 44 = 69.7383500317309 bits (bytes: 9)
Moreover note that for the cards of rank 2, there is only one optimal
option which we can infer from the rest of the cards, so they can degenerate
to 0 bits each:
log2(3)*(52-4-4-4) = log2(3) * 40 = 63.3985000288463 bits (bytes: 8)
Which fits inside a 64-bit machine word.
*Correction*: one edge case for merging the in-the-freecells / bottommost-card
cases is when all the stacks and all the freecells are occupied and there is
more than one 1-card sequence. In this case we need to multiply by
https://en.wikipedia.org/wiki/Combination options where the k is the number
of freecells and n is the total number of 1-card sequences.
Back to the thought process, one can notice that if 3♥ is on 4♣ then
3♦ cannot also be on 4♣. So, for the two 3♥/3♦ cards we have these options:
.Colour Pair Configs
|===
|Opt Index|3♥|3♦
|0
|Parentless
|Parentless
|1
|Parentless
|On 4♣
|2
|Parentless
|On 4♠
|3
|On 4♣
|Parentless
|4
|On 4♠
|Parentless
|5
|On 4♣
|On 4♠
|6
|On 4♠
|On 4♣
|===
For a total of 7 states instead of 9.
So we get:
log2(7)*((52-4-4-4)/2) = log2(7) * 20 = 56.1470984411521 bits (bytes: 8)
This may need to be multiplied by the Combinations number mentioned above.
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
http://is.gd/i5eMQd - Emma Watson’s Interview for a Software Dev Job
*Chuck*: Indeed. Anyway, I invited a friend who is even crazier than I am.
*Kermit*: Really, who is this crazy guy?
*Chuck*: Actually, it’s a crazy girl.
— http://is.gd/htmOCv
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Fri Apr 12 2019 - 04:06:46 IDT