The final, definitive, ultimate guide to the Threes! Card Draw Algorithm Yes, indeed, I have something to share with the group: The final, definitive, ultimate guide to the Threes! Card Draw Algorithm Before I delve into the spoilery stuff, I would like to thank this entire thread for input, mental challenges and general feedback. In particular, I would like to thank all those kind individuals who took the time to record games for me to analyze, namely: ★ cloudpuff ★ CzechCongo ★ LeopardGecko ★ Nicola Salmoria ★ Ryan Clark ★ Scorpion008 ★ SidetalkerWithout your help, none of this would have been possible. Despite most of this being a repeat of what has been said previously, I will refrain from pointing out what's old and what's new in favor of a concise format. Also: apologies in advance for the weird spoiler-behavior, the forum can't cope with indentation blocks inside spoiler-tags. Spoiler The cards in Threes! fall into two categories: basic cards (1, 2, 3) and bonus cards (6, 12, 24, …). The way in which these cards are drawn is quite different. I will therefore cover them separately. Basic Cards The mechanic for drawing basic cards is best described with a face-down stack of cards as one would use in card games like Mau Mau or Gin rummy. In the case of Threes! this stack is comprised of the following cards: Spoiler • 4x blue 1s • 4x red 2s • 4x white 3s As with the physical analogy, card stacks in Threes! are also shuffled upon creation. To keep with the analogy, one can imagine the cards having colored backs (to simulate the next card indicator). When a game starts, a fresh stack is created and shuffled. Then, 9 cards are drawn and placed randomly on the board. With every move the top card of the stack is drawn which reveals the next card. When the last card of a stack is drawn after a move, a new stack is instantly created and shuffled. The top card of the fresh stack is then displayed as the next card. Bonus Cards Bonus cards are managed very differently to basic cards. They only come into play when the high card (highest card on the board) reaches a certain face value. As the value of the high card increases, higher bonus cards can be drawn. The rules that governs this goes as follows: Spoiler • The lowest value bonus card is 6. • The highest value bonus card is the face value of the high card divided by 8. In the case that the value of the high card divided by 8 is less than 6, no bonus cards can be drawn. Once the high card is 48, a 6 can be drawn (48/8=6). From then on, every new rank of high card adds a new possible bonus card to the pool. It is important to note that there is only one card of every value in this pool at any time. So if the pool contains a 6, a 12 and a 24, each of them has an equal chance of 1/3 of being drawn. Once the pool of bonus cards is no longer empty (high card 48), there is a 1 in 21 chance that the next card will not come from the stack of basic cards but rather from the pool of bonus cards. Contrary to the stack of basic cards, the pool of bonus cards is immediately stocked back up after a card has been drawn from it. It is therefore possible (but very unlikely) to draw two 6s back to back. Conclusions Spoiler Apart from the obvious application of this knowledge, that is to keep track of the cards you draw to infer the current stack and predict future draws, one can draw some rules of thumb: Spoiler • If there are four 1s (or 2s) on the board without their counterpart, you will draw them within the next 8 basic cards. • More generally: if the difference between the number of 1s and 2s on the board is 4, the next 4 to 8 draws of basic cards will reduce this difference back to 0. • Using the rules from above, you can anticipate the values of bonus cards. This will come in especially handy with the next update when the next card indicator will show a '+' when the next card is a bonus card. From my point of view, this is a very well designed algorithm. It is simple yet it guarantees the necessary balance of 1s and 2s for the game to work and even if you go the extra mile and count your cards (without error), your ability to reliably predict cards beyond the next one is limited to the latter third of each stack. Bonus Content Spoiler Now that we know how the basic card stack is formed, we can calculate the number of possible stack sequences. If we had 12 different cards to put into a sequence it would be easy, 12!, but we have 4 identical cards of 3 different values. If you swap two 1s in a sequence, it doesn't make any difference. The same thing goes for 2s and 3s. We therefore need to count how many "clone sequences" there are and divide 12! by that number. Luckily, we already have the tools to do that. How many possible sequences are there of 4 1s? Well, 4!. Same answer for 2s and 3s so we get 4!*4!*4! "clone sequences" for a full stack. The answer to the topic question is then: Spoiler 12!/(4!*4!*4!) = 34,650 And in a flash of divine providence, this number is divisible by three. Edit: Hello reddit!
Very nice, kamikaze! Attach your appendices and submit to the iOS thesis committee to collect your degree. Spoiler So, the drawing of bonus cards from their own separate stack doesn't change the regular stack? I.e., if I'm counting cards and get a bonus card, I can resume counting my 12-card stack with confidence, new bonus cards notwithstanding? Also, does your "you'll draw enough cards to even out the 1s/2s within 8 cards" rule hold if bonus cards are included?
Point me to the submission page and I'd be happy to. Spoiler Yes, exactly. Spoiler To be technically correct: no, it does not. However, the chance for the worst case (needing 8 cards) is already slim and the chance for the "even worse" case of more than 8 cards (with bonus cards) is even slimmer. I corrected my wording to be technically correct, but for practical appliance it really does not matter. I wonder if Eli Hodapp will link to my guide and forget to add my name again. (Last paragraph, "[...] TouchArcade forum member is making ridiculous headway […]")
Nicola, Your work is absolutely amazing. I am particularly interested in this AI behavior that you described. This is because this is a strategy that I would heavily employ under the right circumstances. Often, if I can temporarily afford to loose 3 or even 4 spaces, I would defer merging some cards to better align them for later merging as a batch. The goal of these steps are not to just get rid of them in batches but to better align the remaining cards. One risk that you did not describe (though I suspect your AI is already doing) is that you may get a 1 or 2 card during these critical steps and found yourself getting trapped by "staggering" (getting a small card stuck between two big cards). I would go even one step further by saying that your AI is just not employing any "center" or "corner" strategy. This configuration is just naturally occurring when you allow the maximum freedom of the movement of the big cards. This is in line also with what I do in my run. I don't practice so-called "corner" strategy because it sets a mindset of not willing to move the big cards away from the "corner" (or bottom or whatever wall that is designated). In consequence, you loose one or two degrees of freedom and can miss some setups such as the one you described.
And it's live : Nicolas Salmoria'AI has the honours of TA frontpage http://toucharcade.com/2014/02/20/mame-developer-builds-threes-ai/
The interesting thing is that the current version of the AI only considers the next card, and then does a lookahead of 3 more moves assuming that no more cards are added to the board. So it is completely oblivious to the risk of staggering, and yet that's enough to: - reach a 768 in 75% of the simulated games; - score more than 27,000 points in 50% of the games; - score more than 80,000 points in about 1% of the games. So the potential for further improvement, by also taking into account the card drawing algorithm, is scary. I'm not sure if I want to see how far it can go
I'd say that now what remains to be verified is whether the insertion line of the new cards is purely random or there is some sort of bias. This is something that I could easily log while my AI is playing a game. I'll probably wait for the "+" update to be available, though.
I agree but I still consider my work on the card draw algorithm to be complete. The question you're asking refers to the "card placement algorithm" (if there is one, because I'm still suspecting a random placement among the possible spaces).
I'm surprised no one did! I remember seeing it mentioned in the comments of the article, but that's about it.
Here's a thought about that: Spoiler Track the state of the basic card stack and use it to determine when it is beneficial to do deeper lookaheads and how to weigh the subsequent game states by their probability of occurring. When only 4-8 cards remain in the stack it might be good to look ahead until the stack is empty. A fresh stack is relatively unpredictable, so your usual lookahead-strategy should suffice. I want to see this thing go to 6144.
Some of the work you guys have done is just.. Well... Awesome! Here's some cake (of you are on the app that is) ###
Wow, wow, wow, wow, wow. Simply amazing. So Kamikaze, I assume your theory fits all the data perfectly? Are you going to work on placement next? And Nicola Salmoria, I challenge you to get a 6144 with your program! You can do it!
Except when there are logging errors in the sequences, yes. The algorithm I described earlier explains everything I observed in the 100+ sequences I now have. That's a bit more difficult than the card draw algorithm and requires a much more complicated way of logging. We'll see
Seeing the devs are seeing this, just thought I'd extend some fuzzies of my own. The gameplay's enthrallinfuriating enough, but the card personalities are truly wonderful.
