1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 that you may find useful.

$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$ Feb 6 at 23:39
  • $\begingroup$ Also why do you think Value Iteration will work? It should be able to handle this? It'll just take a long time. $\endgroup$ Feb 7 at 1:57
  • $\begingroup$ @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) $\endgroup$ Feb 7 at 9:05
  • $\begingroup$ 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. $\endgroup$ Feb 7 at 10:34
  • $\begingroup$ @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. $\endgroup$ Feb 7 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.