-
>
>
>
>
Programming Assignments >
Assignment 2 - Pig
Objectives
- to use dynamic programming (backward induction) to find a n
optimal strategy for a two-player stochastic game
Introduction
Pig is a dice
game for two players. The players take turns rolling a six-sided die.
On each turn, the current player rolls, adding up the total of the rolls.
The player can stop rolling at any time; when the current player ends the turn
voluntarily then the current turn total is added to the player's score.
However, if the current player rolls a 1 then the turn is over with no
points gained. The first player to a predetermined target (often 100) wins
the game.
Assignment
Write a program that determines the optimal strategy for Pig. The input
will be given as three command-line arguments: a positive integer for
the score needed to win (the target), the score of the next player to roll,
and the score of the other player; both scores will be non-negative integers
less than the target. The output of the program should be the probability
that the next player wins given optimal play by both players, and the
turn total at which the next player should stop rolling on the next turn.
The probability should be given to six decimal places and the two values
should be separated by a single space.
The executable should be named Pig
.
Examples
[jrg94@pig Pig]$ ./Pig 100 0 0
0.530593 21
[jrg94@pig Pig]$ ./Pig 40 0 0
0.544694 18
[jrg94@pig Pig]$ ./Pig 100 70 34
0.851374 10
[jrg94@pig Pig]$ ./Pig 100 34 70
0.205231 30