Assignment 1: Backward Induction #

Due date: 09/04/2024

Task: Create a generic recursive solver and an implementation for the game ( \( n \in \mathbb{N} \) )-to-0 with move options in \( S \subseteq \mathbb{N_{n}\setminus\{0\}} \) .

Provided:

• High-level steps and hints in this web page.
• A correct implementation of this game (as a separate binary, perhaps nova).
• A rough testing framework in the form of a script, replicating the autograding setup.
• Python skeleton code including an abstract game interface in a multi-file structure and basic utilities for parsing arguments from stdin (e.g., game parameters) and for writing to stdout (e.g., a memo-table analyzer, used in Assignments 2 and 3).

Metrics: After executing the python program with the adequate arguments, stdout should match the output of the provided game implementation on arbitrary (but within the bounds of a non-memoized solution) inputs of \( n \) and \( S \) . The specific inputs on which it will be evaluated is not provided. For this assignment, output should be the categorical “game value,” WIN, LOSE, or TIE.

Learning objectives:

• Internalize the “API” of a finite extensive-form game via generic programming.
• Begin getting comfortable writing parameterized game implementations.
• Fundamentally understand the method of backward induction.
• Get used to testing and software organization.

Note: Participants can use any language as long as they can package it into a stand-alone program that they can submit for testing. The source code is provided through a public GitHub repository, and nova can be installed with the Rust toolchain.