Greg’s game for AI-424 (to be retitled)

DRAX⁺ 1999

(formerly Greg’s game).

A Game by Gregory Dudek for AI 308-424 at McGill University.

A program to play this game is the topic of the final project in AI-424.

The objectives for the project include:

Allow students to compete against another to provide motivation and a sense of fun.

Make the project, and hence the game, challenging and rich.

Make the project quite different from those of past years: make it fresh and reduce plagarism.

Include multiple aspects of AI, to be combined at the individual student’s discretion.

Allow substantially different types of approach and strategy.

Relate the game to ongoing research: specifically robotics.

Include uncertainty, as opposed to simply complete knowledge.

Include non-static aspects. •

Include the potential for reasoning and knowledge representation.

Include the potential for search, specifically A* and alpha-beta.

Include the potential for learning.

Permit work from prior assignments to be incorporated.

Do something that will demo well.

Do something that might be executed on real robots (e.g. an exploration strategy). •

Do something that might be useful in the real world (e.g. a web search engine). •

Make the problem scalable: it can be tuned to make it harder or easier.

Minimize the need for mindless coding and system development.

I acknowledge that it is not likely that all these objectives can be simultaneously satisfied. The game below satisfied some, but not all, of the desired objectives.

The proposed game is to be played over the internet, moderated by a socket-based server process. For development, a student can let a program play itself. Subsequently, students will compete against one another, probably using a "Swiss-system playoff" schedule, as is used in (human) chess tournaments.

The proposed game is as follows.

There are two players, one white and one black. Each player has several "stones" (this number can be varied to moderate the complexity). The stones move between the nodes of an 8-connected grid (a slightly more general version of the game could use an arbitrary graph). Players alternate turns: on each turn one player may slide one stone from its current node to different node moving only along the edges of the graph.

All edges have one of two colors: white or black. Moving only along edge of your own color, you can move up to two nodes away in one turn. If you move along an edge of the opponent’s color, you can only move one node away (to an adjacent node) in a single turn. Initially, stones must make progress towards the opposite side of the board every time they move. Once a stone has reached the other side of the board, it can move in any direction on all subsequent moves (this is referred to be "queening").

The simplest configuration for the graph is a grid. For now, I am assuming that the board will always have the form of a grid with additional diagonal links, as discussed in class.

The simplest objective is to remove the opponents’ stones from the board. This is accomplished by moving one of your stones onto one belonging to the opponent, in which case their stone is removed. Note that if two stones are adjacent, whoever moves can remove the other’s stone. If a pair of stone are distance two away from one another, it is possible that only one of the players will be in immediate danger (if the intervening edges are all the same color), or that nobody is in immediate danger.

At any time of positions of all the nodes and connectivity of the stones is known to both players. The game, in principle, supports a form of uncertainty know as "foggy mode" but it will not be used in the project.

[See figure below.]

There is a limited amount of time per move, which would be generous but which might decrease as the game progresses. If you don’t move in time, you lose your turn. This suggests at least one interesting strategy for winning.

The following figures show a 4-connected grid for simplicity. The actual game uses an 8-connected grid (i.e. with some diagonal moves).