## Help

### Instructions

On your turn, hover over a card (or tap on a mobile device) to zoom in and see the card better. You can do this for your own cards as well as others' cards and cards on the table, but you can't see the cards in other players' hands. Click a card (or double tap on mobile) to play it.

### Rules

Black Queen is a card game similar to hearts. I found some information on "Black Queen" and "Black Lady" online, but the rules seemed slightly different from those here. It is usually played with four players and two decks, but with modifications can be played with other numbers of players. There are no jokers.

Each player has a set of cards face up, a set of cards face down below those, and a set of cards in the hand. All players can see all the face up cards, but can only see their own hand cards. Nobody can see the face down cards.

On your turn, there will either be cards on the table from earlier players, or there will not be. If there are no cards on the table, you can play any of your hand cards or face up cards.

Generally, if there are cards on the table from earlier players, you must put down a card of the suit that was first put on the table. However, if you have no cards of that suit, you can play any card. Once all players have put a card on the table, the cards on the table are kept by the player who played the highest card that matches the suit of the first card on the table. If multiple players played the same level card, the cards on the table go to the player who played last of these. Ace is the highest value card.

After the cards on the table are kept by this player, they are no longer in play. All players flip over any face down cards that may have been uncovered by playing face up cards in the previous turn. Then the player who just took the cards will play the next card, and can play any card as there are no cards on the table anymore.

This continues until all cards run out. At this point, each player counts the cards they have kept from the game. Each heart counts as -1 point, and each queen of spades (the Black Queen) counts as -12 points. If a player has kept no cards, their score is +10. If a player has kept some cards but otherwise has no negative points, their score is +5. If a player has kept all of the negative points, their score becomes positive instead; so a -50 from two decks becomes a +50.

You generally want to avoid receiving cards, especially the hearts and queen of spades. However, towards the beginning of the game, it is a good strategy to play higher cards if possible so that you won't be stuck taking the negative points later in the game.

There is one deck for every two players, usually two decks for four players. If there is an odd number of players, some cards must be removed. For three players, 52 is not divisible by 3 but 51 is, so I remove the 2 of diamonds (one of the least significant cards). For five players, 104 is not divisible by 5 but 100 is, so I remove both 2 of diamonds, the 2 of clubs, and the 2 of spades.

## AI

### Principles

Before making this, I had made an AI for chess. The classic technique for
chess is a **minimax** method. I applied that here too. However,
chess is a **perfect information** game. You can see all your pieces
and all your opponent's pieces. Black Queen involves some probability, as
the cards are shuffled randomly, and you don't have perfect information.

The information you have in black queen is:

- All face up cards
- Your hand cards
- All cards in the game (You know the 52 cards in a deck, you know how many decks are in the game, and you know the removals if there are an odd number of players)
- Which of these cards have been played (counting cards in two decks can be hard for humans, but the information is out there to get without cheating, so I allowed it for the computer)

The information you *don't* have in black queen is:

- All face down cards
- Your opponents' hand cards

An AI can use the information that's available in order to make educated guesses about the information that's not not available.

### Strength 0

AI strength 0 simply makes random moves. It is interesting to see to what extent Black Queen is a game of chance.

### Strength 1

Strength 1 is an improvement on Strength 0 because it tries to play in its best interest. However, it does not use any of the information that it doesn't have direct access to. In other words, it plays as if the cards it can see are the only ones in the game.

The Strength 1 AI first looks at each of its valid moves. For each of these
moves, it tries to assign a **worst case** (*minimum*) scenario. Then among
its valid moves, it selects the one with the **highest** (*maximum*)
worst case, so that even if its opponents play in its worst interest,
it will avoid too much loss. This combination of *minimum* and
*maximum* is where the word *minimax* comes from.

The evaluation of a worst case scenario is based on the number of negative points in the round, with some modifications:

- If the AI sees that the negative points are going not to itself but to another player,
it considers them as
*positive*points. In other words, it actively seeks to harm other players, while preserving itself. - The AI takes into account the +5 and +10 from avoiding all cards and points (see rules above).

