Assignment 1: Cribbage Agent

Objectives

to use implement a rule-based and/or heuristic agent for a game

Introduction

Cribbage is a card game for two or more players in which players play a series of hands in a race to 121 points. For the rules of the game, see Wikipedia and to play online, see CardGames.io.

Assignment

Implement an agent for two-player cribbage. Your agent will receive information after the deal and must determine which cards to keep in its hand and which to discard into the crib, and will receive information each time it is its turn during the pegging phase and must determine which card, if any, to play from its remaining cards. The goal of the agent is to maximize the difference between the expected match points won by it and won by its opponent. We score a normal win as 1 match point, a skunk as 2, and a double skunk as 3, with no additional points for a triple skunk.

The /c/cs474/hw1/code directory on the Zoo contains code that implements the rules of two-player cribbage, code for a benchmark greedy agent, and starter code for your agent. This code is also available from a git repository. There is a subdirectory for each of four supported languages: Python, Java, C++, and C. There are two functions/methods in the starter code that you must modify in order to implement your agent:

Python: the keep and peg methods in the MyPolicy class in the my_policy.py module;
Java: the keep and peg methods in the MyPolicy class in the default package;
C++: the keep and peg methods in the MyPolicy class defined in my_policy.h and my_policy.cpp;
C: the keep and peg functions defined in my_policy.c.

The files mentioned above (along with the makefile) are the only files that you may edit, although you may create additional files as necessary.

For all languages, there are objects passed to the required functions that represent the rules of the game and the current state of the game. These objects are instances of various classes

game object	Python	Java	C++
game	`Game`	`CribbageGame`	`CribbageGame`
card	`Card`	`CribbageCard`	`CribbageCard`
deck	`Deck`	`CribbageDeck`	`Deck<CardRank, char, OrderedRanks, CharacterSuits>`
hand	list of `Card`s	`CribbageCard`	`CribbageCard`
sequence of cards played during pegging	`Pegging`	`PeggingHistory`	`PeggingHistory`

The C code uses the C++ objects with a C interface to them defined in c_cribbage.h and c_cribbage.cpp. Please see the documentation in the source code for those classes for information about the methods they provide. For all languages, you may also use the implementation of the greedy baseline agent as a guide for how to use the objects passed to the keep and peg functions/methods.

You may use any method you wish, but for reference, the policies mentioned below in the grading section are heuristics that don't require any methods from later in the course. The heuristic for the discard policy estimates a hand's value by considering some of the things the greedy policy does not consider. The heuristic for the pegging policy applies a series of if condition then score += small-constant adjustments to the score that would be earned by playing each card. Those adjustments are intended to capture the possibility of setting up points to be earned (or avoided) in future plays and include preventing the opponent from reaching a count of exactly 15, and setting up pairs on future plays.

Your code should be capable of playing 1000 games against the greedy opponent in 120 seconds on the Zoo. For Python, you may benefit from using the pypy3 interpreter instead python3, which is the CPython interpreter. Pypy is much faster than CPython, but unfortunately has a more limited range of available libraries (which should not be a problem for this assignment).

Grading

Grading will be based on performance against the baseline greedy agent. The greedy agent determines discards by counting the points earned by the cards it keeps and the points earned by the cards it discards, without considering what the community card might be, or what its opponent might throw. The greedy agent determines which card to play during pegging by determining which card earns the most points when it is played next, without considering how the opponent might respond. In both cases, it breaks ties uniformly randomly.

It is possible to define a policy for choosing cards to discard that, combined with the greedy pegging policy, beats the baseline policy by about 0.14 match points per game in a couple dozen lines of code (and a similar but slightly more complicated version that does another 0.02 points better). It is possible to define a policy for choosing a card during pegging that, combined with the greedy discard policy, beats the baseline policy by about 0.08 match points per game in a few dozen lines of code. Combining the two policies is additive, resulting in a margin of about 0.22 match points per game. Those targets will be used to set grades: 0.08 for a B, 0.14 for approximately a B+, and 0.22 for an A (to allow for room to improve over my implementations, an A here is 94 or 95 points).

