4 ms·
When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are s
by saurik 13y ago
When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are so many possible moves: the probability that, of all the pieces on the board, with all of the positions it could have made, that it would stumble upon a move that devastates your position--especially considering that often multiple correct moves must be performed in specific sequence to take advantage of what "should be" a winning position--is vanishingly small.
Further: the potential for gain (trivial mate against a stupid opponent in a handful of moves) is great. If you are thereby playing for "fastest win over time", taking advantage of random's suboptimality seems sane. In 2048, the bottleneck on your score seems best approximated by how long you survive: pulling stunts won't get you to 2048 all that faster as you need to have worked through enough tiles to arrive at that point: I'd imagine the difference would be at best a tiny fraction of the "required" moves.
Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess.
In summary: I just don't think comparing this game to chess is leading to useful intuitions.
- khafra 13y agoIt sounds like you're thinking he suggested just greedily taking the best possible move. But that's not what he suggested; he suggested evaluating the actual distribution of the opponent's moves and making the move with the highest expected value.
- saurik 13y agoNo, I entirely understood that. I am quite happily willing to believe that I misunderstand the ramifications of that algorithm (I spent a lot of time talking about game theory in college, but it was not my field, and that was a long time ago), but that is the algorithm I inferred. (I would respond more, but you didn't leave me with any specific complaints to respond to, so all I can really say is "no".)
- Anderkent 13y agoThe question is do you want to have the shortest expected number of turns until you win, or a 100% win rate. Playing safe (min-max) is what ensures the 100% win rate, but you might be making games longer on average.
- feral 13y agoIt doesn't have a 100% win rate as it stands. Mini-max isn't even 'playing safe'. Consider the following choice of moves, each leading to one of 5 random tile inserts: Move A, which leads to 5 possible moves with the following game state goodnesses: ['Loss','Win','Win','Win','Win'] Move B, resulting in: ['99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss'] Minimax is never going to choose A. Is that really what you want, even if your strategy is 'play it safe'?
- Anderkent 13y agoFair enough; I only ran it a couple times and it got to 2048 so I assumed it's a guaranteed win.
- khafra 13y agoMin-max optimizes your chance of winning under the assumption of a rational adversary. That chance will be lower than "certain victory," especially in un-solved, symmetric games, because a rational adversary will also be playing min-max. The guarantee min-max provides is that it will do even better against a non-rational adversary than it does against a rational adversary; not that it will do better than any other algorithm against non-rational adversaries--which is the way I think it often gets parsed. Also, we should note that the "value" in "expected value" doesn't have to mean "score." It could be the logarithm of your score, or your chance of winning against a rational adversary, or even the enjoyability of the game to spectators (if you have a precise metric for that).
- feral 13y agoMy impression is that you don't understand how these things work, so I'll start from the basics; apologies if wrong. First off, the chess counter-example was in response to something general shmageggy said about 'all minimax algos'. More broadly, in practice the issue is that you only have computational resources to search a fraction of possible game states. So where do you direct your limited resources? Some candidate strategies: minimax with AB, exhaustive, MC sampling. Even with any of these strategies, we can usually only search the game state tree to a given depth. (This is the tree of 'If I go here, then the game goes there, then I go here etc'.) When we reach our depth limit (if we haven't reached a terminal state - i.e. a win or loss), we use a heuristic (maybe 'number of free tiles') which approximates the value of the state to us at that point. >Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. If the computer only has a few possible moves, then, yes, it might randomly choose the best one. But if it only has a few possible moves, chances are that any tree search technique, even stochastic, will start to expand all of them. The question is, though, how will you know how good each of these moves is when you start examining are? I.e. Which of the moves available to you right now should you make? With Minimax/AB, you'll get a sense the move is optimal, because you'll look at the consequences of the move, (if the game makes the worst response to me (if I make the best move for me (if the game makes the worst response for me ... (heuristic evaluation)))). With (sensible) MC search, you'll instead get a sense of which move is optimal by looking at more like what happens (if I make the best move for me (for each of a bunch of random moves the game could make (then if I make the best move for me (for each of a bunch of random moves the game could make ... (heuristic evaluation)))). My point is that the latter is more suitable for this domain. >As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess. Well, then, if the probability of it randomly hitting a problematic move is high in a certain state, your MC search will be highly likely to come across that move, and thus you'll be likely to avoid moves that bring you to that state. So, no problem. In summary: 1) If the game is highly likely to make a devastating move by random chance, then you are highly likely to come across that move in your stochastic search, so that's not really an objection. 2) In this game, just as in chess, there are always more states you'd like to search and expand than you have the resources to. Even if the computer only has a handful of 'moves' at any time, in order to tell how good these moves around, you've still got to expand out a lot of states. Choosing to use minimax instead of MC doesn't save you from that.