ProjectStructure
The solution, Simulation.sln, contains 4 major project types. These are the console application, the GamePlay library, the common library, and the Strategy libraries.
A console application (Chute.exe) that executes the various demos in the solution. Uncomment each demo individually in the Main method and then run the project to execute the demo. The demos are store in extension methods that extend the GameBoard object and are ordered by where they fit in the Developer's Survey of AI Methods presentation.
This library contains the objects that perform the simulations. There are 3 primary entry points in this library:
-
Game - This object represents a single game of Chutes & Ladders played using the variant rules. This object holds a collection of player objects, each of which implements its own strategy AI.
-
Simulation - This object represents a collection of games all played using the same group of players. The number of wins forf each player is tracked.
-
SimulationCollection - This object represents a collection of simulations executed in parallel, each using a different order of players. The intent is to eliminate the advantage of having one player go 1st all of the time so that we can get an accurate picture of how well a particular strategy works.
A common library used by all projects in the solution. This project holds the Entities, Interfaces, and common extension methods for the solution. The key items in this library include:
-
Player - Represents a player of the game and holds the player's name, # of wins in the current simulation, and a reference to the strategy that the player is employing.
-
IGameStrategy - An abstraction identifying the structure of an object that can make decisions on behalf of a player with regard to game strategy. Each implementation of this interface is an AI that makes decisions about how to play the game based on the current situation. The primary method is the GetMove method which takes a GameSituation object and returns the integer location to which the player should be moved. This result must be one of the options from the LegalMoves collection of the GameSituation parameter.
-
GameSituation - An object that represents the current status of the game for a specific player. The object holds the player's current location on the board, the value of the player's current spin, a collection of legal endpoints that the strategy can chose from, and a list of the locations of all players as of that moment (including the current player). The locatons of the other players is not currently used in these demos but is made available for future opportunities.
These libraries contains the various strategy implementations. Each strategy is an Artificial Intelligence that must decide which of the options available should be chosen. The choices are based on the current location on the board and the value of the spin for the player during the current turn. A strategy implementation is required to implement the IGameStrategy interface from the ChutesAndLadders.Common library.
This library contains a strategy AI that uses a greedy heursitic to decide on the best move to make. The algorithm takes the list of possible endpoints supplied by the game engine and selects the largest number (the number closest in value to 100).
This AI uses the opposite of the ChutesAndLadders.Strategy.Greedy library's strategy by selecting the smallest number from the list of valid endpoints. This strategy was used to prove-out the Greedy strategy by giving it an opponent to play against win an inferior strategy. Be aware that it is likely that this strategy will never finish since it is always trying to move away from the finish line. As such, a game played by players using only this strategy might never finish.
The Linear AI implementation's strategy is to skip all ladders and chutes, keeping to a path that touches every space on the board.
This libary contains a rules engine that executes rules to determine what decisions should be made. By itself, it has a default rule that executes a linear strategy so if no additional rules are added, or if no rule exists to handle a particular situation, the decision made will be the same as if the linear strategy was used. This is also used as the base class for other strategies which add their own rules for gameplay decisions, but always fall back to the linear strategy if no other instructions exist.
A reimplementation of the greedy strategy (described above) using the ChutesAndLadders.Strategy.Rules engine.
A rules engine implementation of a strategy that takes all ladders and skips all chutes. Multiple rules are created for each ladder that represents all of the possible combinations of starting-point and spin from which that ladder can be taken.
This strategy takes a collection of chromosomes that represent all of the possible actions that can be taken and the conditions under which the should be taken, and translates them into rules that are processed by the ChutesAndLadders.Strategy.Rules engine. The chromosomes can be copied into future generations and mutated into new strategy "species".
This libary uses Dynamic Programming to calculate the shortest distance from each space on the game board to the end (space 100). When a decision is required, this AI choses the space that is the shortest distance from the end of the board (closest to winning). This space will often, but not always be the same as the space chosen by the Greedy algorithm.