For this and other assignments for which your submission is graded based on sampling its performance in a stochastic environment, the submission script favors speed over accuracy and will not do much more than check whether your submission runs. To determine your agent's performance accurately enough to assign a meaningful grade, we will have to run your submission for hours – the standard deviation of the match points for a single game between agents of this quality is about 1.2, and getting the standard deviation of the average over a series of games down to 0.001 requires about a million games. Grades will be based on comparisons of the lower ends of confidence intervals after a fixed period of time (rather than a fixed number of games), adjusted for language, so a very slow but otherwise high performing agent may receive a lower score than a very fast but slightly worse agent because the latter's confidence interval will be narrower. You can check your performance by running the TestCribbage program yourself outside of the submission system (see below for an example).

You might want to save anything slow and/or complicated for a final project, which will be graded more on quality of approach and experimental design rather than performance.

Submissions

So that the submission system can use the same build and execute commands regardless of language, you must supply a makefile that creates an executable called TestCribbage with entry point test_cribbage.py, main in class TestCribbage, main in cpp/test_cribbage.cpp, or main in c/test_cribbage.cpp for Python, Java, C++, and C respectvely. There is a sample makefile in the directory with the starter code for each language. The executable takes the number of games to play as its argument and displays the difference between the average number of match points won per game by your agent and that average for the baseline agent. For Python and Java, the executable that the makefile creates is a bash script that compiles (for Java) and runs your program. For example,

TestCribbage:
	echo "#!/bin/bash" > TestCribbage
	echo "pypy3 test_cribbage.py \"\$$@\"" >> TestCribbage
	chmod u+x TestCribbage

You would then submit your source code, makefile, and log as assignment 1. Do not submit any files other than your makefile and the files containing the code that you wrote; the other files will be copied from the given code to grade your submissions and you may not change them.

(base) [jrg94@turtle p1]$ ./TestCribbage 1000
NET: 0
0.571-0.571 {-3=1 3=3 2=64 -1=428 1=434 -2=70 } (8.873 hands/game)
(base) [jrg94@gator python]$ /c/cs474/bin/submit 1 my_policy.py log
Copying my_policy.py
Copying log
(base) [jrg94@gator python]$ /c/cs474/bin/testit 1 TestCribbage
/home/classes/cs474/Hwk1/test.TestCribbage
Copying card.cpp
... [no language detection, so it copies all files for all languages]
Copying utility.h
Executing /home/classes/cs474/Hwk1/test.TestCribbage

Public test script for TestCribbage (09/05/2022)

***** Checking for warning messages *****
Making -B ./TestCribbage
echo "#!/bin/bash" > TestCribbage
echo "python3 test_cribbage.py \"\$@\"" >> TestCribbage
chmod u+x TestCribbage

Each test is either passed or failed; there is no partial credit.

To execute the test labelled IJ, type one of the following commands
depending on whether the file /c/cs474/hw1/Tests/tIJ is executable or not
     /c/cs474/hw1/Tests/tIJ
     ./TestCribbage < /c/cs474/hw1/Tests/tIJ
The answer expected is in /c/cs474/hw1/Tests/tIJ.out.


           Cribbage
PASSED  001. Execution Test (succeeds if your program ran)

           Cribbage: 1 of 1 tests passed

               Deductions for Violating Specification (0 => no violation)

End of Public Script

  1 of   1 Total tests passed for TestCribbage

           Possible Deductions (assessed later as appropriate)
               -10 Deficient style (comments, identifiers, formatting, ...)
                -5 Does not make
                -5 Makefile missing
                -5 Makefile incorrect
                -1 Log file incorrectly named
                -1 Log file lacks estimated time
                -1 Log file lacks total time
                -1 Log file lacks statement of major difficulties

***** Checking log file *****
Estimate: ESTIMATE 20:00
Total: TOTAL 40:00

***** Checking makefile *****

There is a known problem running Java programs through the submission system for which we haven't been able to find a workaround. If your Java submissions do not work through the testit script, you can verify that your Java submission will work when we grade it using the following steps: 1) make a fresh directory, 2) use /c/cs474/bin/retrieve 1 filename to retrieve your submitted files one-by-one into that directory, 3) copy the provided jar file to that directory, and 4) run /c/cs474/hw1/Tests/test.Cribbage.