3 ms·

Wow, what a great answer -- thanks! I have a question -- in a card game, it appears that knowing which cards have been played is important (or can help, anyway

Wow, what a great answer -- thanks! I have a question -- in a card game, it appears that knowing which cards have been played is important (or can help, anyway). This seems to violate the idea of being memoryless. Can you "cheat" and make reason on the cards left instead? Thanks for any clues.

platz 8y ago
Card games e.g. Poker isn't a perfect information game, so history does matter, so it's not markovian.
- chris_st 8y ago
  Sorry, should have given a more concrete example, more what I'm interested in. I was thinking Hearts or Spades, which aren't perfect information, but since the whole deck is dealt out, you can (with a lot of memory :-) know what cards are left.
  - clickok 8y ago
    Yeah, so here we can "solve" the problem without using a POMDP by really expanding what constitutes the state space. Initially, your state is your hand plus the initial rules (who goes first, which suit is trump, etc depending on what kind of game you're playing). After each player's turn you transition into a new state, which is <<starting hand>> + <<history of cards played>>, so at each point in time the state has all the available information. Obviously this leads to a combinatorially huge state space, because there's O(52!) different possible sequences for a standard deck of cards. Typically you have to use some sort of approximation architecture because evaluating all different possible responses to a given sequence of cards would both take too long and even if you could do it, the memory requirements would be enormous. See for example DeepStack[0], which uses a neural net to approximate the quality of positions + possible responses (along with other techniques), rather than having a lookup table for what to do in each possible game state. So you can formulate such games as MDPs, but the question then becomes: is this a useful way to think about it? Sometimes it is, because your approach to the problem scales and so you can throw enough resources (training data, compute power) at it to learn a useful strategy; other times there is a better way of formulating the problem[1]. I have some implementations of reinforcement learning algorithms and code for working with MDPs if you're interested in that sort of thing[2], and of course I highly recommend Rich's book. --- 0. https://www.deepstack.ai/ https://www.deepstack.ai/ -- note that it's not really an RL system, but it does illustrate using neural nets to learn complicated functions in a large state space. 1. For example, I am not sure that such an MDP for hearts is well-posed: the convergence results that I'm familiar with rely on the MDP being ergodic and aperiodic, but the suggested construction is obviously periodic. 2. The algorithms: https://github.com/rldotai/rl-algorithms https://github.com/rldotai/rl-algorithms An MDP library: https://github.com/rldotai/mdpy https://github.com/rldotai/mdpy (check out notebooks/example_notebook.ipynb for a basic demo).
60654 8y ago
For something that has state that is not always fully known (for example, some cards have been played so we know what they were, but we don't know what's left in the deck or in other players' hands), what we're describing is a _partially observable_ Markov decision process, or POMDP. In short, a regular MDP models moving from one state to future states with some probability. In a POMDP, we don't know which state we're in, but we have some guesses, i.e. we have a probability distribution over all states. So we model a sequence of taking actions and performing observations, and using those observations to update the probability distribution, so that we can reduce the uncertainty as much as possible. The typical example is robot navigation, where POMDPs are used extensively. For example, a blind robot starts out somewhere, it doesn't know where, so the probability distribution over all possible locations is uniform. Then it moves north, and discovers that it was successful; this observation modifies the PD to states that are reachable by moving north from previously likely states (conceptually: this will exclude all sorts of corners and dead ends from consideration). Then let's say it tries to drive north once again, but it discovers it bumped into a wall and was unsuccessful. Now the PD gets updated again, based on previous PD and the results of this action (conceptually: we bump the probability of any state that we can drive north to, and hit a dead end or a t-intersection), and so on. As this sequence of actions and observations continues, we hope the probability distribution will collapse to the specific location that we're in, or a small set of guesses. (This is a narrative description of course; for the nitty gritty details there are many more precise materials on POMDPs! :) ) By the way, this is still a _Markov_ process: the trajectory of _how_ we got to some probability distribution doesn't matter, if those sequences of actions produced the same result they are treated as equivalent per Markov assumption.
nazgul17 8y ago
The state of the game does not have to be what you would physically see as a player. Generally, you do not model the state space as a graph, but model the state as a data structure. To make the Markov property apply, you just need to add the right kind of information to your data structure. Factually, you can chat by incorporating history in it. But the algorithms are happy regardless of the cheating: when landing a second time on the same data structure (aka state) the algorithms know that the reward distribution and the next state distribution are the same in both occurrences, so they have some degree of knowledge the second tone based on what happened the first time (and so on, with further experience improving knowledge and increasing the confidence on it).

platz 8y ago

Card games e.g. Poker isn't a perfect information game, so history does matter, so it's not markovian.

chris_st 8y ago
Sorry, should have given a more concrete example, more what I'm interested in. I was thinking Hearts or Spades, which aren't perfect information, but since the whole deck is dealt out, you can (with a lot of memory :-) know what cards are left.
- clickok 8y ago
  Yeah, so here we can "solve" the problem without using a POMDP by really expanding what constitutes the state space. Initially, your state is your hand plus the initial rules (who goes first, which suit is trump, etc depending on what kind of game you're playing). After each player's turn you transition into a new state, which is <<starting hand>> + <<history of cards played>>, so at each point in time the state has all the available information. Obviously this leads to a combinatorially huge state space, because there's O(52!) different possible sequences for a standard deck of cards. Typically you have to use some sort of approximation architecture because evaluating all different possible responses to a given sequence of cards would both take too long and even if you could do it, the memory requirements would be enormous. See for example DeepStack[0], which uses a neural net to approximate the quality of positions + possible responses (along with other techniques), rather than having a lookup table for what to do in each possible game state. So you can formulate such games as MDPs, but the question then becomes: is this a useful way to think about it? Sometimes it is, because your approach to the problem scales and so you can throw enough resources (training data, compute power) at it to learn a useful strategy; other times there is a better way of formulating the problem[1]. I have some implementations of reinforcement learning algorithms and code for working with MDPs if you're interested in that sort of thing[2], and of course I highly recommend Rich's book. --- 0. https://www.deepstack.ai/ https://www.deepstack.ai/ -- note that it's not really an RL system, but it does illustrate using neural nets to learn complicated functions in a large state space. 1. For example, I am not sure that such an MDP for hearts is well-posed: the convergence results that I'm familiar with rely on the MDP being ergodic and aperiodic, but the suggested construction is obviously periodic. 2. The algorithms: https://github.com/rldotai/rl-algorithms https://github.com/rldotai/rl-algorithms An MDP library: https://github.com/rldotai/mdpy https://github.com/rldotai/mdpy (check out notebooks/example_notebook.ipynb for a basic demo).

60654 8y ago

For something that has state that is not always fully known (for example, some cards have been played so we know what they were, but we don't know what's left in the deck or in other players' hands), what we're describing is a _partially observable_ Markov decision process, or POMDP. In short, a regular MDP models moving from one state to future states with some probability. In a POMDP, we don't know which state we're in, but we have some guesses, i.e. we have a probability distribution over all states. So we model a sequence of taking actions and performing observations, and using those observations to update the probability distribution, so that we can reduce the uncertainty as much as possible. The typical example is robot navigation, where POMDPs are used extensively. For example, a blind robot starts out somewhere, it doesn't know where, so the probability distribution over all possible locations is uniform. Then it moves north, and discovers that it was successful; this observation modifies the PD to states that are reachable by moving north from previously likely states (conceptually: this will exclude all sorts of corners and dead ends from consideration). Then let's say it tries to drive north once again, but it discovers it bumped into a wall and was unsuccessful. Now the PD gets updated again, based on previous PD and the results of this action (conceptually: we bump the probability of any state that we can drive north to, and hit a dead end or a t-intersection), and so on. As this sequence of actions and observations continues, we hope the probability distribution will collapse to the specific location that we're in, or a small set of guesses. (This is a narrative description of course; for the nitty gritty details there are many more precise materials on POMDPs! :) ) By the way, this is still a _Markov_ process: the trajectory of _how_ we got to some probability distribution doesn't matter, if those sequences of actions produced the same result they are treated as equivalent per Markov assumption.

nazgul17 8y ago

The state of the game does not have to be what you would physically see as a player. Generally, you do not model the state space as a graph, but model the state as a data structure. To make the Markov property apply, you just need to add the right kind of information to your data structure. Factually, you can chat by incorporating history in it. But the algorithms are happy regardless of the cheating: when landing a second time on the same data structure (aka state) the algorithms know that the reward distribution and the next state distribution are the same in both occurrences, so they have some degree of knowledge the second tone based on what happened the first time (and so on, with further experience improving knowledge and increasing the confidence on it).