4
$\begingroup$

I am working on creating a RL based AI for a certain board game. Just as a general overview of the game so that you understand what it's all about: It's a discrete turn-based game with a board of size n*n (n depending on the number of players). Each player gets an m number of pieces, which the player must place on the board. In the end the one who has the least number of pieces wins. There are of course rules as to how the pieces can be placed so that not all placements are legal at every move.

I have the game working in an OpenAI gym environment like fashion (i.e. control by step function), have the board representation as the observation, reward function, and the thing I am struggling with right now is to meaningfully represent the action space.

I looked into how AlphaZero tackles chess. The action space there is 8*8*73 = 4672: for every possible tile on the board there are 73 movement-related modalities. So for every move the algorithm comes up with 4672 values, the illegal ones are set to zero and non-zero ones are re-normalized.

Now I am not sure if such an approach would be feasible for my use-case as my calculations show that I have a theoretical cap of ~30k possible actions (n * n * m) if using the same way of calculation. I am not sure if this would still work on, especially considering that I don't have the DeepMind computing resources at hand.

Therefore my question: Is there any other way of doing it apart from selecting the legal actions from all theoretically possible ones? The legal actions would be just a fraction of the ~30k possible ones. However, at every step the legal actions would change because every new piece determines the new placement possiblities (also the already placed pieces are not available anymore, i.e. action space generally gets smaller with every step).

I am thinking of games like Starcraft 2 where action space must be larger still and they demonstrate good results, not only by DeepMind but also by private enthusiasts with for example DQN. I would appreciate any ideas, hints or readings!

Thank you!

$\endgroup$
1
$\begingroup$

Deep Reinforcement Learning is a popular answer to representing (state, action) spaces. Instead of having a fixed table of (state, action) pairs, a deep neural network learns a non-linear mapping of the space. Compared to a table, a deep neural network is a more compact representation and is better able to generalize to unseen pairs.

$\endgroup$
0
$\begingroup$

One way I can think of is to redefine "actions" in a game to make them more fragmented, in such a way that a player has multiple actions per turn. In chess, for example, we can define an action as choosing a tile from which to move, or choosing the motion from the chosen tile, as 2 separate actions.

As an example a turn might consist of the following two actions:

  1. Choose E4
  2. Move forward 2 spaces

That way there are 64 + 73, rather than 64 * 73 possible actions. The transition model would indicate that it's still the same player's turn after a "tile selection" action is done.

Of course, this would require increasing the state space in such a way that you can determine which action is legal. So there's a difference between a board state where nothing is "selected" and the same board state where one tile is selected by one player. In the chess example, this would require 2 more boolean CNN layers, one for each player, indicating which tile (if any) is "selected".

I never tried this myself, and I imagine that this might make the learning slower and more difficult, since it requires a deeper tree in the MCTS for the same set of actions.

$\endgroup$
-1
$\begingroup$

A paper by Google for you: Deep Reinforcement Learning in Large Discrete Action Spaces

$\endgroup$
  • 3
    $\begingroup$ This is lacking details that are normally expected on a Stack Exchange answer. To fix it, please add some relevant details from the paper - i.e. summarise what the paper suggests as an approach for large spaces. Also, it is worth linking the paper directly instead of just giving the name. $\endgroup$ – Neil Slater Jun 13 at 7:04

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.