Idea: Go and Arimaa

Description and Goals. The ancient game of Go and the modern Arimaa are known to be hard for computer AI algorithms. The goal of this project is to define these games in Toss, compare how current Toss algorithms fare on these two hard games, and possibly extend the algorithms to play well!

Deliverables. By mid-term both games will be defined in Toss, ready for non-automatic play. By the end, both the current minimax with alpha-beta playout method and the Monte-Carlo with UTC method will be compared on these games with different generated and hand-crafted heuristics.

Modules (in planned construction order).

1. Arimaa definition in Toss (easy)
2. Go definition in Toss without Ko (medium)
3. Toss extension to handle repeated positions (medium)
4. Go definition with Ko (easy after 3)
5. Adapting Minimax and UCT to play somehow (medium)
6. Optimizing the algorithms to play well (unknown)

Needed Skills and Difficulty. Good OCaml programming skills are required, and some general knowledge of game playing algorithms will be necessary. This is a medium difficulty project, but it can become very interesting in the last phase!

Idea: Pac-Man in Toss

Description and Goals. While there is support for continuous dynamics and some concurrency in current Toss code and GUI, these are not fully developed, tested, and not supported in the web interface. The good old Pac-Man is an ideal test candidate for these features, especially for concurrent moves.

Deliverables. By mid-term it will be possible to play Pac-Man in Toss in command line mode and in the GUI. By the end, it will be supported in the web interface and automatic play will work as well.

Modules (in planned construction order).

1. Allow multiple players in one location in Toss (easy)
2. Implement missing concurrency features in Toss (medium)
3. Test, debug and implement missing timing features (easy)
4. Pac-Man in command line and GUI (easy after 1, 2)
5. Make Toss web interface fully asynchronous (medium)
6. Pac-Man in the web interface (easy after 5)
7. Adapt automatic playing algorithms to concurrency

Needed Skills and Difficulty. This idea is easy to medium depending on much one demands in point 7. It requires the student to know both OCaml and AJAX with JavaScript, and to be able to use and debug them in parallel.

Idea: Game Design made Comfortable

Description and Goals. If you are passionate for interfaces, you see clearly that there is work for you in Toss. The interface for playing games is reasonable, but to create a game one has to go back to the text editor and use a syntax which could also see quite some improvements. The goal is to make one interface to take the best of these all and make it the preferred choice for Toss.

Deliverables. The web interface will be extended to allow textual definitions of new games by mid-term, including a possibility to test the game before publishing it to friends or to everyone. Before the end, basic functions of the GUI such as separate editing of rules and changing relations, elements and positions will work online.

Modules (in planned construction order).

1. Make game list dynamic in the web interface
2. Allow users to add new games by uploading .toss files
3. Separate tab or page for game editing, simple text form
4. Handling of errors and basic sanity checks for new games
5. Extend game editing tab, separate rules, definitions
6. Tab for model editing, allow to view defined relations
7. Define a new game with the created interface, is it usable?

Needed Skills and Difficulty. OCaml skills are not required for this project, as it concerns mostly web programming and interface design. But being easy from technical point of view does not make it really easy – a good feeling for interface design is necessary, and a lot of testing to make it right.

Idea: Fast Optimizing Solver

Description and Goals. The solver in Toss is no slouch, but it could be better. Formulas should be compiled to a more optimized form, possibly using relation size statistics. Structures should be optimized for memory footprint and these together for cache coherency – maybe with some parts rewritten in C. Dynamics calculations should be moved nearer to the structure.

Deliverables. By mid-term, the compilation of formulas for the solver will be optimized and cleaned-up, with a separate module not using the current TNF. By the end, the structure module will be optimized and dynamics calculations moved there from the current Term module.

Modules (in planned construction order).

1. Written detailed design of new compilation module
2. New formula compilation functions and unit tests
3. Testing full Toss with the new module, quantify gains
4. Detailed design of new structure module with dynamics
5. Implementation of the new module, possibly in C
6. Interfacing the new module and testing it
7. Testing and optimizing performance of both modules

Needed Skills and Difficulty. This project is technical and requires very good understanding of OCaml, the interface between OCaml and C, and the various factors which can influence performance. Some knowledge of either databases and their optimization techniques or constraint solving will be helpful.

Idea: GGP Competition and Cooperation

