2
$\begingroup$

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. Game played on a 2D grid

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.

$\endgroup$
2
  • 1
    $\begingroup$ I'd suggest going over some basic concepts in reinforcement learning, which is a branch of machine learning that is probably most suitable for your problem. a good start may be spinningup.openai.com/en/latest $\endgroup$ Dec 25, 2022 at 10:08
  • $\begingroup$ This looks great, thank you. So far, I've had a hard time finding learning resources that are at the level I need. Everything is either super basic or just a bit too advanced and mathy, expecting prior knowledge or experience that I don't possess. $\endgroup$ Dec 25, 2022 at 14:05

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ The second approach is interesting. So you'd basically have the combination of actions for a real meta turn, be the combination of individual actions produced in a series of "fake" mini turn. That could work. I guess you'd need to add some kind of stopping action to know when to exit fake mini turns. Thanks for the idea. $\endgroup$ Jan 2, 2023 at 19:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .