How to deal with a huge action space, where, at every step, there is a variable number of legal actions?

Question

I am working on creating an 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 \times 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's gym environment (i.e. control by step function), have the board representation as the observation, and I have defined the reward function.

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 possibilities (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!

Answer 1

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.