2
$\begingroup$

I've been trying to design and implement a DQN agent as an AI opponent option for a math game I've been working on.

The game is a turn-based grid game, where players alternate making moves and combining numbers to reach a target score. The grid consists of n by n numbers, which can only be used once, whereafter they get replaced by None and can't be selected anymore.

I have a method called get_legal_moves that creates the action space, and the state vector is declared as follows: [player_score, opponent_score, self.target_score, self.grid_size, self.agent_player, self.turns_taken, grid/hashed_state]. The part I'm having trouble with is that the grid is filled with randomly generated numbers, and the action space is constantly changing.

I don't have much experience with ML, so converting the features to tensors and having the agent properly interpret it has been a bit of a problem. All of the elements of the state vector are integers, but the grid is a list of lists of integers, or alternatively, a hashed variation.

I skimmed monte carlo trees and other solutions, but I don't really know where to start. I'd like some advice on how to go about building the agent to begin with. I keep hitting tensor matching errors and problems with the action space getting smaller or larger.

$\endgroup$
1
  • $\begingroup$ Hi @X496 and welcome to AI Stack Exchange! If possible, editing this question to have 2-3 paragraphs might help readers digest your question more easily, and it might lead to a faster or even better answer. Great question, and we hope to see more of your questions in the future! $\endgroup$
    – DeepQZero
    Jul 27, 2023 at 14:58

1 Answer 1

3
$\begingroup$

I will try to answer your questions as best I can, potentially building on some of your ideas. Please note that I'm making certain assumptions about how to design the action space because I don't have a complete understanding of how your game functions. Nevertheless, I hope this will aid you in constructing your RL agent.

How to ingest 2d grid data to the network.

I'll start with what I find to be the simplest question: how to prepare the grid values for ingestion by the Neural Network. For this, you would want to vectorize your grid values into a single vector, or in other words, flatten each cell value into a separate and independent feature in the network. Another possibility is to use a convolutional layer specifically for the grid data. As a general rule, if your game has some type of spatial component, it is highly recommended to use convolutional layers. These layers require fewer weights to train and tend to perform better. That's the reason why models like the Original DQN and AlphaGo use Convolutions for their game states.

Handling a Variable Action Space

When creating a Neural Network, the number of nodes in the input, hidden, and output layers remains constant. You could attempt to construct a model that changes its number of outputs or actions, but in my opinion, this would be an overly complex solution. A much better approach will be to list all possible actions in your game (legal and illegal), then apply a mask function that assigns extremely negative values (i.e., $- \infty$) to illegal actions. This means that if the action selection is a greedy one, that will make you sure that those actions are never going to be selected. If you're using an epsilon greedy strategy, you also need to ensure that the randomly selected action does not have a $- \infty$ Q value.

For enumerating all possible actions you must count all the possible actions in the game. If your game consists of a n x n grid I assume that the action space also increases by n. Additionally, you need to take into account the possible numbers each cell can contain, this can be expressed as a set F representing the random numbers that can have each cell.

Size of the Action Space

So as I mentioned earlier, I'm assuming that your action space has a cardinality of $|F| n^2$. For each cell in the grid, you have the possibility of putting any element of the field. Remember that the Agent will have to be trained on a fixed combination of these parameters. This means that for each of these combinations, you will have to make another model with another output parameter. But this doesn't mean that you cannot use the same hidden weights for training on multiple models. This technique is called model pretraining or transfer learning and this has been demonstrated to be very useful in many applications.

Another thing you might need to consider is the size of your action space. You will start to notice that the size of the action space can start increasing very rapidly as you increase the size of your grid. This is because it grows in a quadratic way. Meaning that if the grid is a 4x4 will have 16 cells but if it is a 10 x 10 it will have 100 cells of different options and that number will be multiplied by the elements of possible numbers that can have each cell. Just to give you an idea, the game of GO is a 19 x 19 board leading to a 19 x 19 = 361 action space. As a way of comparison, the Game of GO is considered to be one of the hardest games to master for an RL agent. That's why I will try to limit the size of your grid. Although it always depends on how the dynamics of the game work, and how sparse the reward can be, I think that it works as a very good comparison for your game because of the fact that both are grid-based games with similar properties. But again take this with a grain of salt because, in the end, you are one that really knows how your game works.

In the case that you consider that the action space is too big, you can always use methods of action samplings. Similar methods are used in models like AlphaTensor or Sampled Muzero. In the case of the AlphaTensor model, the action space of the model is approximately 5^12 = 244,140,625 different actions. Although this can easily be a little too far from your action space, it has been demonstrated by these papers (1 2) that sampling a subset of all your action space can be a useful approach to handle big action spaces.

Using Monte Carlos Tree Search

Finally, to address the question related to using other solutions for solving this RL problem. I will talk more about Monte Carlos Tree Search approaches just because I have more experience with these models. I will also recommend you search for feedback on other RL models like PPO or other policy gradient methods. In the case of MCTS, I already reference a lot of models that use MCTS(AlphaGO, AlphaTensor, MuZero). And there's a pretty good reason why. MCTS is an excellent model to use when your state space is too big and you want to implement a planning component. Like in the game of GO, where you have an adversarial player and your goal is to outsmart him seeing various moves ahead of your current state. This is true because MCTS is designed to make beneficial selections by striking a balance between exploration and exploitation. If you're interested, I recommend this lecture by David Silver (Lead Researcher of the AlphaGO and AlphaZero papers). But again MCTS works as a Game Tree Search that is able to solve the problem of exploration vs exploitation in a decent way. In some cases, equally good results can be achieved by simply tuning the hyperparameters of an epsilon greedy strategy with DQNs. Thus, it's important to experiment and choose the algorithm that performs best for your use case. Given said that, by the description of your game, I will recommend you try MCTS for the sake of learning and researching.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to AI Stack Exchange. This is a great first answer! $\endgroup$ Jul 29, 2023 at 8:52

You must log in to answer this question.

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