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

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!