1
$\begingroup$

I'm quite new to reinforcement learning. I've been training the model for the following problem but the mean reward is stuck.

  • In a 5 by 5 board, each position can contain a card with a color (0-4) and a value (0-9).
  • Some initial cards, all distinct from each other, may be on the board.
  • In each round, a card not on the board is chosen with uniform distribution.
  • The player has to place this card in an empty position before the next card is chosen.
  • When all positions are filled, the game ends and the final score is the sum of all points of each row, each column, and each of the two diagonals, where the points are calculated as follows (order does not matter, e.g. AAABB=ABABA, 12345=23415):
Combination Points Colors Values
Straight flush 30 All identical All consecutive
Straight 15 Not all identical All consecutive
Flush 14 All identical Not all consecutive
Five of a kind 28 AAAAA
Four of a kind 16 AAAAB
Full house 10 AAABB
Three of a kind 6 AAABC
Two pairs 3 AABBC
One pair 1 AABCD
Nothing 0

The goal is of course to get a score as high as possible.

Question: How should I write the reward function to teach the agent the rules?

I used invalid action masking, so no invalid actions can be taken. However, it's still hard for high-score combinations to randomly show up. I tried setting reward to be the points possibly added due to the placed card (like if the placed card can form a pair with another one in the same row, add some points based on how much point a pair is rewarded in the final score), and reward 100*(final score) at the end, hoping the agent to learn that the final score is the most important, but the mean reward was not improving even after 2 million timesteps.

I use MaskablePPO with MlpPolicy (alias of MaskableActorCritic) from sb3-contrib. I represent each card as an int8. The upper 4 bits representing the color and the lower 4 bits represent the value.

The observation space I use consists of the card to be placed, the cards on the board, and all cards not on the board. I'm wondering if I should include cards not present in the observation space. I tried to exclude it but it does not change the results much.

Apart from direct answers, any pointers/reference would be much appreciated.

$\endgroup$
4
  • $\begingroup$ Is it a game that you can links the rules for? Your description is fine as-is, but the scoring rules may allow someone to try an experiment. One important detail: Is it possible to calculate a score for the incomplete board using the standard rules? As you have a large state space, and a policy network, I am assuming you are using a neural network. It may be worth explaining what you have tried there, and how you convert state to the representation used by the network. For instance, putting the raw 0-9 values in grid positions to feed into a CNN may not work well. $\endgroup$ Apr 26 at 7:25
  • $\begingroup$ @NeilSlater I updated some info. I am not using a CNN tho, because stable-baselines 3 only allows CNN to work with images. I'm using an actor critic policy. $\endgroup$
    – durianice
    Apr 26 at 17:00
  • $\begingroup$ Thanks for the updates. Are the scores assigned according to strict sequence match ie. a straight has to have values in order in the horizontal (left to right) or vertical (top to bottom) row? Or is it enough to just have a set of consecutive values e.g. reading to to bottom the multicoloured array [6, 5, 8, 7, 4] would be a valid straight? $\endgroup$ Apr 26 at 17:43
  • $\begingroup$ @NeilSlater Order does not matter. Updated. Thanks for pointing out. $\endgroup$
    – durianice
    Apr 26 at 18:15

1 Answer 1

1
$\begingroup$

I would recommend having the reward as the increase to score caused by adding the card in the chosen location. You could optionally include calculations based on partial rows for pairs, three-of-a-kind etc. I do not think you should grant a different final reward for the end score, and definitely not some large difference, as the gradient for a large difference may swamp the networks (unless you also drop the learning rate, but then the smaller early values will not get learned from).

I do not think that your focus should be on clever manipulation of reward signal. It is likely that looking at other things related to this problem will give you better impact.

First you should look at your state representation. If you are feeding the int8 values directly to a neural network, then this is very unlikely to work. Instead, you should use a short vector for each card you want to represent - of either 6 or 15 elements. You should be one-hot-encoding the colour for each position. You may find one-hot-encoding the value also helps, although that is trickier - if you don't one-hot encode, then you should scale the value e.g. $(v - 5)/3$ to keep it in range for best neural network learning.

The card in hand, about to be placed, should be part of the state. So far, before any feature engineering, that would give you a vector of at least 26 * 6 = 156 dimensions, but you could take that further.

If possible, use afterstates instead of enumerated actions. That may not be possible if you are using a library that expects enumerated actions. You probably won't find a version of Actor-Critic with afterstates because the Actor would need to express a probability distribution over the afterstates, which is awkward to do. You may be able to set the Actor to use enumerated actions and the Critic to score advantage based on afterstates though.

To help the agent, do some feature engineering to add summaries of each possible line to the state (so a summary for each of the 12 lines). One important feature will be whether that line is complete or not - if it is complete, no more reward is possible from that line (perhaps a scaled "how many spaces left" counter would work here). Other features that could be useful are a "bag of colours" and "bag of values" i.e. one-hot-encoded list of current variation in that row - such a summary makes it easier for the NN to tell whether an x-of-a-kind or flush or straight are possible.

In theory you could also pre-calculate the immediate reward from placing the card in each position, making that part of the state (another 25 features). That is so the agent is not trying to predict this value - it is hard for the NN, but easy for the game engine and not "cheating" at the game by e.g. peeking at the next card. That should allow the NN to use more of its capacity for planning ahead and statistically gambling on what might be available in future, which is perhaps the more interesting aspect of this game.

$\endgroup$

You must log in to answer this question.

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