Sadly, totally unrelated to the Hong Kong film...
2048 AI
151–160 of 197 posts
Re: 2048 AI
#152How would I go about making an AI for this game? Mainly getting it to interface with the actual game input and output.
Re: 2048 AI
#153if this is AI why it scores only 512 square as max?
Assuming you're not trolling, it's because this AI is using a heuristic approach rather than a guaranteed correct approach.
Heuristics rely on simplified rules which don't accurately model the system on which they're acting 100% of the time. Good heuristics can come close to 100%, however.
But why? Glad you asked!
A 100% correct solution would be to write an algorithm which enumerates all of the possible moves as a decision tree, and walks the decision tree to find the correct answer.
However, given that there are four possible moves the user can make (up, down, left, right) and an upper bound of 32 possible moves the computer can make (computer places "2" or "4" anywhere in a 4x4 grid), each level of the tree could require up to 128 times the number of computations that it took to compute the previous level of the tree.
For example, calculating the first turn is on the order of 128 calculations. Calculating the second move is on the order of 128^2 calculations. Calculating the third is 128^3, an so on. By order of magnitude, how many moves do you think it takes on average to get to 2048? 10^3? Even if we were being really optimistic, maybe it's 10^2. In that case, you'd have to perform somewhere around 128^100 computations in order to solve the game perfectly every time.
Incidentally, python tells me that'd be
5260135901548373507240989882880128665550339802823173859498280903068732154297080822113666536277588451226982968856178217713019432250183803863127814770651880849955223671128444598191663757884322717271293251735781376
Or for fun, this is 128^1000:
16216967556622020264666650854783770951911124303637432562359820841515270231627023529870802378794460004651996019099530984538652557892546513204107022110253564658647431585227076599373340842842722420012281878260072931082617043194484266392077784125099996860169436006660011209817579296678781962552377006552947572566780558092938446272186402161088626008160971328747492043520874011018626908423275017246052311293955235059054544214554772509509096507889478094683592939574112569473438619121529684847434440674120417402088754037186942170155022073539838122429925874353753616104159343594557666561701790904172597025336526662682021808493892812699709528570890696375575414344876088248369941993802415197514510125127043829087280919538476302857811854024099958895964192277601255360491156240349994714416090573084242931396211995367937301294479560024833357073899839202991032234659803895306904298017400980173252106913079712420169633972302183530075897845195258485537108858195631737000743805167411189134617501484521767984296782842287373127422122022517597535994839257029877907706355334790244935435386660512591079567291431216297788784818552292819654176600980398997991681404749384215743515802603811510682864067897304838292203460427757655073776567547507027144662263487685709621261074762705203049488907208978593689047063428548531668665657327174660658185609066484950801276175461457216176955575199211750751406777510449672859082255854777144724233490076402632176089211355256124119453870268029904400183858505767193696897593661213568888386800238409325673807775018914703049621509969838539752071549396339237202875920415172949370790977853625108320092839604807237954887069546621688044652112493076290091990717742355039135117441532973747930089955830518884135334798464113680004999403737245600354288112326328218661131064550772899229969469156018580839820741704606832124388152026099584696588161375826382921029547343888832163627122302921229795384868355483535710603407789177417026363656202726955437517780741313455101810009468809407811220573803353711246329589162370895804762245950918253016369092362406714116443316561598280583720783439888562390892028440902553829376
Re: 2048 AI
#154Re: 2048 AI
#155my AI won the game with a score of 20388
Re: 2048 AI
#156Is this game always guaranteed to be winnable, or is it like Solitaire?
Solitaire is perfectly winnable.
I have finished solitaire a lot of times.
Re: 2048 AI
#157Earlier quoted context omitted.
Heh. If you look in the code you'll see a big commented out chunk where I tried randomly sampling computer moves to get sort of an 'expected value' for the opposition's move. Empirically, it performed worse. I think this is for the same reason that all minimax algos assume optimal play by the opponent: if you assume optimal and they play less than so, it can only work in your favor. However I think there's some truth…
Its interesting that your approach performed worse; I wonder if it could be modified to do better? Interesting. >I think this is for the same reason that all minimax algos assume optimal play by the opponent: if you assume optimal and they play less than so, it can only work in your favor. That doesn't make sense when talking about a random opponent, though. Imagine its chess. You are considering moving a pawn into a…
[deleted]
Re: 2048 AI
#158if this is AI why it scores only 512 square as max?
Assuming you're not trolling, it's because this AI is using a heuristic approach rather than a guaranteed correct approach. Heuristics rely on simplified rules which don't accurately model the system on which they're acting 100% of the time. Good heuristics can come close to 100%, however. But why? Glad you asked! A 100% correct solution would be to write an algorithm which enumerates all of the possible moves as a d…
Actually, to make a 2048 you need to make two 1024s. It's unlikely that you'll make two 1024s at the same time. Similarly for the lower tiles. As a sort of upper bound you expect the game to be over in about 1024 moves and it's likely to not be much less than that. I think a more realistic number is somewhere in the 500s
Re: 2048 AI
#159Earlier quoted context omitted.
I am with saurik. The utility function is an approximation. So MCMC is aggregating information over an erroneous space, and min/max is also optimizing over an erroneous space too. Which is the correct thing to do is conditioned on how the utility function behaves. In this scenario I think min/max plays maximumly conservative, which empirically seems to be the best thing to do. If the utility is minimize free space on…
I agree that all approaches are approximations, and which would actually perform best in this game is an empirical question. It'd take some work to really explore and tune either minimax or MC approach, so I wouldn't throw either out due to one failed attempt. I accept the argument that "minimax is conservative, and conservative is good" might be correct. But I don't think its likely, and, without the time to code my…
I was initially surprised that minimax worked at all for the exact reasons you cite. But it actually matches my intuition from playing the game kind of a lot. I think it's generally the case that most "opponent" moves are completely OK but there's one move that results in a high probability of loss (the one that's behind your "stack"). Avoiding worse case scenarios is really the entire game (i.e. your example wherein low probability of certain loss is being compared unfavorably to a guaranteed 99% loss rate does not actually come up). So if you built a really good, comprehensive MC approach, it might just reduce itself to minimax anyway. Thus perhaps the minimax is just a simpler way to implement the right approach from the get-go.
Re: 2048 AI
#160I always get at least 1024 now. I'm playing somehow like tetris...