ILP Part 68 — War card game

~ afish

This is the sixtieth eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to implement War card game in ILP. I assume you know the rules so let’s jump straight to implementation.

First, let’s define solver and couple configuration variables:

We use regular deck with four colors (lines 11-12) to make things faster. We play the game between two players (line 13) and we play three turns only (line 14).

Next, we define couple useful variables:

We base our model on three hands (numer of players plus one). Each hand holds exactly 52 cards (full deck). Third hand is used as a pool for conflicting cards (when there was a tie).

We create hands:

Each card in a hand is a positive or zero integer. We number cards from 1, 0 means missing card.

We also define couple useful flags saying if card is present or not:

You can see that initially only half of a hand is non-empty. For last hand (war pool) all cards are missing.

We now randomize the initial state:

So we take cards and shuffle them, and then we divide each number by four (number of colors) to effectively ignore colors and keep ranks only. We also need to initialize rest of hands for missing cards:

Great, initial state is ready. Now we just store the history:

Our history is a four element tuple. First element is hands, then we have flags, third element is a binary flag saying if the game ended in previous turn, last element is list of flags if player won in previous turn.

We can also enforce some initial state:

So first turn will be a tie, second turn will be winning for player one.

Okay, now we need to implement history:

We iterate over turns and start with copying the state. We now calculate the end condition and who won:

Nothing special here. Game ends when and of any player starts with zero (no more cards). Winner of current state is a player with strictly greater card. You can modify the conditions here to allow for more sophisticated rules etc.

Now, we need to take one card from each players’ hand and move it to the holding pool in order:

We maintain a state previousFull indicating whether previous slot was full (this is to track previous ties).
Next, we iterate over players and then calculate the stack card in line 6. If this stack position had some card previously then we just reuse the card. Otherwise we check if previous position was non-empty – in that case we are at the end of stack and here is the spot where we should put current players’ cards. Finally, we update the flag tracking the end of the stack.

Next, we want to move cards in players’ hands and get cards from the stack for the winner:

We iterate over players. For each of them we calculate how many cards he had at the beginning of this turn. We then iterate over all cards for given player. We first check if this card was somewhere in the middle of the hand (line 4). Then, we want to find card from the holding pool which should land here (lines 6-17) – for that we calculate how far we are from the last non-empty slot in player’s hand, then find matching card in the pool by comparing indexes, and then get the card. Finally, in lines 19-20 we update the card and the flag if there is card in the slot or not.

Lastly, we need to update the holding pool:

If anyone won the turn then the holding pool is empty, otherwise we just keep the pool. Similar for flags.

Finally, we store new state in the history:

Last thing is solving the problem and printing history:

History is in the form wasThereACard=cardRank. You can see the output for three turns for full deck for two players:

It took almost 5 minutes and 341k variables to calculate. Obviously, this can be optimized (CPLEX presolves it pretty well) but it’s still enormous.

Since now we have the engine, we can start playing with interesting conditions. For instance, we can minimize number of turns or look for initial shuffles leading to some specific situation after turns.