Description and Goals. General Game Playing, GGP, is a name for the task of playing a game given as input. In the 0.7 release, Toss gained a module to translate games defined in GDL, the Game Description Language used in GGP Competitions, to the Toss format. This allows to compete against GGP players, and we even won quite a few games already! But the GGP translation is not complete, games with recursive definitions cannot be translated yet, and some translated definitions can be large. The idea is to improve this, but also to cooperate with the GGP guys, especially with the GGP Galaxy Project, to make General Game Playing truly accessible for everyone!

Deliverables. Toss GGP translation module will be improved by mid-term to handle standard games well, including single-player games which do not translate well now. By the end, the majority of games in GDL will translate well and will be made usable from the web interface. The GGP Competition starts around autumn, so of course the best final goal would be for Toss to score a win there!

Modules (in planned construction order).

1. Generalize GGP translation using fixed-points (medium)
2. Generalize GDL translation to handle simultaneous moves and arbitrary turn taking (enrich concurrency support in Toss)
3. Improve readability of translated games, test, debug
4. Add some position detection or layouting to the translation
5. Adapt web interface to be usable with translated games

Needed Skills and Difficulty. Due to different design choices behind the GDL and Toss formalisms, the translation is a complex task and it requires acquaintance with concepts from logic programming. Good knowledge of OCaml is necessary of course, but some previous knowledge of GGP/GDL or Prolog would be helpful. Still, passion for GGP is the best recommendation for this project!

Idea: Feature Learning

Description and Goals. Currently, Toss generates functions for position evaluation form the payoffs and rules of the game in one way, fixed in the code. It would be better to use a weighted mix of various evaluation functions or their parts (which we call features) and learn the appropriate weights by playing them against each other. We expect that this will improve Toss strength significantly.

Deliverables. By mid-term the basic framework for feature learning should be present, and demonstrated e.g. by learning weights for pieces in chess. By the end, the goals is to replace the default play mode of Toss by one which uses feature learning.

Modules (in planned construction order).

1. Implement weighted mixing of heuristics (easy)
2. Hook up multi-dimensional optimization (medium, use GSL?)
3. Test weight learning, minimize needed playouts (easy)
4. Create features from various game parts (hard)
5. Memorize learned weights, replace default playout (medium)

Needed Skills and Difficulty. This is a medium to hard project – a lot depends how many features will be generated and how, but even using just a few should already improve playing strength. OCaml experience is required.

Idea: Games with Imperfect Information

Description and Goals. At present Toss only allows to define games with perfect information, i.e. the complete state is known to all players. The idea to extend Toss to imperfect information games is based on views, which are tuples of formulas which convert the true state into a new structure, which the player sees. Such extension should allow to define some well know games with imperfect information such as a card game or Minesweeper.

Deliverables. To add views it is necessary to extend the core game definition in Arena, and to adapt many things which rely on this. Such extension, together with a toy example and of course preserving the current functionality should be ready by mid-term. After that, it will be necessary to adapt automatic playing algorithms to take imperfect information into account, and at least one full game with imperfect information should be defined by the end of the project.

Modules (in planned construction order).

1. Add views to Arena, update everything (already started)
2. Adapt interfaces to account for views (medium)
3. Testing, a toy imperfect information game (easy)
4. Generalize automatic play to imperfect information (hard)
5. Define a full game with imperfect information (medium)

Needed Skills and Difficulty. Good knowledge of OCaml and some understanding of games with imperfect information will be necessary. This project is medium to hard, depending on how much effort one makes to adapt automatic play.

Idea: Mobile Visual Game Recognition and Learning

Description and Goals. Do you know that Toss can learn game rules from simple video demonstrations? And Toss also works on mobile devices, we are in the App Store and Android port progresses with Chromium on Android. But these two parts do not work together: video recognition is based on OpenCV and our mobile ports are mostly JavaScript. But maybe you can bring those two together? Recording a game with a cell phone and being able to play it just after that is the ultimate cool thing anyway!

Deliverables. By mid-terms the video recognition pipeline should be integrated with Toss server and clients, so that at least clear and steady videos can be recognized and simple games played. By the end it should be possible to define basic games even when the video changes position and light is not steady.

Modules (in planned construction order).

1. Integrate video recognition with the Toss Server code
2. Transfer videos or parts from Client to Server
3. Re-structure the recognition pipeline for mobile use (unstable videos, more corrections needed)
4. Test the new video pipeline in various situations, report
5. Present examples of games learned from mobile recordings

Needed Skills and Difficulty. This project is ambitious and requires good knowledge of OpenCV and issues in video recognition. It will also be necessary to have a good grasp of how to interface OCaml and C code, and of the issues involved in transfering video over the net. These are difficult things, but the effect will certainly be very rewarding!