File CoinGame.h

↰ Parent directory (ADS/optimization)

The game of the coins in a line: n coins of values V_0 .

Definition (ADS/optimization/CoinGame.h)

Detailed Description

. V_{n-1} lie in a row, and two players take in turn the first or the last coin left, each one to get the most; coinsInALine() is the most the first player can be sure of, against any play of the other.

With D[ i ][ j ] the largest difference between the coins of the player to move and those of the other on V[ i .. j - 1 ], :math:`[

D[ i ][ j ] = max( V_i - D[ i + 1 ][ j ] , V_{j-1} - D[ i ][ j - 1 ] ) ,

` D[ i ][ i ] = 0, and the first player gets ( S + D[ 0 ][ n ] ) / 2, S the sum of the coins; the table filled by increasing length keeps one row, :math:` Theta( n^2 ) ` time and :math:` Theta( n ) ` space. The scheme is the minimax on the intervals; the form with two moves ahead, :math:` M[ i ][ j ] = max( V_i + min( M[ i + 2 ][ j ] , M[ i + 1 ][ j - 1 ] ) , ldots ) `, gives the same value.

For n even the first player never loses: the coins of even places and those of odd places can each be taken all by the first player, who chooses the larger set; this strategy, though, is not optimal in general.

The contracts [see File Contract.h]: none on the values, which may be negative. The functions are defined in CoinGame.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Winkler, Mathematical Puzzles: A Connoisseur’s Collection, A K Peters, 2004

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions