Thanks!! C# Nice! I read his post too, and use a 64-bit int and lookup arrays as well, but your code seems significantly faster than mine. I suspect this is mostly because it's written in C# as opposed to C++. Are you doing anything to parallelize your algorithm? One of the reasons I picked C# is because it has excellent multithreading tools, and so when I run my AI it uses all 8 of my logical cores at 90+%. If you're only running on one core, then I wonder if there's a more fundamental way in which I can improve the performance of my algorithm, since typically the speed difference between C# and C++ isn't all that huge. Given your terminology, the results I posted are for running my bot at 1+2+3. The "X" number is obviously hugely expensive, since there are so many random possibilities it has to check. This is basically how my evaluation function works. I don't have enough statistical data to prove this, but I'm fairly confident that there is a point at which further increasing the Y value in 1+X+Y actually becomes detrimental. I ran a handful of hundred-game sets, and 1+1+4 was actually worse than 1+1+3. I hypothesize that the empty spaces introduced by *not* predicting new cards actually makes the AI overly optimistic.
Yes, my program is multithreaded too. I guess this is one of those cases where the raw power of C++ really shines, or there is some optimisation that you left out. Did you check with a profiler? I used Very Sleepy which helped iron out a couple of bottlenecks. Also, I found that compiling the app as 64-bit improved performance since it has to do so many bitwise operations on a 64-bit integer. Interesting. My program does 100 runs at 1+2+3 in about 5 minutes. Here are the results: 384: 100% 768: 100% 1536: 84% 3072: 23% 6144: 0% min score = 21,816 median score = 88,038 max score = 263,577 they are comparable to yours, apart from the notable lack of 6144! That was my experience as well, and I agree with your hypothesis.
Could certainly be... in my experience C# is less aggressive than C++ with optimizations like loop unrolling and inlining method calls. I might try writing a simple C++ version of my AI to see how it compares. I have not profiled yet, but I will. Yeah, I have 64-bit mode turned on. (As it is by default in C#.) By any chance do you have a way to measure how many actual board evaluations your program can perform per second? Mine does about 2.5 mil/sec. (By "board evaluation", I mean when your algorithm has reached its maximum look-ahead depth and then evaluates the potential board.) I just want to verify that we're measuring performance in the same way, so I would assume that your program can do far better than 2.5 mil/sec.
Easy enough. For 10 runs of the 1+2+3 configuration I logged this: 2391946846 evaluations in 66.744000 seconds, or 35837631 evaluations/sec but note that just having an atomic variable to count evaluations perturbs the measure. Taking that out, the running time almost halves: 0 evaluations in 36.642000 seconds, or 0.000000 evaluations/sec so that would be 2,391,946,846 evaluations in 36.642 seconds, so the real figure is more like 65 million evaluations/second.
If you mean 'atomic' in the thread-safe sense, why not keep counters separately per thread (non-atomic) and combine the counts at the end? A non-atomic counter really shouldn't impact the runtime.
I'd like to propose an experiment for your bots: let them chose which card to insert and where. This would of course still conform to the rules (stack of 12, new card only in lines where cards moved, bonus card with a chance of 1/21 et cetera). With the normal cards the bot can pick any card left in the stack and if a bonus card will come up next it can chose the value. The only thing left to chance is the choice of whether the next card is a normal one or a bonus card. This should give us a really good upper bound for the best possible score an insanely skilled human with an insane luck can achieve. Can it break a million?
I had the "oracle" bot doesn't get to choose which card to get or where to put it, it simply knows them in advance. Surely this is more restrictive of what you are proposing? It scored 2,444,010 some time ago. The current version of the engine can probably do better than that.
The upper bound is nearly limitless, due to the bonus cards, which quickly become the only relevant cards as the topmost card gets sufficiently high. For instance, suppose the board has a 6144 and a few low cards. Keep pushing the low cards together to make 48's, and give yourself a 768 for each bonus card. After 8 bonus 768's (merging them as you go to make 1536, 3072), you can merge that with the 6144 to make a 12288, and you're back where you started, with a few 48/96/192's on the board. Now to clean up these cards, make each bonus card a 48/96/192 until you have a 384, then make the bonus card sequence 384, 768 to give you a 1536. Then catch 7 1536 bonus cards to make another 12288, and merge it with the first 12288 to make 24576. Then you're essentially back where you started (except the high card is doubled), and you can use the same technique to easily leverage your way to 49152, 98304, 196608, 393216, 786432, and so on. You'll eventually hit a limit as you have several intermediate cards "climbing the ladder" at once, but I'm guessing the final card value limit is in the neighborhood of 10^100. Of course, you'll need more than 64 bits to represent these boards!
Knowing what comes next does not prevent bad luck from screwing you over. In principal, I agree with you but your abstract description for reaching potentially limitless scores ignores the board limitations, card draw mechanic and movement rules of the game. Just because in theory you could combine cards forever does not mean that the rules of the game allow that.
I seem to recall you posting that there was a 1/21 chance for drawing a bonus card, which meant you would rarely get 2 bonus cards in close proximity. There is a small yet finite probability of getting just enormous bonus cards, then. If you artificially limited the bonus cards to 1/21 that wouldn't be following the rules of the game either. Or did I misunderstand? Very likely possibility there, I give it higher than 1/21 odds.
Would the neccessary 2's and 1's and threes not mess this up eventually? As in, eventually you need a very small number of spaces assuming you get a bonus of 1/8 your high card. 1 space for the 1/2 high card, 1 space for the 1/4 high card, and 2 spaces for the highest bonus you can get. After that match, you have unsufficient spaces. I just wonder if given the perfect cards you can always match enough cards at once to keep the board open indefinately.
What I proposed in the "insane skill + insane luck" scenario is that the only randomness left is with the occurrence of bonus cards. To put it in different words: after every move, there is a fair roll of an (imaginary) 21-sided dice, if it comes up 1, the next card must be a bonus card >3 if not, it comes from the stack of 1's, 2's and 3's. I will admit, however, that a "300 bonus cards in a row"-scenario is not impossible but very very unlikely (approx. 1:2,000,000). That's precisely what I'm wondering about. Can you go on forever while still abiding to the rules (and a probable distribution of bonus cards)?
Wouldn't it be (1/21)^300? That breaks my iPhone calculator, but (1/21)^10 is 1:1.7e13 odds. (Btw, I think I've found a bug in my iPhone calculator. (1/21)^68 gives 1.3e-90, (1/21)^69 gives 5.8e164.)
Yes, you're absolutely right. My result should have startled me. The correct probability for 300 bonus cards in a row is indeed (1/21)^300=1/4.6e396. The universe will turn into a stuffed pink teddy before that happens.
