Reinforcement Learning for Fish: a Social, Multiplayer Card Game
Advisor: Dr. Movshovitz
Internship Location: Remote with Professor William Andreopoulos of San Jose State University
Onsite Mentor: Professor William Andreopoulos, Department of Computer Science @ San Jose State University
Reinforcement Learning (RL) is a subset of AI that has long been used to optimize strategy in logic-based games such as Go and Chess. While Fish is a card game with logical components and tactics, gameplay is also affected by the unpredictability of human behavior, through disadvantageous risk-taking for the purpose of deception. In this remote project with assistance from Professor Andreopoulos of SJSU, I will investigate how RL agents can learn and adapt to human behavior as well as uncover new strategies in Fish. Through training an agent on collected real-world gameplay data and in self-play stages, testing different model frameworks and parameters, as well as evaluating results in play against optimal human players, I expect the final model to gain gameplay advantages but not exceed the most skilled human players capable of reading emotional and behavioral cues outside the agent’s view. In particular, I will analyze how the agent responds to unexpected, counterlogical human behavior, with implications in the larger field of socioaffective computing and human-assisting robotic agents.
Project Blog
Post 1: 1: Fish
Wow. I can use style tags in HTML to make the header colorful (hopefully it'll translate when it reaches your screen).
What is Fish?
A card game for a group of 6 or 8. It's part memorization, part luck, and part logical inference that will become quickly obvious as you play a few rounds.
The Deck & The Sets
I always begin introducing Fish by telling you about the cards. In case you're not familiar, a standard Poker Deck has 54 cards, which are the following:
2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, and A, each of which there are four copies of belonging to one of the four suits—Hearts (♥️), Diamonds (♦️), Spades (♠️), and Clubs (♣️). I.e., there's a 2 of Hearts (abbreviated here as H2), of Diamonds (D2), of Spades (S2), and of Clubs (C2). The same is true for 3s, 4s, ... , and As. This is, if you can do the math, 52 cards.
Two special looking cards, the Jokers (🃏). They're typically colored differently, with one being big (abbreviated here as JB) and another small (JS).
In Fish, the 54 cards of the standard deck are divided into 9 sets with 6 cards in each. They are the following:
Four sets composed of the low cards (2-7) of each suit. {S2, S3, S4, S5, S6, S7} would be called the low spades, for example.
Four sets composed of the high cards (9-A) of each suit. Likewise, {S9, S10, SJ, SQ, SK, SA} are the high spades.
One set, known as the eights and jokers, with the four 8s and two Jokers. This set is excluded when playing with 8 players.
Confused yet? Fortunately, remembering the sets is the biggest hurdle for beginners. Here's how gameplay works. The 6 (or 8) players sit in a circle. Players sitting alternately to each other are part of the same team.
Asking
A player is chosen to start (it is minimally relevant who begins). On your turn, you ask a player of the opposing team for a card from the deck, with the very important precondition being that the set of the card you asked for you already have one card from. I.e., you can only ask for the D9 if you already have a card from the high diamonds ({D9, D10, DJ, DQ, DK, DA}) in your hand. As a sidenote, in trolling games, you may ask for a card you already have (i.e. D9 when you have D9). This is prohibited in no-trolling games, which is standard.
If the player whom you asked has the card in their hand, they have to give it to you and it remains your turn and you are free to ask the same player or any other opponent player. If they do not have the card you asked for, it becomes their turn.
Calling Set
When you believe that your team has all 6 cards in a set, you can call set by naming where every card of that set is on your team.
If your team does not have all 6 cards in possession, the set is counted for the other team.
If you incorrectly name the location of a card, the set is counted for the other team.
Your teammates cannot communicate or assist during this process.
When all sets have been called or miscalled (called incorrectly), the game ends. The team with the most sets then wins the game.
Strategies
Some common strategies include:
When your teammates are looking for a card and you have one from the set, you also ask for the same card from that set. That is, unless you have that card in your hand, in which case you can ask for a different card from that set.
As opposed to the previous strategy, not asking for cards from a set to conceal that you have one, when that set is sought after by opponents.
Feint attentiveness or inattentiveness. It tends to make obvious your possession of a set when you seem to pay extra attention.
However, the most effective strategy in Fish tends to be to stay unpredictable—to deceive your opponents into believing you don't have a card while trying to not deceive your teammates, to ask for abitrary, unrelated sets to avoid disseminating information about your hand, or to act aloof about exchanges for a set you have as to not alert your opponents to your possessions. This is why I chose Fish as an reinforcement learning task, to see how well such a data-heavy method can expect and respond to the unpredictable.
Post 2: 2: Data, pt. 1
Okay, so, you are training a reinforcement learning (RL) model to play a card game. What do you need? Well if you know anything about machine learning (which RL is a subset of), you know the importance of data.
Data
Mary is in Kindergarten, and she is learning the names of different shapes—triangles, squares, circles. How? Well, she sees a lot of triangles, squares, and circles, and she is told for each shape the name. Machine learning works the same way—using algorithms, a model fits itself to the data it is fed. Mary learns to perfectly identify triangles she has seen before. But Mary would not be able to name a pentagon—we had never taught her. See, the drawback of ML is that models cannot improvise on tasks it did not receive training data for. So data is everything.
What kind of data do we need to teach an RL to play Fish? Hundreds, if not thousands, of games for the model to observe and detect trends in. Fortunately, we don’t need to record that many instances of real world gameplay. A neat trick with RLs is that gameplay can be artificially simulated via setting up self-play. Here, the RL is given opponents that are copies or variations of itself, and they make decisions independently, returning a lot of insight from the gameplay experiences of each copy.
Yet, it is still helpful to begin with human gameplay. An untrained model does not begin with a foundational sense of reasoning (unless it is pretrained, but that is rather heavy duty). So, in self-play, its decision making policy would begin rather randomly—unproductive to actually forwarding gameplay to a learnable level. Think—before teaching Mary what each shape is, forcing her to guess the name of each shape each time via a random combination of letters. Monkey Shakespeare stuff, will take an absurd number of tries for her to actually hit a correct guess.
Real World Data
So we should start by training our model on some human gameplay. It doesn’t matter if this human gameplay—these human players—play optimally. In fact, it is great if they make unoptimal mistakes so the model learns to avoid those mistakes.
Formatting
I’m using data I recorded, gathering my friends to play Fish and recording video footage capturing each action. Then, I manually transcribe the video footage into a neat text format that I can parse easily using code, and you can find the currently transcribed in my GitHub repository:
Here’s what each line means.
YS:{S9,CJ,H3,DK,SA,S2}
These represent starting hands, players are represented using initials. Here, I (YS) have the nine of spades, jack of clubs, and so on. In this line, the players are listed in seating order, and thus alternating players are on the same team. Players of the same team as the first listed player are the “odd” team, the rest are on the “even” team.
KZ PB H9 0
This is an ask. KZ asks PB for the nine of hearts. the 0 at the end indicates that this ask was unsuccessful as PB did not have the card. If PB did, the transcription would’ve been KZ PB H9 1.
KZ KZ:{HJ,HQ,HK} OZ:{H9,HT,HA} 1
Calling set. KZ calls set and states that he has the jack, queen, and king of hearts, while OZ has the nine, ten and ace of hearts. Again, a trailing 1 indicates success while 0 indicates failure.
4 4
The final score is listed in “odd”-“even” order.
Matrices
However, I can’t just feed this file into an reinforcement learning model. I have to instead encode every piece of information as an array, as the calculations in an artificial neural network run on vector algebra. I will continue explaining my precise methodology for this next week, as I work simultaneously on video-to-text transcription and text-to-model-acceptable-states-actions-and-rewards programming.
Post 3: 3: Data, part 2
Good one. Let’s talk about converting game transcripts to vectors!
Categorical Data
One thing I learned, from my time working with neural networks, is one-hot encoding. Let’s say you are trying to train a model to predict house prices. One feature (factor) you want to consider in your model is whether the residence is single-family, a townhouse, apartment, etc. Say every datapoint fits into one and only one of these categories. How can we represent this numerically? It might be easy to just start assigning IDs to each of these categories.
{
“single-family”: 0,
“townhouse”: 1,
“apartment”: 2,
…
}
Uh oh, problem! A neural network (the underlying structure we’re using for our model) will interpret this as numeric, akin to the degree to which a feature is (e.g. house age, which scales continuously). That’s a nono, because there is no relationship in the degree of category ID to the house price. Here’s what I mean:
You might expect the relationship between house price and house age to be a continuous function, like this.
But the relationship between house price and category index? Something piecewise like this.
Generally, a neural network doesn’t do so good with piecewise inputs. This is where we use one-hot encoding. Instead of inputting category ID as one dimension in our neural network model, we instead spread it out to n dimensions where n is the number of categories.
Suppose the category index is k. Then, the one-hot encoding we use for our neural network would be defined as
, where
Why is This Relevant?
If we recall what information we want to encode:
Hands: YS:{S9,CJ,H3,DK,SA,S2}
Asks: KZ PB H9 0
Calls: KZ KZ:{HJ,HQ,HK} OZ:{H9,HT,HA} 1
None of these are numeric. Players should be easy to represent, one-hot encoded into a vector of length 8. Cards, are a little trickier. We could use a vector of 54 dimensions, one for each card in the deck, but that would get very long very quickly, particularly when encoding calls when multiple cards are involved. Thankfully, we have the power of combinatorics. I’ve instead chosen to use a vector with 9 values to encode the card’s set, and another vector with 6 values to encode the card’s position in the set, according to the following array:
[
["D2","D3","D4","D5","D6","D7"],
["C2","C3","C4","C5","C6","C7"],
["H2","H3","H4","H5","H6","H7"],
["S2","S3","S4","S5","S6","S7"],
["D9","DT","DJ","DQ","DK","DA"],
["C9","CT","CJ","CQ","CK","CA"],
["H9","HT","HJ","HQ","HK","HA"],
["S9","ST","SJ","SQ","SK","SA"],
["D8","C8","H8","S8","*S","*B"]
]
This way, we only really need a vector with 15 dimensions to encode 9x6=54 different possibilities. By combining these pieces of information, we can convert any game into a state of 200x54, where 200 is the number of actions that any player take in an entire game (which is typically 100-120, but given 80 extra rows for backup) and 54 is the encoding for each action.
Next time, let’s talk about the neural network I’ve been working on!
Post 4: 4: Reinforcement learning, part 1
As discussed previously, machine learning approximates a series of computations (a model) that brings us from the value of features (data) to target values (predictions). What are these features and targets in reinforcement learning, when we are teaching a model to play Fish? In reinforcement learning, the information (features) you derive information from are states. As previously discussed, this will tentatively be a 200x54 array encoding the sequence of game events.
Predictions
Before we discuss what our model should predict, let's introduce the concept of reward. The reward should be a quantifiable measurement of the benefit of taking an action. In Fish, for example, reward would relates to the set called, as actions that lead to correctly calling a set also lead to victory. In training data, we set up a reward to be +1 immediately following the action of correctly calling a set and -1 for the action taken which loses a set. We should note that while not every action immediately yields a reward, current actions can yield future benefit, the expected value of which is also quantifiable. That expected value is what we call a Q-value.
In Q-learning, we use the game state (for us, the sequence of events) at a given step to predict the reward of taking any of the actions available to us at a given step. The following action choices we define as available in Fish are as follows:
Whether to call set – available always
Which set to call – available when you choose to call set
Which card in the set to call – available when you choose to call set
Who to ask a card from – available on turn
What set to ask a card from – available on turn
What card to ask – available on turn
Notice there's a hierarchy. Whether you choose to call set unlocks more sub-options. These options are also restricted – you would not be able to ask cards from players with no cards remaining, for example, so those would be masked and unavailable for selection. For each option and sub-option, the model will calculate a Q-value. When we actually use the model, we take action based on which options have the highest Q-value, expected reward, of the lot.
Post 5: 5: Reinforcement learning, part 2
Neural Networks and Loss
So, let me tell you a bit about how our model, the neural network, actually works. You may recall from part 1 that a neural network tries to predict target values from features. Both features and target values can be represented as a scalar in ℝ or an array of ℝ.
A neural network diagram I made for some other project. Here, the features are represented as a one-dimensional array (vector) of all the x variables, commonly known as X. The target is y.
A neural network is composed of hidden layers (the columns of a in the diagram above), which are each connected by a number of neurons (each line connecting two circles). The neuron, modeled after biological neurons, is a linear function that takes an input value, say, s, multiplies it by a weight, w, and adds that product by a bias, b, giving ws + b. Where multiple connectors meet at a node of a, the products of weight and input are summed, and the bias is introduced to that sum rather than to each individual input product.
The process of gradient descent, which I will not attempt to prove, essentially modifies over many adjustments the values for w and b for each neuron in the hidden layer to create a model which most closely predicts outputs for given inputs in the dataset provided. As a reminder, in our situation, the neural network will try to generate Q-values which most closely represents the reward of choosing a given action based on the current state.
In order for those adjustments in gradient descent to occur, we must first calculate the delta between the "ideal" Q-value Q and the predicted Q-value, Q̂. This is known as the loss. Intuitively, the greater the loss, the more the adjustment to the weights and biases should be during gradient descent.
Here is how we calculate the "ideal" Q-value:
r is the reward earned by taking the given action. This is typically 0, as rewards only have nonzero values on set calls, a small proportion of all the actions that occur in a game. γ (gamma) is the learning rate, which controls the precision of gradient descent and is a typically standardized constant we don't worry about just yet. γ is multiplied by the maximum Q-value predicted of subsequent actions of the next step after that given action was chosen. This term allows the reward to be passed up the step history, so although there are only rewards at certain intervals, the actions of the steps in between also become partially attributed with that reward, allowing for a greater amount of foresight.
With the ideal Q and Q̂, we can use the mean squared error formula to calculate a positive delta, substituting Y and Ŷ for Q and Q̂ to get our loss:
With this loss, the model then backpropagates to fit our data.
Post 6: 6: Reinforcement learning, part 3
It's been a little while since I've written anything worthwhile here, so I'll try to be less preachy and just describe what I've been working on.
The Data
It is improper to describe the training process as broken down into two stages-one on existing data, one on self-play-because the model could suck at either or both tasks and then you'd have to fix the model and rerun it through both stages again. This would repeat as you gradually adjust the model to something functional.
I've got 10 rounds of real-world gameplay, amounting to the experiences of 68 players, each of which could be leveraged. But I've also introduced a method of data creation-shuffling. Referring to our discussion of data encoding and representations, I can shuffle the set and ordering for cards in a set, values which are used to generate these encodings, to create a maximum of 9!×(6!)⁹ permutations of a single game. Additionally, I can shuffle the seating order of a player's teammates and opponents, which doesn't affect game play but allows the game to be generalized further. So out of the 68 experiences, we can create a near infinite amount of data for real-world training.
Furthermore, I have created the pipeline for self-play, which is as follows:
A game object is created and hands are dealt randomly.
A player is arbitrary designated to first. It is considered their turn.
After any action occurs in the game, a single agent is prompted to generate action Q-values for each player based on the information available to that player.
If any players wish to call set (the Q-value for calling set is greater than that for not calling set), then that player is allowed to call set, with the set and the card assignments determined by the other Q-values. If multiple players wish to call set, the player with the greatest set-calling Q-value is given priority.
If no player is calling set, the player whose turn it is will ask for a card from an opponent according to the Q-values generated for asking.
The player whose turn it becomes is then reassigned if necessary (i.e. if it becomes the opponent's turn).
Steps 3-6 are repeated until one team is completely out of cards, after which the remaining players must call set.
Helping
During self-play, the model might begin poorly, picking actions not considered valuable (i.e. asking for the wrong card repeatedly). However, in the set of all possible actions an agent can take, the set of actions which are actually helpful to earning sets is very small, and it is foolish to expect to stumble upon them by chance. As such, I've included a component of "helping" the agents by overtaking the agent's intended action and interjecting instead with choices that could help the model learn:
Helping the agent actually obtain a card from the opponent, rather than asking for a card the opponent doesn't have. The frequency of this can occur at a rate of 0.2-0.8 depending on settings.
Helping the agent call set correctly, when a team has an entire set in their combined hands (a set is "monopolized"). This is set to trigger whenever a team obtains an entire set.
These are essentially training wheels for teaching via self-play, the frequencies of which could be reduced over time as the model gains more innate ability.
The Model
I went and reworked the model. The problem? It seemed too big a leap to get from game events → action directly, even with many hidden layers ("thinking processes"). In an actual game of fish, players typically use game events to infer other players' hands, and based on the inferred hands, decide what action to take next. This is adds an intermediate step: game events → other player's hands → action. So if we have our agent follow this intermediate step, it could potentially produce more informed actions. We thus break our one singular Q-network into two separate networks:
One LSTM neural network which takes the sequence of previous game states and outputs a prediction of other players' hands as an 8×54 array. This is essentially a classification task, categorizing each of the 54 cards into one of the 6 or 8 players.
The LSTM allows the neural network to take every event that has happened in the game prior one at a time, rather than all previous events at once. It then updates its hidden state after each time step (event) to track sequential information.
Another normal Q-network which outputs the action Q-values, but with the input instead being that 8×54 array encoding other players' predicted hands (during testing) or actual hands (during training).
Thus, to return the Q-values after any event, the LSTM hand-prediction model is applied first, then the output of that is fed into the revised Q-network.
Post 7: 7: Reinforcement Learning, part 4
Right now, I’m debating on whether, during training, the Q-network should be trained on producing Q-values based on the hands the LSTM predicted, or the hands the players actually held.
Using predicted hands:
CON: More logistically challenging to implement
CON: Predictions ould have additional noise which may distract from the relationship between players’ cards and Q-values
PRO: Uncertainty can be learnt as a factor in decision-making
Using actual hands:
PRO: Do not have to use new implementation
PRO: Allows Q-values to learn precisely relationship between cards and rewards provided when asking & calling
CON: Does not reflect uncertainty. This leads to some problems, such as calling set when uncertainty is high.
So I ended up using predicted hands instead, and it works well enough.
Also, my model still doesn’t know how to call set. I’m thinking I’ll just collect all the memories where the model incorrectly/correctly called set and provide it a designated training session on that instead. Other than that, it works surprisingly well—it has an average of around 35% validation accuracy on correctly determining the location of each card (given that in an actual game, you wouldn’t know everyone’s cards anyways), and it’s also able to learn pretty well based on its hand predictions where they can successfully ask for cards. In a passing observation, its weak spot is coordinating with teammates to obtain all cards in a set, as the mechanism for calling set isn’t well developed yet. In the last stretch, I will try to refine that process, and move onto evaluating the model against human players.
Post 8: 8: Reinforcement Learning, part 5
So I wanted to test how the model would perform in a game with real players. Needless to say, it would’ve been much easier to show some metrics about how the model would’ve performed relative to itself before training (i.e. randomness). Yet, I still chose to take it against human players, and it performed terribly—somehow unable to dynamically choose cards to ask (this could either be due to a system bug or because the model was truly bad), causing it to repeatedly ask for the same card over and over again—and also having an insane urge to call set even when it doesn’t know what to call. So when I gathered five of my friends to play against it, we lost 9-0, with the agent having given away all its cards. So I went back to the drawing board and redesigned the entire architecture for picking actions given predicted cards.
The main idea is to create a neural network that is set- and player-agnostic. The problem with the previous model is that it had to learn the relationship between each card in the hand predictions and the card its asking for and player its asking form individually, for all cards and all players. It wasn’t able to generalize these relationships between input and output across all cards and players, which diminishes the usefulness of single datapoints. The new design, hopefully, does exactly that:
Let’s break it down!
x1 = x.reshape(-1, 1, 8, 54) reshapes the input, an array with dimensions of -1x432 (here, -1 substitutes for the arbitrary batch length) into one with dimensions -1x1x8x54. The first layer, misnamed as fc1, samples from each 8x54 matrix of the -1x1x8x54 at widths of 6 and outputs a single such value for that segment of 8x6, giving a matrix of -1x1x9 (there are nine 8x6 segments in an 8x54), which is then reshaped into -1x9 by dropping the extra dimension. Hopefully, this represented some information about the ownership of each set. This array of length 9 is then used to determine whether to call set! For a given call, the assignment of who has which card is produced via selecting the 8x6 segment corresponding most significant set of call_set from the predicted hands and doing matrix multiplication between the transposed 6x8 with an 8x4 linear layer to produce another matrix of 6x4 which hopefully corresponds to something about the ownership of cards for players on your team. The same concept applies for asking for cards.
To summarize, prior to these improvements, the input was a flattened -1x432 and we feed that directly into some layers to give another flattened -1x2, -1x9, -1x24, and -1x216. Not very smooth or demure. Now, its a dimensional -1x8x9x6 that drops and flattens dimensions to transform into -1x2, -1x9, -1x6x4, and -1x4x9x6. This allows for greater generalization, which should help the model learn better! And it seems to, as well—the model has demonstrated set-calling capabilities for the first time!
Post 9: 9: Reflection
Blog 10! Here’s what I’ve learned, as it relates to larger patterns within myself, during my senior project.
Some people say that there’s no end to optimizing an AI model (or the software development cycle, in general), and they might say I fell into that trap when pacing my senior project. However, I propose an alternative issue that hindered progress—my unwillingness to write code.
Unwillingness to write code? Isn’t your entire project writing code? You may ask. Well, yes, it is writing code. But a lot of machine learning isn’t just implementing the model architecture with lines of code, but rather adjusting the parameters within that code. How many epochs will you train your model on? In those epochs, how many datapoints will comprise a single batch? What is your dropout rate? What is the patience of your learning rate optimizer? These are just a segment of the features, when tuned, which can produce vastly different results for model performance.
This is the trap I fell in.
You see, at many points in model development, I had, through output inspection, determined fundamental model problems that could be resolved with a model redesign—set- and player-agnosticism, a weakness in LSTM memory, or greater logic in preengineered features—that I chose to delay the development and evaluation of. This is because, as I will realize later, I don’t like coding.
Specifically, I don’t like having to build code to implement new features. There is so much mental burden in typing out the algorithms pertaining to a feature. I can have a vision for how the algorithm would be implemented in mental abstractions—the firing and connection of neurons—but having to write the code itself is boring.
Contrast this with my enjoyment of debugging. Perhaps from years of competitive math training, I have grown accustomed to solving problems. My simian brain gains a particular neuronal activation successfully resolving bugs that cannot be replicated with any fulfillment of implementing a new feature. When I spoke to my other software friends, they could not disagree harder—their frustrations when debugging is to me a practice of grit, an exercise of intellect.
My habit of tuning parameters was born not from an obsession with parameters, but rather, a boredom with coding itself. Ironically, I do enjoy devising clever structural solutions to the problems my models faced. From breaking down the task of one model into two, to devising a system that’s agnostic to set or player; these small tricks are the second product of my competitive math background. Debugging isn’t the only outlet for problem-solving; these designs are, too. Perhaps that’s what I’ve graduated into: from math proof writing to AI research; from math solution checker to programming debugger.
I shouldn’t romanticise my disdain for implementing new features. After all, coding is a necessity in every line of work from every possible branch of my future. Thankfully, I also avoid vibecoding due to a mix of informed and biased prejudice, so I am forced to write my own code, and in turn, conquer that disdain.