AI

AI Strategy Modules

Every robot player has an attached strategy module that it consults for all bidding and playing decisions. More concretely, the strategy module is an object whose class extends the abstract class AiStrategyModule and (at least) overrides the functions makeBid() and makePlay(). These functions are allowed to collect and process information about the game and must execute a bid or card play, respectively, on behalf of the player. The intention is for the strategy module to contain all logic relevant to that strategy, making it relatively easy to implement different strategies and test them out, potentially against each other.

Part of my goal for this Oh Hell project is for everything to be done from scratch. So, all of the machine learning is in the Java. General machine learning tools, including neural network models, layers, vectors, matrices, activation functions, loss functions, and some other things like decision trees, bagging models, and gradient boosting models can be found in the ml package. Code that uses these tools for training AI can be found in the aiworkshop package, and the strategy modules themselves can be found in their own packages (e.g., the OI module is in strategyOI).

OI module

Overview

Currently, the default (and most successful) strategy module is the OI module (stands for Overall-Immediate). A high level explanation of the underlying approach to bidding and playing is:

always bid the number that will maximize the expected points, and
always play the card that will maximize the probability of making the bid.

The strategy module tries to accomplish these tasks by estimating and utilizing the following probabilities.

Given a card $c$, define the overall value of $c$, denoted $p_O(c)$, to be the probability that $c$ will win a trick at some point in the remainder of the round.
Given a card $c$ , define the immediate value of $c$ , denoted $p_I(c)$ , to be the probability that $c$ will win the current trick.

Note that there are more conditions on these probabilities, i.e., $p_O$ and $p_I$ take more inputs than just the card $c$ . For instance, it is important what the other players' bids are, what cards have already been played, what the trump suit is, etc. The strategy module estimates overall and immediate values with neural networks, as described in the next section. But, to finish off the overview, I'll now describe how the overall and immediate values of cards can be used to estimate the quantities relevant in (1) and (2).

Suppose our hand has cards

$H=\{c_1, c_2, \dots, c_h\}$ .

Consider some subset $S$ of $H$ of size $s$ . The probability that the cards in $S$ all win tricks at some point in the round and the cards not in $S$ all lose tricks is

$q(H,S)=\prod_{c \in S} p_O(c) \cdot \prod_{c \in H \setminus S} (1-p_O(c))$ ,

where $c \in S$ means the product is over all cards $c$ in $S$ and $H \setminus S$ means the cards in $H$ not in $S$ (note that this assumes the events are independent, which in reality is almost certainly false, but it is a good enough approximation). Going further, given a number $s$ , the probability $q(H,s)$ that we will make exactly $s$ tricks is the product of the numbers $q(H,S)$ , where $S$ ranges over subsets of size $s$ .

Suppose it's our turn to bid. Given a number $b$ , the expected number of points we will make by bidding $b$ is

$\sum_{s=0}^h q(H,s) \cdot Pts(b,s)$ ,

where $Pts(b,s)$ denotes the number of points gotten by bidding $b$ and taking $s$ tricks.

Suppose it's out turn to play a card and that we still want $w$ tricks. Given a card $c$ in our hand $H$ , the probability we will make exactly $w$ tricks from now until the end of the round if we play $c$ is

$p_I(c) \cdot q(H \setminus c, w-1) + (1-p_I(c)) \cdot q(H \setminus c, w)$

by the law of total probability.

Neural networks

The OI module uses two neural networks that estimate overall value and immediate value. They are called OVL (overall value learner) and IVL (immediate value learner) respectively. An OVL-IVL pair is trained for a specific number of players and decks. For the remainder of this section, we will consider the number of players $N$ and the number of decks $D$ (either 1 or 2) fixed. We also define the quantity $H=min(10, (52D-1)/N)$ , which is the maximum hand size. Lastly, $c$ will always denote a card in hand.

OVL

The features and dimensions for the input layer of the OVL are listed below. They are all discrete and encoded as one-hots.

Feature	Dimension
Cards left in hand	$H$
Tricks still wanted (one vector for each player)	$(H + 1) \cdot N$
Number of voids in hand	$4$
Trump not seen	$13D$
$c$ is or is not trump	$2$
Cards not seen in $c$ 's suit	$13D$
$c$ 's adjusted number (explained below)	$13D$
$c$ 's matching copies not seen	$D-1$

$c$ 's adjusted number is a modified version of $c$ 's number that is meant to account for cards already seen (i.e., already played, in hand, or as the flipped up trump card). It can be defined as the number of cards in $c$ 's suit that $c$ will beat plus the number of seen cards that would beat $c$ . For this reason, the OVL (and IVL) will treat consecutive cards in hand as equivalent in a single-deck game.

The output of the OVL is a single value between 0 and 1 estimating $p_O(c)$ . The final activation function is sigmoid, and all others are ReLU.

IVL

To estimate $p_I(c)$ , the OI module first checks if it can definitively say $p_I(c)=0$ . For instance, this is the case when $c$ is not trump and its suit is not the led suit. In single-deck, this is also the case when $c$ is beaten by a card already in the trick. In double-deck, it's more complicated. If $c$ is trump or its suit is the led suit, then the OI module first determines the number of cancels that need to occur among cards already in the trick for $c$ to have a chance of winning. If this number is greater than the number of players who have yet to play, then again we can say $p_I(c)=0$ . If none of these checks pass, then the OI module resorts to the IVL.

The features and dimensions for the input layer of the IVL are listed below. Again, they are all discrete and encoded as one-hots.

Feature	Dimension
Tricks still wanted (one vector for each player)	$(H + 1) \cdot N$
Trump not seen	$13D$
Trump was led	$2$
Cards not seen in led suit	$13D$
$c$ is or is not trump	$2$
Cards not seen in $c$ 's suit	$13D$
$c$ 's adjusted number (see above)	$13D$
$c$ 's matching copies not seen	$D-1$
Cancels required (see above)	0 if $D=1$ , $\lfloor(N-1)/2\rfloor$ if $D=2$

The output of the IVL is a single value between 0 and 1 estimating $p_I(c)$ . Again, the final activation function is sigmoid, and all others are ReLU.

Hyperparameters and training

The OVL and IVL are put into an OI module and are trained together on many games. $N$ AI players are put in a game, all hooked up to this same OI module and feeding data into its OVL and IVL. Since the OVL and IVL are estimating conditional probabilities of a card winning tricks, the "truth" values of these probabilities are set to 1 or 0 depending on whether that card did or did not win the trick respectively. The data used per epoch is always the data coming from some number of full games.

I have trained OVLs and IVLs typically with only one hidden layer. The number of dimensions of the hidden layer is usually set to 40 for OVL and 30 for IVL, though they seem to reach similar accuracy with hidden layer dimensions as low as 10 or even 5.

As the OVL and IVL train, I monitor the performance of the OI module in terms of its average score and the mean squared error of the OVL and IVL. I manually adjust the learning rate and amount of data per epoch accordingly, in between epochs. As learning stagnates, I decrease the learning rate and increases the amount of data per epoch to decreases variance. For $N=5$ and $D=2$ , the OI module usually reaches a competent level of play after around 1000 games.

Navigation Menu

AI

AI Strategy Modules

OI module

Overview

Neural networks

OVL

IVL

Hyperparameters and training

Uh oh!

Clone this wiki locally