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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
var solver = new CplexMilpSolver(new CplexMilpSolverSettings { IntegerWidth = 15, Epsilon = 0.1, StoreDebugExpressions = false, CacheConstants = false, StoreDebugConstraints = false }); Console.WriteLine("-----------------------------------------"); var cardsInDeck = 13; var colors = 4; var players = 2; var turns = 3; Console.WriteLine("-----------------------------------------"); |

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:

1 2 3 4 |
var conflictHandId = players; var cardsCount = cardsInDeck * colors; var totalHandLength = cardsCount; var initialPlayerHandLength = cardsCount / players; |

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:

1 2 3 4 |
Console.WriteLine("Create hands"); IVariable[][] hands = Enumerable.Range(0, players + 1).Select(p => Enumerable.Range(0, totalHandLength).Select(card => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray() ).ToArray(); |

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:

1 2 3 |
IVariable[][] handFlags = Enumerable.Range(0, players + 1).Select(p => Enumerable.Range(0, totalHandLength).Select(card => solver.FromConstant(p == conflictHandId || card >= initialPlayerHandLength ? 0 : 1)).ToArray() ).ToArray(); |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Console.WriteLine("Initialize non-empty cards"); var nonEmptyCardsToInitialize = Enumerable.Range(0, players).SelectMany(p => hands[p].Take(initialPlayerHandLength)).ToArray(); foreach(var card in nonEmptyCardsToInitialize){ solver.Set<GreaterOrEqual>(card, solver.FromConstant(1)); solver.Set<LessOrEqual>(card, solver.FromConstant(cardsCount)); } solver.Set<AllDifferent>(nonEmptyCardsToInitialize[0], nonEmptyCardsToInitialize.Skip(1).ToArray()); Console.WriteLine("Make colors not important"); for(int player=0;player<players;++player){ for(int card=0;card < cardsInDeck * colors / players;++card){ hands[player][card] = solver.Operation<Addition>(solver.Operation<Division>(solver.Operation<Subtraction>(hands[player][card], solver.FromConstant(1)), solver.FromConstant(colors)), solver.FromConstant(1)); } } |

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:

1 2 3 4 5 |
Console.WriteLine("Initialize empty cards"); var emptyCardsToInitialize = Enumerable.Range(0, players).SelectMany(p => hands[p].Skip(cardsInDeck * colors / players)).Concat(hands[conflictHandId]).ToArray(); foreach(var card in emptyCardsToInitialize){ solver.Set<Equal>(card, solver.FromConstant(0)); } |

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

1 2 |
List<Tuple<IVariable[][], IVariable[][], IVariable, IVariable[]>> history = new List<Tuple<IVariable[][], IVariable[][], IVariable, IVariable[]>>(); history.Add(Tuple.Create(hands, handFlags, solver.FromConstant(0), Enumerable.Range(0, players + 1).Select(player => solver.FromConstant(0)).ToArray())); |

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:

1 2 3 4 5 |
Console.WriteLine("Force some card initially"); solver.Set<Equal>(solver.FromConstant(1), hands[0][0]); solver.Set<Equal>(solver.FromConstant(2), hands[0][1]); solver.Set<Equal>(solver.FromConstant(1), hands[1][0]); solver.Set<Equal>(solver.FromConstant(1), hands[1][1]); |

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

Okay, now we need to implement history:

1 2 3 4 5 6 7 |
for(int turn=0;turn<turns;++turn){ Console.WriteLine("Turn " + (turn+1)); hands = hands.Select(h => h.Select(c => c).ToArray()).ToArray(); handFlags = handFlags.Select(h => h.Select(c => c).ToArray()).ToArray(); ... } |

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

1 2 3 4 5 |
var isEnd = solver.Operation<Disjunction>(Enumerable.Range(0, players).Select(player => solver.Operation<IsEqual>(handFlags[player][0], solver.FromConstant(0))).ToArray()); var playerWins = Enumerable.Range(0, players).Select(player => solver.Operation<Conjunction>(Enumerable.Range(0, players).Where(otherPlayer => otherPlayer != player).Select(otherPlayer => solver.Operation<IsGreaterThan>(hands[player][0], hands[otherPlayer][0])).ToArray())).ToArray(); var anyoneWon = solver.Operation<Disjunction>(playerWins); |

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:

1 2 3 4 5 6 7 8 9 10 11 |
var previousFull = solver.FromConstant(1); for(int stackCard = 0; stackCard < totalHandLength; stackCard += players){ var newPreviousFull = handFlags[conflictHandId][stackCard]; for(int player = 0; player < players; ++player){ var currentPosition = stackCard + player; hands[conflictHandId][currentPosition] = solver.Operation<Condition>(handFlags[conflictHandId][currentPosition], hands[conflictHandId][currentPosition], solver.Operation<Condition>(previousFull, hands[player][0], solver.FromConstant(0))); handFlags[conflictHandId][currentPosition] = solver.Operation<Disjunction>(handFlags[conflictHandId][currentPosition], previousFull); } previousFull = newPreviousFull; } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
for(int player = 0; player < players; ++player){ var nonEmptyCardsCount = solver.Operation<Addition>(handFlags[player]); for(int card=0; card < totalHandLength;++card){ var wasMiddle = card < totalHandLength - 1 ? handFlags[player][card+1] : solver.FromConstant(0); var matchingCardFromStack = solver.FromConstant(0); for(int stackCard = 0; stackCard < totalHandLength; ++ stackCard){ matchingCardFromStack = solver.Operation<Condition>( solver.Operation<Conjunction>( handFlags[conflictHandId][stackCard], solver.Operation<IsEqual>(solver.Operation<Subtraction>(solver.FromConstant(card + 1), nonEmptyCardsCount), solver.FromConstant(stackCard)), playerWins[player] ), hands[conflictHandId][stackCard], matchingCardFromStack ); } hands[player][card] = solver.Operation<Condition>(wasMiddle,card < totalHandLength - 1 ? hands[player][card+1] : solver.FromConstant(0), matchingCardFromStack); handFlags[player][card] = solver.Operation<IsNotEqual>(hands[player][card], solver.FromConstant(0)); } } |

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:

1 2 3 4 |
for(int card=0; card < totalHandLength;++card){ hands[conflictHandId][card] = solver.Operation<Condition>(anyoneWon, solver.FromConstant(0), hands[conflictHandId][card]); handFlags[conflictHandId][card] = solver.Operation<Condition>(anyoneWon, solver.FromConstant(0), handFlags[conflictHandId][card]); } |

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:

1 |
history.Add(Tuple.Create(hands, handFlags, isEnd, playerWins.Concat(new IVariable[]{solver.FromConstant(0)}).ToArray())); |

Last thing is solving the problem and printing history:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
solver.AddGoal("Goal", solver.FromConstant(0)); solver.Solve(); Console.WriteLine("Game history"); for(int i=0;i<=turns;++i){ Console.WriteLine(string.Format("Turn: {0}, was end in previous {1}", i, Math.Round(solver.GetValue(history[i].Item3)))); for(int player = 0; player <= players;++player){ Console.WriteLine(string.Format("Player {0} won previous {1}", player + 1, Math.Round(solver.GetValue(history[i].Item4[player])))); for(int c=0;c<cardsCount;++c){ Console.Write(string.Format("{0}={1},", Math.Round(solver.GetValue(history[i].Item2[player][c])), Math.Round(solver.GetValue(history[i].Item1[player][c])))); } Console.WriteLine(); } Console.WriteLine(); } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
Tried aggregator 3 times. MIP Presolve eliminated 592648 rows and 197844 columns. MIP Presolve modified 936212 coefficients. Aggregator did 331903 substitutions. Reduced MIP has 747284 rows, 441564 columns, and 2641111 nonzeros. Reduced MIP has 340904 binaries, 100660 generals, 0 SOSs, and 0 indicators. Presolve time = 9.42 sec. (5819.78 ticks) Probing fixed 204695 vars, tightened 101909 bounds. Probing changed sense of 2328 constraints. Probing time = 222.97 sec. (30961.53 ticks) Cover probing fixed 0 vars, tightened 770 bounds. Tried aggregator 6 times. MIP Presolve eliminated 464923 rows and 258349 columns. MIP Presolve modified 139632 coefficients. Aggregator did 66039 substitutions. Reduced MIP has 216323 rows, 117176 columns, and 678023 nonzeros. Reduced MIP has 66827 binaries, 50349 generals, 0 SOSs, and 0 indicators. Presolve time = 6.31 sec. (4297.37 ticks) Probing fixed 7668 vars, tightened 11529 bounds. Probing changed sense of 328 constraints. Probing time = 1.44 sec. (181.69 ticks) Tried aggregator 5 times. MIP Presolve eliminated 84302 rows and 45918 columns. MIP Presolve modified 28823 coefficients. Aggregator did 2657 substitutions. Reduced MIP has 129368 rows, 68601 columns, and 425809 nonzeros. Reduced MIP has 39841 binaries, 28760 generals, 0 SOSs, and 0 indicators. Presolve time = 1.94 sec. (1643.64 ticks) Probing fixed 2178 vars, tightened 2261 bounds. Probing changed sense of 122 constraints. Probing time = 0.38 sec. (50.43 ticks) Cover probing fixed 0 vars, tightened 748 bounds. Tried aggregator 5 times. MIP Presolve eliminated 30210 rows and 16200 columns. MIP Presolve modified 9404 coefficients. Aggregator did 612 substitutions. Reduced MIP has 98549 rows, 51789 columns, and 340338 nonzeros. Reduced MIP has 30469 binaries, 21320 generals, 0 SOSs, and 0 indicators. Presolve time = 1.44 sec. (1212.69 ticks) Probing fixed 2017 vars, tightened 2128 bounds. Probing changed sense of 104 constraints. Probing time = 0.45 sec. (47.20 ticks) Clique table members: 105098. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 2.44 sec. (1697.51 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 11976 0.0000 11 * 0+ 0 0.0000 0.0000 13998 0.00% 0 0 cutoff 0.0000 0.0000 13998 0.00% Elapsed time = 265.00 sec. (58140.64 ticks, tree = 0.00 MB, solutions = 1) GUB cover cuts applied: 6 Clique cuts applied: 2976 Cover cuts applied: 20 Implied bound cuts applied: 3008 Flow cuts applied: 428 Mixed integer rounding cuts applied: 2272 Zero-half cuts applied: 1290 Root node processing (before b&c): Real time = 265.14 sec. (58170.49 ticks) Parallel b&c, 8 threads: Real time = 0.00 sec. (0.00 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 265.14 sec. (58170.49 ticks) Game history Turn: 0, was end in previous 0 Player 1 won previous 0 1=1,1=2,1=7,1=3,1=13,1=2,1=9,1=11,1=13,1=11,1=4,1=8,1=10,1=5,1=11,1=6,1=12,1=5,1=6,1=11,1=5,1=7,1=10,1=7,1=13,1=8,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 2 won previous 0 1=1,1=1,1=12,1=4,1=7,1=6,1=8,1=12,1=10,1=3,1=2,1=9,1=4,1=10,1=1,1=3,1=2,1=9,1=12,1=3,1=4,1=9,1=5,1=13,1=8,1=6,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 3 won previous 0 0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Turn: 1, was end in previous 0 Player 1 won previous 0 1=2,1=7,1=3,1=13,1=2,1=9,1=11,1=13,1=11,1=4,1=8,1=10,1=5,1=11,1=6,1=12,1=5,1=6,1=11,1=5,1=7,1=10,1=7,1=13,1=8,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 2 won previous 0 1=1,1=12,1=4,1=7,1=6,1=8,1=12,1=10,1=3,1=2,1=9,1=4,1=10,1=1,1=3,1=2,1=9,1=12,1=3,1=4,1=9,1=5,1=13,1=8,1=6,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 3 won previous 0 1=1,1=1,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Turn: 2, was end in previous 0 Player 1 won previous 1 1=7,1=3,1=13,1=2,1=9,1=11,1=13,1=11,1=4,1=8,1=10,1=5,1=11,1=6,1=12,1=5,1=6,1=11,1=5,1=7,1=10,1=7,1=13,1=8,1=1,1=1,1=2,1=1,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 2 won previous 0 1=12,1=4,1=7,1=6,1=8,1=12,1=10,1=3,1=2,1=9,1=4,1=10,1=1,1=3,1=2,1=9,1=12,1=3,1=4,1=9,1=5,1=13,1=8,1=6,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, Player 3 won previous 0 0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0,0=0, |

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.