My approach encodes the entire board (16 entries) as a single 64-bit integer (where tiles are the nybbles, i.e. This game took 27830 moves over 96 minutes, or an average of 4.8 moves per second. The AI never failed to obtain the 2048 tile (so it never lost the game even once in 100 games) in fact, it achieved the 8192 tile at least once in every run! The minimum score over all runs was 124024 the maximum score achieved was 794076. For each tile, here are the proportions of games in which that tile was achieved at least once: 2048: 100% To assess the score performance of the AI, I ran the AI 100 times (connected to the browser game via remote control). If the search depth is limited to 6 moves, the AI can easily execute 20+ moves per second, which makes for some interesting watching. In testing, the AI achieves an average move rate of 5-10 moves per second over the course of an entire game. The AI in its default configuration (max search depth of 8) takes anywhere from 10ms to 200ms to execute a move, depending on the complexity of the board position. As far as I’m aware, it is not possible to prune expectimax optimization (except to remove branches that are exceedingly unlikely), and so the algorithm used is a carefully optimized brute force search. The AI simply performs maximization over all possible moves, followed by expectation over all possible tile spawns (weighted by the probability of the tiles, i.e. After a while, I started looking at how I could play it automatically, so I wrote a 2048 AI using expectimax optimization. One could discuss a bit how and when a game ends but this answer is already long enough.I caught the 2048 fever a while back, but got a little bored of playing the vanilla game. Once again, it will be easier to consider the general templates (see the answer below) and the logarithmic notation.Ĭonsider $\ A=A_0=A_1=\ldots$ and $\ \forall_$. Actually, it is obtained as corollary to a maximal configuration (even if such a configuration can be fictitious-nevertheless, all tiles have values not exceeding the respective tiles of the fictitious configuration). Since I have my bound for the maximal tile, let me follow it with an upper bound for the total sum. I'll clarify the simple issue of an upper bound for the total sum: PS: I'd like to see a quote of an essential moment of a rigorous proof of an upper bound for a maximal tile. Please, show me in those posts that it's otherwise (a feeling that a construction is the best is not a proof). Their style seems to be of the type: I cannot do it better (without even attempting a mathematical proof of a bound). The other two posts mentioned provided a construction but not a proof that it provides maximum, and there is no other proof of a specific lower bound there. It's nice to know about both posts, but that's all. Is related to the game 2048, this post and my question and my answer below are otherwise not related. If $X$ is not sharp than sharper bounds are welcome too.īTW, have anybody published an upper bound for 2048 on Internet or elsewere? (If there is a respective link then I'd like to see the article).Įxpected halting time for "The 2^n Game" (aka 2048) - with random moves Thus my question: what is the maximal possible score for game 2048? (I'll provide $X$ in an answer below, as a SPOILER it was quite straightforward to get $X$, and similar upper bounds for a way larger family of similar games).
Possibly my $X$ is the actual maximal score, I don't know, it may go either way. I have an explicit integer $X$ which is greater or equal than any score of this game. T's been weeks (months?) since the 2048 game-by Gabriele Cirulli-took Internet by storm.
0 kommentar(er)
