They are counterexamples of the statements you proposed as theorems. They respect the requirements of your statements, so the theorems are wrong. I'm not saying that the end result isn't true (that is, that under certain conditions it is not possible to have less than 7 cards on the board), but there is too much hand waving in the proofs.
The point of our "legal starting state" is to handle the exception I mentioned earlier where a lucky starting state would allow a lower minimum than 7, as you demonstrate quite clearly. When you add the legal starting state to each theorem individually, they still hold. I just didn't want to start everything with "Given a legal starting state defined by the following conditions: ". I agree however on the amount of hand waving in the proofs. I think with the Zeroes!-relaxation we have a nice tool to work with and I'm sure we'll find a better, more elegant and less hand-wavey proof in time.
It's easy to prove that if there are no empty lines, you can't go down to 5 cards. There are three ways to reduce to 5 cards: 1) Start with 8 cards and make 4 merges. But that would mean having all the 8 cards in two lines, and leaving two empty lines. 2) Start with 7 cards and make 3 merges. But that would mean having 6 cards in 2 lines, and only 1 more card to cover two more lines. So you'd leave at least one empty line. 4) Start with 6 cards and make 2 merges. This means having 2 pairs of 2 cards on 2 lines, and covering the remaining 2 lines with the other 2 cards, which necessarily have to be singletons, in a configuration like this one: Code: 3 3 - - 3 3 - - - - 3 - - - - 3 But what could be the position before this one? The four cards that are going to be merged cannot be new cards, because they are in pairs both horizontally and vertically: if they were new cards, they would have to be the only card in a row or column. But the other 2 cards cannot be new cards either, because they are singletons: before adding them, at least their row or their column would have been empty, so the previous position would have had an empty line. So 6 is the minimum, and you have already shown a starting position that would lead to that result. I don't think that would be possible at any moment in the game, so the question is which property needs to hold to make it impossible to go below 7. Also, I'd like to point out that this all started from mclifford82 posting a screenshot of a good position (http://i.imgur.com/agYpmL4.jpg) and CzechCongo congratulating for getting down to 7. But that position actually only goes down to 8 (11-4+1). So it's still open to debate whether even 7 is actually achievable later in the game.
That might be true. What needs to formally be proven, then, is that in order to form a singleton by merging, at least one of the cards being merged had to be a singleton in a previous position. Otherwise, the mere fact that my counterexample has only 8 cards doesn't mean anything: we know that it's possible to go down to 8 cards from the initial 9. I see that you edited your post to actually add these starting state conditions. They weren't there when I replied to it. However you are also saying This is actually possible, as shown in the counterexample that BenW posted. You could add even one more card.
Okay, let me try. I will do this in Zeroes! for simplicity. First, I argue that neither of the merging cards can be lonely (what you call a singleton) because they are neighbors to each other since they can be merged. In order for a singleton to form after this merge, these two cards need to be lonely except for their merging partner, that is to say they both only have the other card in their neighborhood. It follows that there must be 2 rows and 1 column (or vice versa) empty except for these merging cards. This occupies 10 spaces on the board leaving only 6 to place other cards. Such a position is prohibited by C3 (exactly 9 cards on the board). Edit: Shoot, I misunderstood your post and proved something completely different. I noticed that while you were replying and edited both of my proofs to add the "no lonely card" condition back in.
Going back to the automated player that I've been working on, I made some improvements to the position scoring, and improved the lookahead to check all possible (non-bonus) cards being added in the next 2 moves, instead of just leaving the space empty, then do 2 more moves of lookahead leaving the space empty (this is a compromise to keep speed acceptable so I can still run at least 100 rounds of simulation). With these changes, the performance increased significantly, and the algorithm started being able to reach the 3072 card: 384: 100% 768: 98% 1536: 62% 3072: 13% median score = 71,050 I expect that adding card counting to account for the card drawing behaviour should improve this even further.
the computer achieves 100% of the time the 384 card, which is the best I can do. I feel dumb and mostly too impatient, playing too fast I reckon.
I think this is already proven. In Zeroes! I already showed that the neighborhood of any card cannot decrease in size. Since every card has a non-empty neighborhood in a legal starting state (C2) you cannot form a singleton. Don't feel dumb. Computers can solve Sudokus, Rubik's Cubes and similar puzzles in a split second and humans still enjoy them. Your conclusion regarding your tempo might be right. Slow down, take your time, think about moves beyond your next one. That should definitely improve your score in the long run. And another thing: just because some strategy didn't work the first time doesn't mean that the strategy is bad. The luck of the draw can royally screw you over as we've seen even in the AI. Be patient.
You shouldn't feel dumb. Frankly, there's nothing strange in the fact that a computer can play better than most of us, especially in a "simple" game like Threes. Processing a lot of data in a short time is what computers were designed for.
Thinking about your response lead to this: Counterexample: The following is a more than legal starting condition: Code: _ 0 0 0 _ 0 0 0 0 0 0 0 [B]0[/B] 0 0 0 Move down. Code: _ _ _ 0 _ 0 0 0 _ 0 0 0 [B]0[/B] 0 0 0 The marked 0 reduced its number of neighbors from 4 to 3. So the Corollary above is wrong. How about the following modification: Corollary #2: In Zeroes!, once a card has neighbors (cards in the same row or column) it cannot go back to being lonely (have no neighbors). The proof, interestingly enough, remains unchanged.
Playing too fast is likely. Notice that Nicola's program works by looking ahead. You should take the time to do the same!
Sure it's funny to me too - I just wanted to address the little kernel of truth that might hide in his statement. Many people have developed or acquired an aversion to math and/or logical reasoning (for examples, just look into the comments on Vi Hart's videos on YouTube). Don't get me wrong: I'm not blaming anyone for their attitude towards these topics, I just try my best not to add to their aversion by writing my posts as concise and interesting as possible. The third of Clarke's Laws states: "Any sufficiently advanced technology is indistinguishable from magic.". A similar statement can be made about theories. The important thing to keep in mind is that it's only the understanding of the theory or technology that makes the difference to magic.
Well, I've implemented card counting and it did improve the results, but not by much. Since this is calculated over only 100 simulations, it isn't necessarily significant. 384: 100% 768: 98% 1536: 67% 3072: 10% median score = 76,410
TouchArcade show mentionings Hey guys, we made it into The TouchArcade Show #143 (from 1:12:45 to 1:17:31). Free kudos for all!
This thread is one of the best I have seen for some time on any site! Also Vi Harts videos are awesome. Also, if you haven't already heard of them, check out Numberphile on YouTube. They are very interesting - for example what is the answer if you add all integers between one and infinity? You'll have to watch the video to find out. Back on topic I still have only had one 768
