yahtzee.txt

Yahtzee is a popular dice game for two (or conceivably more) players.
Rules can be found at http://www.hasbro.com/common/instruct/Yahtzee.pdf.

Write a program that plays Yahtzee. Your program will play games
against other Yahtzee players. Your goal is to win games by scoring
more points than your opponent.

I/O:

The program should accept a stream of positions from stdin and print
a stream of actions to stdout.  A position is described by 34
integers, as follows:

Integers 1-14 give the content of the current player's scorecard.  The
first thirteen integers give the entries in the thirteen Yahtzee
scoring areas: ones, twos, threes, fours, fives, sixes, three of a
kind, four of a kind, full house, small straight, large straight,
Yahtzee, and chance.  An entry of -1 means that the slot in question
has not yet been filled.  The fourteenth entry gives the number of
bonus points scored for Yahtzees beyond the first.

Integers 15-28 give the content of the opponent's scorecard.

Integers 29-33 give the dice rolled.  Each integer is a number from 1
to 6.

Integer 34 gives the roll number.  A value of 1 indicates that this is
the first roll, 2 indicates the second roll, and 3 indicates the third
roll.

The program should print out an "action", which is a value from 0 to
63.  If the low order bit is zero, the action indicates that the
program desires to place the dice in a given row of the Yahtzee score
card; the row selected (0-12) is in the higher order bits.  So a value
of 6 (binary 110) indicates that the dice should be played in the
"fours" row (the ones row is zero, etc).

If the low order bit is one, the action indicates which dice the
program wants to "hold".  Bit 1 corresponds to the first die
(corresponding to input integer 29), bit 2 to the second die, etc.  If
the bit is 1, the die in question is held.  If the bit is zero, it is
rerolled.  As an example, a value of 45 (binary 101101) indicates that
dice 2, 3 and 5 (of 5) should be held.

The positions will be single-space-separated integers terminated with
a linefeed character (ASCII 10). Your output should be a single
integer terminated by a linefeed character.

Example:

Position:
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1

(In this position, you have 8 points in the fours slot, 20 points in
the chance slot, and no bonuses. All your other slots have not yet
been filled. Your opponent has 3 points in the threes slot, 0 points
in the fives slot, and no bonuses. All of your opponents other slots
have not yet been filled. You have rolled the dice one time and they
show the numbers 1, 3, 4, 5, and 6.)

You might play:
18 

In binary, this is 010010. Since the low bit is 0, this places the
dice in the row indicated by the higher-order bits: 01001. In decimal,
this is 9. The 9th slot (counting from 0) is small straight. 

You might play:
5

In binary, this is 000101, Since the low bit is 1, this holds some
dice and rerolls the rest. In this example, only the three is held;
the 1, 4, 5, and 6 are rerolled.

See the bottom of this description for more examples of legal and
illegal plays.

COMPETITION:

Your program will compete against other programs one-on-one using a
double-elimination knockout format. Each match will consist of 1,000
games.

In order to be considered a contest submission, your program must beat
a Yahtzee player that just plays one random legal move each turn. This
is not hard - we built a very simple greedy player that doesn't even
know about the joker rule, and thus may sometimes attempt to play
illegal moves, thereby forfeiting the game, and it still beats the
random player by a huge margin.

PROGRAM REQUIREMENTS:

We will evaluate your program by having it play matches of 1,000 games
against other Yahtzee programs. You have 10 minutes of CPU time (on a
modern multi-core machine) to play these 1,000 games. If you run out
of time in a match, the remaining unplayed games in that match will be
considered lost. Your program should not print anything to stdout that
is not an action to be played.

Your programs will only be restarted between matches. If your program
crashes during a match the remaining unplayed games in that match will
be considered lost. Your program should not read one position and then
print out one action; it should continue to read positions and print
outputs until stdin reaches EOF.

A player attempting to play an illegal move will forfeit the current
game, though not the match. 

