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!