8 ms·

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

by feral 13y ago

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 position where it can be obviously taken with no cost by the other player, but where, if the other player doesn't take the pawn, you'll get a sure checkmate on the next go. You'd never make that move against an 'intelligent' player (i.e. in a minimax setup). But you'd definitely consider it against an enemy that moves randomly, because the expected value is so high. This isn't to discount your empirical experience with this game, just to make a more general point.

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 ago
  It 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 ago
    No, 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 ago
    The 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 ago
      It 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 ago
        Fair enough; I only ran it a couple times and it got to 2048 so I assumed it's a guaranteed win.
gradstudent 13y ago
> That doesn't make sense when talking about a random opponent, though. Sure it does. AB search means you play to maximise your own value and minimise the value for your opponent. If your opponent is using a random strategy they will likely make a poor move and that's extra advantage for you. Your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true. Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go).
- feral 13y ago
  Consider this game: You choose either Die or Coin. If you chose Die, I will roll a die. If the die is 1, I give you $0; otherwise, $1000. If you choose the coin, I'll give you $10 for heads, and $20 for tails. If you use a minimax policy, you will choose the coin, because the worst outcome of that choice is a $10 payoff. The 'best' 'worst' outcome is what you get with minimax, and that's $10. It is true that, as you say, if you instead get $20, you will be pleasantly surprised. "extra advantage for you", as you put it. But it should be crystal clear that minimax is nonetheless the wrong decision policy here. If you use a minimax policy when the outcomes are random, you will generally be doing it wrong. There are exceptions (e.g. you are starving and need $10 or else you'll die; or you are in my casino, and you think I'm using loaded dice, in which case the outcomes aren't random and you have an adversary; etc.) but in general, minimax is just wrong there. >your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true. No - my argument is that if an opponent is random a minimax strategy is generally not best. >Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go). Yes, that's also true.
  - gradstudent 13y ago
    You describe a one-player game with stochastic outcomes. I'm talking about a deterministic two-player game with one player making random moves. They're not the same thing.
deleted 13y ago
[deleted]

by feral 13y ago

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 ago
It 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 ago
  No, 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 ago
  The 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 ago
    It 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 ago
      Fair enough; I only ran it a couple times and it got to 2048 so I assumed it's a guaranteed win.

gradstudent 13y ago

> That doesn't make sense when talking about a random opponent, though. Sure it does. AB search means you play to maximise your own value and minimise the value for your opponent. If your opponent is using a random strategy they will likely make a poor move and that's extra advantage for you. Your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true. Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go).

feral 13y ago
Consider this game: You choose either Die or Coin. If you chose Die, I will roll a die. If the die is 1, I give you $0; otherwise, $1000. If you choose the coin, I'll give you $10 for heads, and $20 for tails. If you use a minimax policy, you will choose the coin, because the worst outcome of that choice is a $10 payoff. The 'best' 'worst' outcome is what you get with minimax, and that's $10. It is true that, as you say, if you instead get $20, you will be pleasantly surprised. "extra advantage for you", as you put it. But it should be crystal clear that minimax is nonetheless the wrong decision policy here. If you use a minimax policy when the outcomes are random, you will generally be doing it wrong. There are exceptions (e.g. you are starving and need $10 or else you'll die; or you are in my casino, and you think I'm using loaded dice, in which case the outcomes aren't random and you have an adversary; etc.) but in general, minimax is just wrong there. >your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true. No - my argument is that if an opponent is random a minimax strategy is generally not best. >Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go). Yes, that's also true.
- gradstudent 13y ago
  You describe a one-player game with stochastic outcomes. I'm talking about a deterministic two-player game with one player making random moves. They're not the same thing.

deleted 13y ago

[deleted]