For the remainder of this section, "GB" means 2^30 bytes, and "MB"
means 2^20 bytes.

You may not at any point exceed 2GB of memory usage. If you do, your
program will be halted and the remaining unplayed games in the match
will be considered lost.

You may send us a 5MB data file for your program to access while it
runs. You must send us the source code and the build scripts you used
to generate this data file.

If you wish, you may indicate that your program should be run in a
particular way (for instance, by passing it a certain flag) in order
to generate a much larger data file. This larger data file may be no
more than 10GB in size and must take less than 8 wall clock hours to
generate. Generating this file must use no more than 2GB of memory at
any time. Your program, when run in the normal way, may use this
larger data file to play its games.

You must submit all of your source code and build scripts. Include a
file named readme.txt explaining how to build your program. Tell us
the exact compiler and library versions you are using. For instance:

libstdc++ 6.0.9
i686-apple-darwin10-g++-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664)

All your code must be original, with the exception of standard
libraries. You may also use Boost, SciPy, or Apache Commons Proper. If
you want to use another library, ask first.

All matches will be run on a Unix-like operating system. Do not assume
anything about the case sensitivity of the file system.

F.A.Q.

Q: Is 5-of-a-kind a legal full house?

A: Not unless the joker rule is active.

Q: Is 4-of-a-kind a legal 3-of-a-kind?

A: Yes.

Q: How are the dice chosen?

A: We use a high-quality pseudorandom number generator and a random
seed.

Q: How often will the program be restarted?

A: Your program will be restarted between matches.

Q: Can my program do some precomputation before reading in the first
position?

A: Yes.

Q: Is the last number for a player's score (i.e. "the number of bonus
points scored for Yahtzees beyond the first") in increments of 1 or
100?  That is, does the number represent the bonus chips, per Hasbro
rules, or the actual points?

A: The actual points.

Q: After reading in one position and printing out one action, should
my program quit?

A: No, it should continue to read positions from stdin and print
actions to stdout until stdin reaches EOF.

Q: I have one aggressive program (that may play illegal moves or
crash) and one safer one (that may win fewer games). Can I submit
both?

A: You can submit whatever you like, and we will read it, but you
should pick one that we will run.

APPENDIX - EXAMPLES OF LEGAL AND ILLEGAL PLAYS:

In the examples below, illegal plays are described by the reason for
their illegality. Legal plays are simply described as "legal".

-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 2
1
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 3
1
There are no rolls left
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
1
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
-1
Only the first five dice are available for holding
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
63
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
65
Only the first five dice are available for holding
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
0
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 20 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
-2
Invalid row for placement
-------------------------------------
-1 0 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
24
legal
-------------------------------------
-1 0 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
26
Invalid row for placement
-------------------------------------
-1 0 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 3 4 5 6 1
22
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
22
This row is already full
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
4
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
0
Under the joker rules, if the appropriate upper section row is empty, it must be used
-------------------------------------
-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
12
legal
-------------------------------------
-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
2
Under the joker rules, if the appropriate upper section row is full, the lower section must be used unless the whole lower section is filled
-------------------------------------
-1 -1 6 -1 -1 -1 0 0 0 0 0 0 0 0 -1 2 3 -1 0 -1 0 -1 0 -1 0 0 0 0 3 3 3 3 3 1
2
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 50 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
22
This row is already full
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 50 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
4
legal
-------------------------------------
-1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 50 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
0
Under the joker rules, if the appropriate upper section row is empty, it must be used
-------------------------------------
-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 50 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
12
legal
-------------------------------------
-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 50 -1 0 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 3 3 3 3 3 1
2
Under the joker rules, if the appropriate upper section row is full, the lower section must be used unless the whole lower section is filled
-------------------------------------
-1 -1 6 -1 -1 -1 0 0 0 0 0 50 0 0 -1 2 3 -1 0 -1 0 -1 0 -1 0 0 0 0 3 3 3 3 3 1
2
legal