Vitro Project: Reversi - Model AI Assignments

Vitro Project : Reversi Assignment

Summary	The classic two-player board game Reversi (also called Othello™) will be the domain for learning and implementing adversarial search methods. Students will implement minimax and alpha-beta pruning algorithms and design evalutaion functions for this domain. A Tic Tac Toe domain is also provided for illustrating concepts in a small scale and for testing purposes. The Reversi assignment fits into the broader Vitro project; Vitro provides a simulation and visualization framework supporting several fun and classic domains (Wumpus World, Slide Puzzle, Tic Tac Toe, Reversi, Lunar Lander, Sokoban, etc.) to enable active learning for AI students.
Topics	The project focuses on adversarial search, specifically minimax and alpha-beta pruning.
Audience	Introduction to Artificial Intelligence students; Post- Data Structures.
Difficulty	The project is split into 3 items and is expected to be part of a series of programming assignments for the course. The project can be completed in 1.5-2 weeks.
Strengths	The assignment allows for students to understand adversarial search using a entertaining game. The visualization allows for students to watch, step through, and potentially debug their agents in action. Working with the Vitro framework will provide students with an opportunity to make extensions to a medium-sized pre-existing codebase, emphasizing Object-Oriented development practices. The inclusion of multiple domains with a common set of interfaces allows students to reuse code between projects and write general solutions.
Weaknesses	The Vitro project requires knowledge of Java and implementing project using the provided jar file and Java documentation. Othello is a fairly straightforward game, and in the future we would like to provide increasingly sophisticated and engaging domains of which these adversarial search projects could be "first steps". Also, this model assignment covers a narrow range of AI techniques, focusing on adversarial search- we intend to expand the range of programming assignments to cover many other AI concepts.
Dependencies	The project requires the student to have a basic understanding of data structures and search methods. The project is OS independent, but uses Java. The assignment describes the use of the Eclipse IDE, but is not dependent on this choice.
Variants	The basic algorithms required for the project may also be used in other domains, such as Tic Tac Toe. The Vitro project allows instructors to extend the domain for other programming assignments and provides a common interface for writing agents. Our architecture makes it possible to automate running agents against one another, and with small extensions to the system teachers could hold classroom competitions between agents. Aside from programming assignments, domains developed in Vitro can be used as in-class lecture aids or distributed to students for later study.

Reversi Assignment

A description of the Reversi assignment is available here [pdf]. The project codebase is available for download here [zip]. The project is OS independent.

Vitro

The Reversi domain is part of the larger Vitro project. See list of demos (run in the project directory) illustrating the various domains.

Reversi - The classic two-player board game Reversi (also called Othello) will be the domain for learning and implementing adversarial search methods. A demo of this domain using two greedy players:
```
java -classpath lib/vitro.jar demos.reversi.ReversiEye
```
Tic Tac Toe - Another classic adversarial search domain. This domain can be used to check the generalizability of a students' minimax and alpha-beta pruning search implementations. A demo of this domain can be run:
```
java -classpath lib/vitro.jar demos.tictac.TicTacEye
```
Slide Puzzle - A classic domain used to illustrate search methods. A demo of the domain using a random search:
```
java -classpath lib/vitro.jar demos.slide.SlidePuzzleEye
```
Lunar Lander - A fun video game-like domain that could be used for a reinforcement learning or planning project. A demo using an ad-hoc controller:
```
java -classpath lib/vitro.jar demos.lunar.LunarEye
```
Sokoban - A maze world can be created and filled with robots, blocks they need to push to target locations, and environmental obstacles (lights on/off, restricted passage ways, etc.). A demo with robots taking random actions:
```
java -classpath lib/vitro.jar demos.robots.RobotsEye
```
We also have scenarios demonstrating pathfinding algorithms:
```
java -classpath lib/vitro.jar assign.search.SearchHost
```
Wumpus World The classic AIMA example of an agent hunting a Wumpus. A demo using a controller which acts based on logical inference rules.
```
java -classpath lib/vitro.jar demos.wumpus.WumpusEye
```

The Vitro framework allows an instructor to create new domains by starting from scratch or using a template. The included templates provide rules for creating simulations with grid-, graph-, and planar-based models of space.

Grid-based Domains - Examples of the grid-based domains include the Reversi, Slide Puzzle, and Sokoban demos from above as well as games like MineSweeper:
```
java -classpath lib/vitro.jar demos.sweeper.SweeperEye
```
Graph-based Domains - An example of the graph model is the Wumpus World demo. Additional examples illustring this design are:
```
java -classpath lib/vitro.jar demos.vacuum.VacEye
```
Plane-based Domains - An example of the plane model is the Lunar Lander demo.
```
java -classpath lib/vitro.jar demos.lunar.LunarEye
```