Gym action space for board game with reward function

Question

Im trying to design an openai gym environment that plays a quite simple board game where each player has 16 pieces that are exactly the same in regard to how they can move.

The board is 10x10 and each piece can go UP, DOWN, LEFT, RIGHT, UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT. They can move in that direction as many fields as pieces are in that line, including the piece that moves. So if I want to go LEFT I count all other pieces to my left AND my right add 1 for myself and then go that many fields to the left. The field may be obstructed though in which case the move is not possible.

So my question is: How could I implement an action space for this? Would be discrete with the (sice of the board) * (how many actions[Up, DOWN...]) suitable? And how can I teach the rl AI (PPO2) that a move is not possible? Should I just give a negative reward and give the same state as before?

I would greatly appreciate help :)

Answer 1

Conceptually, the thing you are trying to learn is a graph where each board state is a unique node, valid moves are edges connecting them. Each game is a walk through the graph where players take turns picking an edge, trying to get to one of their win states. Your first order concern is to pick edges such that you maximize your odds of having a path to the win. The second order concern is to sabotage the opponents path to his win.

In reality the tree is huge, and running actual graph algos like breadth first search is unfeasible. You would likely need heuristics. Firstly symmetry can cut it down a few fold, but probably not by orders of magnitude (depending on the exact game rules). A very common strategy is to devise a way of "scoring" the board to figure out how strong is each player's position. This vastly simplifies the search, instead of trying to find a path you just try to go to the best adjacent node, and hope that if you keep doing that you'll automatically get to a win state. This is effectively a greedy strategy, and cannot so gambits by temporarily revealing weakness to trap the opponent. Also, it will only work as good as the scoring heuristic, which may or may not be hard to compose. You could try collecting statistics on past games as a naive way of finding states that seem like they tend to decide the outcome.

A simple extension of the above is to not go to the best adjacent node, but best node within X hops. In chess, I think 3-10 is common. Obviously this exponentially increases computational demands, but also looking further ahead can make traps, feints and gambits available.

You can further cull the tree by distinguishing moves that are simply legal, from moves that are "no brainer" moves. In many games, you may have the choice of dozens or hundreds of legal moves, but most are obviously bad ideas. It's usually not that hard to see that only a few moves are really worth considering, and it comes down to choosing among those. If you can add that to your algorithm (for instance by embedding it in the structure of your graph, eg. the color of edges) that should speed things up.

Ultimately it comes down to layers of heuristics to decide what moves strengthen or weaken your position. There's some obvious, general ones that I mentioned, but you're also only limited by your imagination and insight into the game. Ideally you should have a framework that can easily deal with an arbitrary number of heuristics for any given situation.

Answer 2

You can use each position on the board as an action (100). Then use a mask that will give you only the available positions (from your current position) as possible actions.