-
Notifications
You must be signed in to change notification settings - Fork 1
Generic backtracking game solver written for CS4 project, fall 2012
License
solb/cs4gamesolver
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Sol Boucher <slb1566@rit.edu> Kyle Savarese <kms7341@rit.edu> CS4 4003-334 2121 Healy Project Submission 3 The Take Away Game ================== This program is a coach and simulator for the Take Away game, and can be run in either of two modes: Coach (Advisory) Mode --------------------- In this mode, given the number of pennies currently in the game's pile, the program advises the user the optimal number of stones to take on this turn. This functionality is the default when invoked as follows: $ ./takeaway num_pennies Simulator (Interactive) Mode ---------------------------- This mode allows the user to duel the computer to the death. The human player is allowed to go first, and she is asked to enter an integer within the given constraints on this and each subsequent turn. (If her input is out of range, she will be prompted again, although the result of entering non-integral requests is undefined.) The computer takes turns with her, and always plays perfectly. Thus, it should be noted that not all games are actually winnable. In order to enter this (more exciting and less cheap [from the opponent's perspective, at least]) mode, invoke the executable as: $ ./takeaway play num_pennies Format of Command-line Argument ------------------------------- The num_pennies argument referenced in the two subsections on program mode is required to be a positive integer. The play argument---used to switch into interactive---is case-sensitive and must be provided exactly as written. Status ------ 1. Executes normally 2. Has no known issues producing the best move and next position 3. Produces a score value at the end of an interactive game 4. Has no known issues in interactive mode 5. Guilty of reporting no known incorrect answers 6. If I truly knew whether it halted, I'd be working on my doctoral thesis instead of this project. 7. Contains no known memory leaks The Kayles Game =============== This program is a coach and simulator for the Kayles game, and can be run in either of two modes: Coach (Advisory) Mode --------------------- In this mode, given the current state of the game, the program advises the user the optimal number of pins to take on this turn and from which line. This functionality is the default when invoked as follows: $ ./kayles num_pins_1 num_pins_2 ... Simulator (Interactive) Mode ---------------------------- This mode allows the user to duel the computer to the death. The human player is allowed to go first, and she is asked to enter an integer within the given constraints on this and each subsequent turn. (If her input is out of range, she will be prompted again, although the result of entering non-integral requests is undefined.) The computer takes turns with her, and always plays perfectly. Thus, it should be noted that not all games are actually winnable. In order to enter this (more exciting and less cheap [from the opponent's perspective, at least]) mode, invoke the executable as: $ ./kayles play num_pins_1 num_pins_2 ... Format of Command-line Arguments -------------------------------- Each of the num_pins arguments referenced in the two subsections on program mode is required to be a positive integer. The play argument---used to switch into interactive---is case-sensitive and must be provided exactly as written. Status ------ 1. Executes normally 2. Has no known issues producing the best move (and, in interactive mode, the next position) 3. Produces a score value at the end of an interactive game 4. Has no known issues in interactive mode 5. Guilty of reporting no known incorrect answers 6. If I truly knew whether it halted, I'd be working on my doctoral thesis instead of this project. 7. Contains no known memory leaks The Connect-3 Game ================== This program is a coach and simulator for the Connect-3 game, and can be run in either of two modes: Coach (Advisory) Mode --------------------- In this mode, given the current state of the game, the program advises the user of an optimal move to make on this turn. This functionality is the default when invoked as follows: $ ./connect3 <filename | -> Simulator (Interactive) Mode ---------------------------- This mode allows the user to duel the computer to the death. The human player is allowed to go first, and she is asked to pick a legal move on this and each subsequent turn. (If her input is out of range, she will be prompted again, although the result of entering non-integral requests is undefined.) The computer takes turns with her, and always makes optimal moves assuming that she also does so. In order to enter this (more exciting and less cheap [from the opponent's perspective, at least]) mode, invoke the executable as: $ ./connect3 play <filename | -> Format of Command-line Arguments -------------------------------- If a - is provided as the primary argument, the program pauses and waits for a properly-formatted board data file to be fed in via standard input. Substituting a filename instead results in an attempt to read this data from the specified path. The format for a board data file is as follows: width height [a line for every height, each of which consists of width chars] The play argument---used to switch into interactive---is case-sensitive and must be provided exactly as written. Status ------ 1. Executes normally 2. Has no known issues producing the best move (and, in interactive mode, the next position) 3. Produces a score value at the end of an interactive game 4. Has no known issues in interactive mode 5. Guilty of reporting no known incorrect answers 6. If I truly knew whether it halted, I'd be working on my doctoral thesis instead of this project. 7. Contains no known memory leaks The Crossout Game =============== This program is a coach and simulator for the Crossout game, and can be run in either of two modes: Coach (Advisory) Mode --------------------- In this mode, given the current state of the game, the program advises the user the optimal number of pins to take on this turn and from which line. This functionality is the default when invoked as follows: $ ./crossout max_num max_sum Simulator (Interactive) Mode ---------------------------- This mode allows the user to duel the computer to the death. The human player is allowed to go first, and she is asked to enter one or two integers within the given constraints on this and each subsequent turn. (If her input is out of range, she will be prompted again, although the result of entering non-integral requests is undefined.) The computer takes turns with her. In order to enter this (more exciting and less cheap [from the opponent's perspective, at least]) mode, invoke the executable as: $ ./crossout play max_num max_sum Format of Command-line Arguments -------------------------------- The max_num and max_sum arguments referenced in the two subsections on program mode are required to be positive integers. The play argument---used to switch into interactive---is case-sensitive and must be provided exactly as written. Status ------ 1. Executes normally 2. Has no known issues producing the best move (and, in interactive mode, the next position) 3. Produces a score value at the end of an interactive game 4. Has no known issues in interactive mode 5. Guilty of re 61BA porting no known incorrect answers 6. If I truly knew whether it halted, I'd be working on my doctoral thesis instead of this project. 7. Contains no known memory leaks Design ====== First, we created the idea of a State that is a base for States used by the two games (TakeawayState and KaylesState). No such generic State actually exists, but specific implementations of these two games do. These provide several common utilities for users. Most significant is successors(), which returns a vector of all possible next states from the current state. Each state also contains a hash function necessary for the HashTable that does the memoization storage for the game. It can also check if the current state represents a terminal state, can return the score of the game( for terminal states ), can return a string representation, and compare for equality with other states of the same type. Additionally, each state class is expected to provide convenience functions for use in the main programs (areSubsequent and diff). The Solver is templeted around states. It knows what the current state is, can tell the nextBestState, accept requests for a next state, and advance to the next state. The Solver loop recursively traverses the game tree in a brute force fashion, constructing the memoization table while passing around a struct called StatePlusScore. The "Score" of a state is defined by the individual game state class. The states are not expected to reverse the board. The Score will always return from one player's point of view, and assumes that the computer wants to win. A score is "good" if the computer thinks that the move benefits it. Implementing a new game can be done by implementing a new state class that defines all applicable functions and defines scores such that preferred states for the computer have higher scores than less desired states. (This is the exact procedure that was followed for Connect-3.)
About
Generic backtracking game solver written for CS4 project, fall 2012
Resources
License
Stars
Watchers
Forks
Packages 0
No packages published