Answers.Body: <p>I think that there are too many game states in that game for you to use value iteration. The upper bound for a simple concise representation would be <span class="math-container">$49^2 \times 2^{49}$</span>. That is:</p>
  <ul>
  <li><p><span class="math-container">$49^2$</span> covering all possible locations of the two players.</p>
  </li>
  <li><p><span class="math-container">$2^{49}$</span> covering whether each square exists or has been removed.</p>
  </li>
  </ul>
  <p>In this scheme, many combinations are not feasible, as pieces do have to be on existing squares and cannot share a space. However, this doesn't drop the number of allowed states by a significant amount (several or more orders of magnitude) that would make it worth a more complex representation, or put the game into reach of dynamic programming solutions.</p>
  <p>Potentially, a version on a 4x5 grid would be small enough to fit in memory and be solvable with dynamic programming. That would have a few million valid states.</p>
  <p>In terms of an id code, you could use a 64-bit unsigned integer, reserving 49 bits for the existence of the squares, and for simplicity giving 6 bits each to the locations. This would also be a valid state representation for actually playing the game efficiently, most programming languages support the bit manipulations that you would need in order to maintain the representation. However, it would need a separate expanded representation if you were to create neural network features for approximate value functions.</p>
  <p>In terms of writing a solver for the 7x7 version, I would recommend combining a look-ahead planner such as negamax, with an approximate neural network-based reinforcement method, perhaps DQN for simplicity. The neural network would provide a backup &quot;best guess&quot; solution when you could not look far enough ahead in the early stages of the game.</p>
  <p>On a quick search for the true number of states in this game, <a href="http://www.primaryobjects.com/2020/01/26/intelligent-heuristics-for-the-game-isolation-using-ai-and-minimax/" rel="nofollow noreferrer">I found an introduction to using minimax on a smaller version</a> that you may find useful.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-06T23:39:03.833Z
Answers.Text: How about Monte Carlo tree search? Either way no matter the method I need a way to embed the state into a key. Any suggestions? Also I believe representation is 49*48*2^47
Answers.UserDisplayName: user8714896
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T01:57:44.233Z
Answers.Text: Also why do you think Value Iteration will work? It should be able to handle this? It'll just take a long time.
Answers.UserDisplayName: user8714896
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T09:05:27.877Z
Answers.Text: @user8714896 Regarding 48*49 yes that's a better upper bound for that part of the state  space, but it is awkward to encode and not worth the effort for the space it saves (as per my second paragraph). MCTS would be fine, as would many other approaches, I just suggested a couple. Regarding value iteration "it'll just take a long time" - do the maths and you will see you need memory space of thousands of terrabytes. If you can arrange that, then yes it will just take a long time (years on current CPUs)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T10:34:37.070Z
Answers.Text: actually what stops MCTS from not requiring more space than in computationally feasible? Is there just a depth cut off? If you don't have a horizon it can take as much space or more than value it because you're also storing # of visits and relations between child states and parent.
Answers.UserDisplayName: user8714896
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T11:53:40.553Z
Answers.Text: @user8714896 MCTS typically only stores a small sub-tree out of the whole game tree, even with the evaluation horizon being the end of the game.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T13:18:35.893Z
Answers.Text: but it's not guaranteed to be of a reasonable computational size cause part of the learning is expanding nodes unless there's a guaranteed with UCB that it'll stop at some point due inadvertently pruning states not worth remembering.
Answers.UserDisplayName: user8714896
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-07T13:48:39.623Z
Answers.Text: @user8714896: You have a lot more control in MCTS over the size of the space explored. It's definitley more feasible than value iteration for your problem. I see you have asked another question about MCTS, so perhaps try to clarify there or in a new question.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-06T21:04:42.953Z
Answers.LastActivityDate: 2021-02-06T21:15:23.173Z
Answers.LastEditDate: 2021-02-06T21:15:23.173Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm trying to think of how I can embed a game's state into a unique key value. The game I'm specifically working with is Isolation: <a href="https://en.wikipedia.org/wiki/Isolation_(board_game)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Isolation_(board_game)</a>. The game state has the coordinates of player 1's pawn, coordinates of player 2's pawn, coordinates of free spaces and coordinates of already used spaces. Is there a way to embed this into a unique key value? My plan is to generate a dict and use that for value iteration with RL to learn the optimal value function for every state.</p>
  
