I would like to propose a step 2. It consists of the following: "Hey Asher or Greg, is the choice of insertion row/col truly random?" Admittedly this takes all the fun out of it. As a developer, I don't see any obvious reason or mechanism by which the choice should be non-random. However, I would have also said the same thing about the overall card sequence; there are simple non-stack-based (and thus non-countable) ways to generate cards that have practically the same statistical properties and distribution. E.g. based on the current board position, choose the next tile as: 64% colored (1 or 2, weighted as below) 32% '3' 4% bonus (randomly chosen from 6, 12, 24, .., high-card / 8, with equal weighting) where the choice of 1 or 2 (in the 64% case) is weighted by the current "color balance", defined as red cards minus blue cards on the board. In other words (and the exact numbers for +-2 and +-1 are guesses): +4: 100% blue +3: 90.0% blue, 10.0% red +2: 75% blue, 25% red +1: 62.5% blue, 37.5% red 0: 50% blue, 50% red -1: 37.5% blue, 62.5% red -2: 25% blue, 75% red -3: 10.0% blue, 90.0% red -4: 100% red Nicola, you could add a counter to your bot to see if these probabilities reflect the actual game. It can also be calculated analytically: there are only 70 (8 choose 4) distinct sequences into which 4 red and 4 blue tiles can be mixed in a stack. Solving explicitly for the +3 case, there are only 8 (equally likely) color sequences within a stack that can generate a red balance of +3: RRRRBBBB (+3 count happens twice) RRRBRBBB (+3 count happens twice) RRRBBRBB RRRBBBRB RRRBBBBR RRBRRBBB RBRRRBBB BRRRRBBB In the 10 individual cases where a +3 count is reached, only once does it proceed to +4. Therefore, if you see a count of +3 on the board, in absence of any other information, there is exactly a 1/10 chance that the next colored card will be red. (If you're counting cards in the stack-based game, you will be able to further distinguish this into 0% and 20% cases, depending whether you've already seen all 4 red cards or not.)
Jumping into the +2 case, there are three basic ways to reach a count of +2: 2 cards into stack: [RR][RRBBBB] // 15 possible sequences 4 cards into stack: [RRRB][RBBB] // 4 * 4 = 16 possible sequences 6 cards into stack: [RRRRBB][BB] // 15 possible sequences With a +2 count 2 cards in, there is a 5/15 chance the next card will be red. With a +2 count 4 cards in, there is a 4/16 chance the next card will be red. With a +2 count 6 cards in, there is a 0/15 chance the next card will be red. So the probability of getting a red card on a +2 count is: (5 + 4 + 0) / (15 + 16 + 15) = 9 / 46 = 19.57%. (as opposed to the 25% I guessed in the previous post.) Analyzing the +1 case, there are 4 basic ways to reach a count of +1: 1 card into stack: [R][RRRBBBB] // 35 sequences 3 cards into stack: [RRB][RRBBB] // 3 * 10 = 30 sequences 5 cards into stack: [RRRBB][RBB] // 10 * 3 = 30 sequences 7 cards into stack: [RRRRBBB] // 35 sequences And the respective probabilities of getting a red card next are: 15/35, 12/30, 10/30, 0/35 so (15 + 12 + 10 + 0) / (35 + 30 + 30 + 35) = 37 / 130 = 28.46%. (as opposed to my guess of 37.5%.) Analyzing across the +1, +2, +3 cases: +3: 10 ways, 1/10 chance of going to +4 +2: 46 ways, 9/46 chance of going to +3 +1: 130 ways, 37/130 chance of going to +2 (1 + 9 + 37) / (10 + 46 + 130) = 47 / 186 = 25.27%. What this means is that if the board is "red", then the next color card is 74.73% likely to be blue. Let's hear it for combinatorics
Nicola, I just thought of another test you could do, just to see how it may work if approached like many average players would do (would be interesting if somehow you got much higher results). Run it without all the computer advantages. That is, skip your calculations for open blocks, matching blocks, etc. Run it the following ways: 1. Random moves with no consideration for what might be the best move. 2. Have it always choose to combine blocks, if that is possible - priority given to multiple matches over single matches and if only single matches are possible, opt for the one with the largest score. I think that second one would be how many people would at least start out playing (not looking multiple moves ahead) or for people just playing quickly. Theoretically, the scores shouldn't be anything particularly good. But what if you do get higher scores? I think most people in such a situation would be mostly limited to 384. Well, that's my best card. Could be revealing of something if the computer does much better anyway - don't know what.
Here is my personal high score, which I have now maddeningly achieved exactly twice. I'm stuck in a thrut!
Yeah, that's kind of the boring course of action. I thought of an easy notation that might reveal a hidden bias. My main concern was that there are 3 distinct, interesting scenarios that need to be covered: 2, 3 or 4 possible rows/columns of insertion. A robust notation has to cover all of them and allow for individual analysis of these cases. I came up with the following, inspired by y2kmp3's earlier attempt: 1. After you've decided on a move, drag slowly to see exactly which rows/columns move in order to determine the number of possible spawning locations along the wall. 2. Note this number. 3. Rank the possible spawning locations from desired (1) to least desired (number you noted in step #2). 4. Do the move and note your ranking from step #3 of the actual spawning space. Separate this value with a comma (,) from the number of possibilities. Add a line break and start over.Here's an example to illustrate this method: Code: __ 3 2 2 __ 3 6 12 3 3 24 1 3 1 24 48 Next: blue. I decided to slide down and all but the rightmost column will allow a new card to sawn. I note Code: 3, Now, the best case for me would be if the 1 spawned next to the left 2 in the top row (my 1st choice). Left of my 1st choice would be my 2nd choice and the left corner of the top row would be my 3rd choice. Now I move down and the board looks like this: Code: 1 __ __ 2 __ 3 2 12 __ 6 6 1 6 1 48 48 My 3rd choice happened, I note: Code: 3,3 Now I'm ready to note my next event. Note that in contrast to our previous project, you do not have to log an entire game this time. Only if you reach a situation where you can make a clear list of preference for the possible spawn spaces (however minute the difference in your preference for certain choices might be) would you need to write 2 numbers separated by comma (,). My thinking for this kind of experiment goes as follows: Hypothesis #1: If the selection among the candidates is random, the average preference of each case should converge towards their average, like (1+2+3)/3=2 Hypothesis #2: Conversely, if there is a bias towards/against the player, there will be a statistically significant diversion from the average. The choice of which event to log should not skew the results if Hypothesis #1 is true and it should only exaggerate the results should Hypothesis #2 be correct.It is of vital importance, however, that nobody discards any logged events just because they did not fit their preconceptions. Once again, send me your results via PM. You might think so and while your balance of blue to red cards would probably work, there is a flaw with your allocation of white cards. Your purely probabilistic algorithm would scatter white cards around an average of 32%. You could have six 3s in 12 cards or just 2. Similarly, you could have a very long sequence or blue and red cards (balanced, but still possibly overwhelming). Not seeing these events is one of the strongest argument for the undrawn stack algorithm.
The stack algorithm can already yield 16 blue/red cards in a row or 8 white cards in a row (more if you count bonus cards). It very rarely does this of course (about one in 350,000 two-stack sequences will have either 16 blue/red or 8 white in a row), but it's possible. The pure random algorithm would yield these longer streaks more often of course, an inevitable consequence of having an IID memory-less algorithm, but it's still pretty rare: about 1 / 1300 to get 16 colored cards in a row. (A game to 768 takes about 320 moves I think, so you'd get a streak like this every 4 games or so.) On the other hand, the algorithm could still be tuned based on what's on the board, with a higher probability of a 3 if more colored cards are on the board or vice versa, and still be memory-less and thus not countable. I wonder if most historical Tetris implementations have been purely random, or whether any of them enforced a more even distribution? In the early days of iTunes, Apple was criticized for its shuffle algorithm being "not random enough", so they had to add measures to even out the distribution of songs. It's funny how the perception and reality of randomness are often quite different.
Amen. Another amazing quote which goes in a similar direction: This is from the book "Thinking, Fast and Slow" that I mentioned earlier. Back to topic: By showing how much tuning and fiddling you have to do with a probabilistic, memoryless algorithm you're nicely demonstrating the Okkam's Razor argument for the stack algorithm.
Shouldn't we test which position the new card "spawns" at from an objective point of view too? Perhaps there is a bias towards one corner of the board.
By mere coincidence, I stumbled upon a video by 148apps with both aeiowu and AsherVo giving live comments: http://www.youtube.com/watch?v=rhdbsNOwUNU At 14:00 aeiowu basically confirms the "spawn space is chosen at random from candidates"-theory. Or he was lying. Edit: The coincidences continue with Veritasium just posting a video relevant to our endeavor: http://www.youtube.com/watch?v=vKA4w2O61Xo
Is there anything left to do then? Also, can the incredible AI ever get 6144's and higher consistently or it at it's peak, given the randomness and time needed to do the lookaheads?
And here are the results over 100 simulations. 384: 100% 768: 99% (was 98%) 1536: 80% (was 67%) 3072: 20% (was 10%) 6144: 2% (was 0%) median score = 87,030 max score = 622,722 so adding one lookahead step effectively doubled the ability to reach the 3072 card.
Well, first of all, we haven't answered the question about the minimum number of cards yet. Everybody suspects 7 to be correct but nobody was able to prove it. Then there is an endless possibility of fan-projects like Kickstarting plushy-versions of all 12 characters or fridge magnets or And lastly: as long as you can't get a 6144 and all the hidden achievements legitimately you are not finished with the game yet. I can't remember how many lookaheads he's doing right now (I think 2 with with new cards and 2 without) but at some point the exponential effort to compute an additional lookahead will outweigh its usefulness.
With purely random moves, over 100,000 attempts: Never went above 192, and reached 192 only 15 times. The median score was just 228, with max card 24. It also got exactly 1 ThreeLock, which is kind of interesting. So making random moves is definitely not a good strategy Right, I didn't have time to try this. Just removing the lookahead, and changing the scoring to only reward empty spaces (thus favoring merging), over 100,000 attempts: Never went above 384, and reached 384 only 11 times. Median score 420, with max card 48.
Nicola, are you taking requests? Try having it slide in one direction repeatedly until it can't, then repeatedly with the next direction clockwise (i.e. start sliding up, when up doesnt work slide right, etc.).
Well, no obvious surprises then, Nicola. So that would seem to confirm your simulation is accurate. Thanks for the effort.
If you have time Nicola I really think this would prove once and for all how insane your AI is. Do one of the most intense versions of you algorithm and play out the choices on a board. Unless you wanted to wait until the + card update that is.
Hello everybody, I've been following the thread for over a week... really awesome work here. Kamikaze28's work to uncover the pattern of card drawing, Nicola's algorithm, AsherVo's visit to the thread... well, very nice. I have been developing my own algorithm to play Threes!, but my attempt is dwarfed by Nicola's I have to congratulate Nicola's achievements with the program. What he does might look easy, specially by the way he describes it, but it isn't. So... I have a couple of questions. I check the leaderboards and see outrageous scores: the first six have scores of 99 million. I also see that Scorpion_008 has 44M, is it the same Scorpion008 that is in this thread? There must be some cheaters in the list If there are cheater's, why not delete them? This is just in case AsherVo is reading A few months back Apple introduced the section "Manage Scores and Players" where developers can delete scores and ban players. And this brings the questions... 1) What is the maximum card? 6144? In the High Card leaderboard I see people with high cards like 98304, 49152, 24576, 12288! In the achievement's table there is only space for up to the 6144 card. Is the 12288 card possible to achieve? 2) There must be a limit to the maximum card achievable, isn't it? What is it? 3) And what is the maximum score possible?
