How are NNs output setup for games that allow multiple actions each turn and have very large sets of possible actions?

Question

I was looking at an AI coding challenge for a two player game on a 2D grid of variable size (from one game to the next).

Here is a screen shot example of the playfield.

Each player has multiple units on the board. In fact, each tile can hold multiple units and you can move all or a part of those units. Each turn, each player may perform several actions at a time.

You feed your actions to the game engine on one line, separated by a ;

• MOVE amount fromX fromY toX toY.
• BUILD x y.
• SPAWN amount x y.
• WAIT.

Example of possible command sent to the game engine on one turn:

MOVE 2 2 3 3 3; SPAWN 1 6 6; BUILD 1 1; MOVE 1 9 8 9 9; MOVE 3 11 2 12 2

And the very next turn your command might be:

WAIT

And the turn after that

SPAWN 1 6 6; SPAWN 2 3 3

You get the idea. Each turn you can play a variable amount of "moves" or "actions". And, on bigger boards, the number of valid possible actions can be very big.

I was wondering how would one go about dealing with games like these when trying to use a NN to predict the best move(s) to play on any given turn.

I know how I would handle the variable map size in the input, I'd probably just use the biggest possible map size and then pad the input for smaller map sizes. What I'm really scratching my head about is the output.

How would one setup the output layer in order for the NN to output the best set of actions to play on a given turn?

If we structured the output layer to account for each possible actions, whether they are legal or not on the current turn, the layer would be positively huge, wouldn't it? Number of tiles x number of neighbors, and that's just for moves, add to that spawning and building. Oh, and that doesn't even account for the fact that you can move or spawn more that one unit on a tile. How would you even structure that in your output?

I did see this unanswered question Designing Policy-Network for Deep-RL with Large, Variable Action Space which I think might be similar to what I'm asking but I'm not 100% sure as it is using some terms I'm unfamiliar with.

Answer 1

I participated in this contest and ended up 30th (out of ~4500). I used mainly neural network. I split the problem into parts:

• for each my own cell, I ask the NN what to do (build, spawn, move)
• inputs for the NN was mainly the 5x5 square vision around the cell
• there were 2 networks:
  • first network with 2 outputs - if first output is > 0 then build. if second output > 0, then spawn
  • if the above not occurred, second network was responsible for move, 5 outputs (WAIT, N, S, E, W), highest value wins
• for multiple units per cell, I asked the NN several times, each time with the updated inputs as if the move happened

Training was done via neuroevolution, particularly evolution strategies. Personally I don't know (yet) how to train this type of NN by more conventional means.

More details in: https://www.codingame.com/forum/t/fall-challenge-2022-feedbacks-strategies/199055/4

Answer 2

I replied to a very similar question about checkers here.

To summarize, there are two options:

• Have a large policy head that encodes all possible (combinations of) moves. It can be pretty large, AlphaZero for chess had 73x8x8 = 4672 output values.
• View the game in a different way where turns are split into multiple, smaller turns that don't always change whose turn to play it is, and then use a smaller policy head.

It seems like this game is better suited to the second approach.