Tags: <reinforcement-learning><game-ai>
Title: Embedding Isolation game states into key values for RL
UserDisplayName: user8714896
ThreadText: # Embedding Isolation game states into key values for RL
  
  (Asked by: username_0 on 2021-02-06)
  
  I'm trying to think of how I can embed a game's state into a unique key value. The game I'm specifically working with is Isolation: <https://en.wikipedia.org/wiki/Isolation_(board_game)>. The game state has the coordinates of player 1's pawn, coordinates of player 2's pawn, coordinates of free spaces and coordinates of already used spaces. Is there a way to embed this into a unique key value? My plan is to generate a dict and use that for value iteration with RL to learn the optimal value function for every state.
  
  **Tags:** reinforcement-learning, game-ai
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-06. Score: 1
  
  I think that there are too many game states in that game for you to use value iteration. The upper bound for a simple concise representation would be $49^2 \times 2^{49}$. That is:
  
  * $49^2$ covering all possible locations of the two players.
  * $2^{49}$ covering whether each square exists or has been removed.
  
  In this scheme, many combinations are not feasible, as pieces do have to be on existing squares and cannot share a space. However, this doesn't drop the number of allowed states by a significant amount (several or more orders of magnitude) that would make it worth a more complex representation, or put the game into reach of dynamic programming solutions.
  
  Potentially, a version on a 4x5 grid would be small enough to fit in memory and be solvable with dynamic programming. That would have a few million valid states.
  
  In terms of an id code, you could use a 64-bit unsigned integer, reserving 49 bits for the existence of the squares, and for simplicity giving 6 bits each to the locations. This would also be a valid state representation for actually playing the game efficiently, most programming languages support the bit manipulations that you would need in order to maintain the representation. However, it would need a separate expanded representation if you were to create neural network features for approximate value functions.
  
  In terms of writing a solver for the 7x7 version, I would recommend combining a look-ahead planner such as negamax, with an approximate neural network-based reinforcement method, perhaps DQN for simplicity. The neural network would provide a backup "best guess" solution when you could not look far enough ahead in the early stages of the game.
  
  On a quick search for the true number of states in this game, [I found an introduction to using minimax on a smaller version](http://www.primaryobjects.com/2020/01/26/intelligent-heuristics-for-the-game-isolation-using-ai-and-minimax/) that you may find useful.
  
  > **Comments:**
  > **username_0**: How about Monte Carlo tree search? Either way no matter the method I need a way to embed the state into a key. Any suggestions? Also I believe representation is 49*48*2^47  
  > **username_0**: Also why do you think Value Iteration will work? It should be able to handle this? It'll just take a long time.  
  > **username_1**: @user8714896 Regarding 48*49 yes that's a better upper bound for that part of the state  space, but it is awkward to encode and not worth the effort for the space it saves (as per my second paragraph). MCTS would be fine, as would many other approaches, I just suggested a couple. Regarding value iteration "it'll just take a long time" - do the maths and you will see you need memory space of thousands of terrabytes. If you can arrange that, then yes it will just take a long time (years on current CPUs)  
  > **username_0**: actually what stops MCTS from not requiring more space than in computationally feasible? Is there just a depth cut off? If you don't have a horizon it can take as much space or more than value it because you're also storing # of visits and relations between child states and parent.  
  > **username_1**: @user8714896 MCTS typically only stores a small sub-tree out of the whole game tree, even with the evaluation horizon being the end of the game.  
  > **username_0**: but it's not guaranteed to be of a reasonable computational size cause part of the learning is expanding nodes unless there's a guaranteed with UCB that it'll stop at some point due inadvertently pruning states not worth remembering.  
  > **username_1**: @user8714896: You have a lot more control in MCTS over the size of the space explored. It's definitley more feasible than value iteration for your problem. I see you have asked another question about MCTS, so perhaps try to clarify there or in a new question.  
  
  ---
  
  