8402: 2048 from the other side
sphere.chronosempire.org.uk
sphere.chronosempire.org.uk
I remember watching this AI play and thinking if I could write my own strategy into an AI. The AI's strategy suffers from the issues that my strategy tries to combat. Perhaps someone can tell from my screenshot what my strategy is.
The way I beat the AI was to try to give them isolated 2s on the opposite sides of the board and then flood the board with 4s. This prevented the AI from keeping all the low numbers together and blocked some tiles from use (the ones with the isolated 2s).
My strategy was to give the AI a single 2 at the beginning, then only 4s. When the board fills up enough, there will probably be a space where you can put a second 2 to make it lose before it can combine them.
Now we need a multiplayer variant a-la puyo-puyo-pop.
The easiest solution is to have just one 2 on the table, then spam 4 in corners.
Best( lowest ) score: 1684
This is the first 2048 variant that I'm able to beat. yay me... .__.
but 4d is terribly hard: http://huonw.github.io/2048-4D/
edit: I did a 3d victory in the 18 minutes in editing the comment. You can generally just push higher numbers into a corner, and pick either the left or the right side to consistently fold to and you'll get it mostly without thinking.
That probably says something about how humans relate to interfaces that map higher dimensions to 2D planes, or maybe it's just the way the 4D layout maps to the screen.
I'm sure some people can maintain clear mental models of higher order dimensions and seamlessly translate the grids on the screen in some hyperspace in the mind.
But I, my friend, have no chance of that. The more I ignore that notion, the easier it becomes.
all lies.
Take chess as an example. It's an EXP-TIME complete game with a branching factor of 35, and AI techniques win pretty much all of the time. In this case you're looking at a much simpler game (if you treat it as an expectiminimax problem, you alternate between turns with a branching factor of less than or equal to 4 and ones with a branching factor of less than or equal to 32). The game is much less complicated than chess. The game tree is really small, meaning that it should be tractable to most AI techniques.
Even though it is reasonable to 'solve' the problem, there are board setups that are unwinnable. Since the player has a lot more power over the game in placing tiles than the agent does in moving them, it is easier for the player to force the game to one of the unwinnable states than it is for the agent to prevent these things. Even if the agent is acting optimally, the player should still be able to win.
You say this game is less complicated than chess, but what measure of complexity are you talking about? Might it be computational complexity? Computer scientists of all people know that simple rules can provide arbitrary complexity.
This game is MUCH easier than the original, at least for me. I never managed to beat the original, but on the other hand I've yet to be beaten by the AI.
This makes it smell like a PSPACE-hard problem (if you make the board size arbitrary).
[EDIT] Now I see what you mean, that you could start in a position where you can guarantee a win and so being in P doesn't matter (the computer would just be able to tell quickly that it cannot win if you play optimally). But this also isn't satisfying because it seems unlikely that a random starting position would put you in such a state (since it's so early in the game!).
Edit: Try to play it the other way, too. Try dropping tiles in the best most convenient pattern for the AI. Notice the amount of clutter that inevitably results when reaching higher numbers. An interesting question would be, if you control both the tile placement and movement, what is the highest number you can reach? With the constraint you can place only 2s.
So let me be formal. I'm posing the following decision problem: given a target score n and some initial board configuration of size (k * k), can one player force a score of at least n? I conjecture this problem is PSPACE-hard.
Your claim is that if n >= 2048 and k = 4 then the answer is always no (though I don't buy your justification). My question is more general, and it's clear that there is not a constant answer (e.g. if n is 2 the answer is always yes, but for some sufficiently large n the answer is always no)
Either way, really cool.
setInterval(function(){ var cells = document.getElementsByClassName("grid-cell"); var pos = Math.floor((Math.random()*cells.length)); if(Math.random() < 0.5){cells[pos].click();} else {var ev = document.createEvent('HTMLEvents'); ev.initEvent('contextmenu', true, false); cells[pos].dispatchEvent(ev);} },100);