Entry tags:
Local solutions versus search spaces
I play a lot of board games and card games (of both the regular and collectible types). I'm pretty good at most of them, too, although not brilliant. And one of the recurring questions that I frequently think about is the method I use to pick my moves in each game - am I just choosing whatever looks good at the time, am I planning two or three moves ahead, or do I have a long-term strategy that I'm sticking to? Or to put it another way, if I was going to design an AI to play the game for me, what would be the least effort for me to code that would still lead to optimal or near-optimal moves? I'm pretty sure that in a lot of games you can get away with choosing the most obvious 'best' move and end up with optimal play.
Some considerations involved:
* What do we actually mean by a local move versus a search throuh a solution space? The most obvious example I can think of here is that in chess one way to play would be to try to model an opponent's likely moves and work out which ones will lead to checkmate. But if you play chess enough that you can recognise good and bad board positions intuitively, a large part of play can be reframed as trying to get your pieces into a good overall position, without needing to make costly explicit predictions about the opponent. (disclaimer: I can count the number of times I've played chess on one hand, so I am very much open to being corrected on this). Although then the new problem would be how to formulate rules for what constitutes a 'good' position. Searching a solution space might be faster.
* Is there a meta-strategy for working out which games you need to plan ahead and which ones you can make local moves for? I'm pretty sure there is one, but at the moment my method can be summarised as knowing it when I see it. Part of it is obviously player interaction - if most of your points are gained from interplayer conflict then it's more likely that you'll need to predict what your opponent is up to. Another obvious factor is randomness - snakes and ladders is completely random and there's nothing to predict, while at the other end of the scale we have wargames like Diplomacy where the outcome is completely dependent on your skill as a player and you spend the entire game trying to predict and influence your opponents' moves. Other likely factors are whether the game is zero-sum (ie. your gain is your opponent's loss) and how large a gain or loss you can potentially make in a single turn, but they don't seem to be really strong predictors.
Tangentially-related anecdote that is only of interest to people who've played Puerto Rico: I spent most of last week extremely sleep-deprived due to a combination of grad school applications and work. So when we sat down to play Puerto Rico, my ability to plan ahead was massively compromised*. I've played it enough that I have a good intuitive feel for what a 'good' move is most of the time, but my build orders were haphazard, and at least once I picked a role in such a way that the player to my left got most of the benefit from it. But I still did relatively well despite all of that - only 7 points behind the victor, and not last. So I would consider Puerto Rico to be a game that requires some planning ahead but not an extensive amount - at any given point you need to be able to predict what roles are likely to be chosen and in what order before it's your turn again and try to make sure you can benefit when they're called, and for the shipping phase you need to calculate everyone else's optimal move, to decide whether it's worth choosing Captain at all or you can afford to wait for someone else to choose it for you.
* Tangent to the tangent that will be of interest to no one: I was so sleep-deprived that after I'd finished explaining the game basics to Malcolm, when Anton asked whether I'd covered how the game ends, I couldn't remember what the conditions were - my vague impression was that you play until you stop, and then you count up your points. Oh and I double-counted the extra victory points from my Harbour during one of the last shipping phases and didn't realise until the next morning.
Some considerations involved:
* What do we actually mean by a local move versus a search throuh a solution space? The most obvious example I can think of here is that in chess one way to play would be to try to model an opponent's likely moves and work out which ones will lead to checkmate. But if you play chess enough that you can recognise good and bad board positions intuitively, a large part of play can be reframed as trying to get your pieces into a good overall position, without needing to make costly explicit predictions about the opponent. (disclaimer: I can count the number of times I've played chess on one hand, so I am very much open to being corrected on this). Although then the new problem would be how to formulate rules for what constitutes a 'good' position. Searching a solution space might be faster.
* Is there a meta-strategy for working out which games you need to plan ahead and which ones you can make local moves for? I'm pretty sure there is one, but at the moment my method can be summarised as knowing it when I see it. Part of it is obviously player interaction - if most of your points are gained from interplayer conflict then it's more likely that you'll need to predict what your opponent is up to. Another obvious factor is randomness - snakes and ladders is completely random and there's nothing to predict, while at the other end of the scale we have wargames like Diplomacy where the outcome is completely dependent on your skill as a player and you spend the entire game trying to predict and influence your opponents' moves. Other likely factors are whether the game is zero-sum (ie. your gain is your opponent's loss) and how large a gain or loss you can potentially make in a single turn, but they don't seem to be really strong predictors.
Tangentially-related anecdote that is only of interest to people who've played Puerto Rico: I spent most of last week extremely sleep-deprived due to a combination of grad school applications and work. So when we sat down to play Puerto Rico, my ability to plan ahead was massively compromised*. I've played it enough that I have a good intuitive feel for what a 'good' move is most of the time, but my build orders were haphazard, and at least once I picked a role in such a way that the player to my left got most of the benefit from it. But I still did relatively well despite all of that - only 7 points behind the victor, and not last. So I would consider Puerto Rico to be a game that requires some planning ahead but not an extensive amount - at any given point you need to be able to predict what roles are likely to be chosen and in what order before it's your turn again and try to make sure you can benefit when they're called, and for the shipping phase you need to calculate everyone else's optimal move, to decide whether it's worth choosing Captain at all or you can afford to wait for someone else to choose it for you.
* Tangent to the tangent that will be of interest to no one: I was so sleep-deprived that after I'd finished explaining the game basics to Malcolm, when Anton asked whether I'd covered how the game ends, I couldn't remember what the conditions were - my vague impression was that you play until you stop, and then you count up your points. Oh and I double-counted the extra victory points from my Harbour during one of the last shipping phases and didn't realise until the next morning.