There are also a few parts of the AI's strategy that see beyond the current move to think long-term.

- The AI prefers to play a higher valued card if possible, especially early in the game, as long as it doesn't conflict with other goals. This part of the AI's strategy sees beyond the current move, as it is avoiding taking negative points later on.
- As an extension of the above point, the AI gives further preference to playing the king or ace of spades when possible, in order to avoid the black queen.
- Since the +5 and +10 from having no negative points or no cards are rare by the end of the game, the AI only counts them as +0.25 and +0.50.

### Strength 2

Strength 2 is a further improvement on Strength 1 because it takes into account possibilities for the opponents' hand cards.

Remember how the Strength 1 AI plays as if the cards it can see are the only ones in the game?
This means that if it sees that a certain player has no cards face up for a certain
suit, it will simply assume that the player has *no* cards in that suit.
The strength 2 AI instead calculates a probability that the player actually has no cards
in the suit. Let \(A\) be the event that the player the AI is looking at
actually has no cards in the suit, and therefore can play any suit. The probability is
approximately
$$p(A) = \bigg( 1 - \frac{S}{N} \bigg)^n$$
Where \(S\) is the number of unplayed cards in the suit that are invisible to the AI,
\(N\) is the total number of unplayed cards that are invisible to the AI, and
\(n\) is the number of cards that the player the AI is looking at has in the hand.
This is different from the Strength 1 AI. If the Strength 1 AI saw no face up cards of a
suit, it assumed that the probability of not having the suit was just 1.

Checking some special cases for this formula, we see that if \(S=N\), meaning all invisible cards are of the correct suit, the hand cards must all be of this suit and so the probability of having no cards in the suit really is 0. If \(n=0\), the probability of having no cards in the suit is 1, because there are no hand cards and the AI determined before using this formula that there are no cards of the correct suit that are face up.

Once the AI has figured out the probability of whether or not the player it is looking at has a card of the correct suit, it analyzes the hand cards themselves. It considers all the cards it can't see that haven't been played yet. Let \(C\) be the event that the player the AI is looking at has any given one of these cards. The probability is approximately $$p(C) = 1 - \bigg(1 - \frac{c}{N} \bigg)^n$$ Where \(c\) is the number of this type of card (such as three of hearts) that haven't been played yet and that are invisible to the AI, and the rest of the variables are the same as before.

Both of these approximations work best when \(N \gg n\), and \(N \gg c\).

If this invisible card is of the correct suit, or if there are no cards on the table yet, the player the AI is looking at can play any suit. This means the probability that this card can actually be played is simply the above probability. Otherwise, the AI can only play if it has no cards of the correct suit. We must multiply by the probability that the AI has no cards of the correct suit, which we calculated earlier.

Now the question is how the probability affects decision making. Consider this scenario:

- There are two cards on the table, both low spades.
- The AI is about to put the third card on the table.
- The player after the AI has only one hand card.
- There are no black queens visible to the AI.

It depends on whether or not the card in the next player's hand is a black queen or not. The probability of this occuring can be determined using the formulas above; let's say it's 0.3. So there is a 0.3 chance of the AI losing 12 points by playing the ace of spades. At first, this looks like an expected value of -3.6. Intuitively, however, this scenario seems more dangerous than expecting to lose 3.6 points due to hearts. I think this has to do with the "volatility" of the move, as in finance: there is a wide range of what the outcome could be, which is not a good thing.

Therefore, I made the AI multiply not by the probability itself but by the square root of the probability. \(-12 \sqrt{0.3} = -6.6\), so the AI will be more concerned about playing the ace than if it expected to take 3.6 hearts, but not quite as concerned as if it knew for a fact that the next player had a black queen.

Using the square root was somewhat of an arbitrary decision, based on some intuition rather than rigorous math. If I were to do the math properly, I think I would use probability theory to try to minimize the standard deviation in addition to maximizing the expected value. However, I think I would need to learn some more statistics first.