Registration Dates Kickoff Proposals Interims Evaluations Final Reports Expo STI School Map Sponsors Mail Discussion Forum Technical Guide Past Participant   Survey
Supercomputing Challenge

# Twelve Men's Morris

Team: 9

Area of Science: Artificial Intelligence

Interim: Problem Definition:
In today’s world, artificial intelligence is becoming a prominent topic in the computer world. Artificial Intelligence is now used by scientists to handle hazardous materials, play chess, and even vacuum the floor for you. While we continue to make breakthroughs in this field, we will use AI more and more in our daily lives. Anyone who has played a game of chess or checkers on his computer has used AI before. AI is important because it allows machines to things people can’t, like lift a three ton car to save a child from a fire or take measurements from an active volcano. In the future, AI will become extremely important to society as a whole, as it is already on its way to being.
The goal of our project is to take Twelve Man’s Morris, which is a game as old as the Roman Colisseum, and make it so it can be played on the computer. Twelve Man’s Morris is a board variation on Nine Men’s Morris. Morris has a square board with intersecting lines, where each intersection is a place where a piece can be placed. Each player starts with 12 pieces. The players take turns placing the pieces. For this part, we will give the computer preferred places to put its own pieces, and some simple strategy regarding where the other player’s pieces are, and how that affects the computer’s moves. The second stage of the game is where you move the pieces. You move one piece a turn to any open adjacent square. If you get three in a row of your own pieces anywhere one the board in a straight line, then you get to take one of your opponent’s pieces off the board. The first person who loses all their pieces loses their game. The challenge of this project is to develop AI so that the computer can play this game against a human effectively.

Problem Solution:
The board will be set up graphically, and we will create two arrays for stage 1 of the game. We will give the board preferred moves in one array and taken spots in another array. After positioning the pieces on the board, the AI will figure out which is the best move at that time on the board. The AI will try to find ways to make three in a row, and perhaps keeping your opponent from forming their own.

Progress:
We have gotten the board up and running so that we can see it on the computer screen. Later, we might try to use a more sophisticated graphical style, but for now we will stick to lines and dashes. We have also started to create the algorithms needed. The first one that we have been working on is to place the pieces. The way we are attempting to do this is to play the game ourselves many times so that we will be able to see where the best moves are, so that we can use our knowledge of the game to program the AI. Right now we have the game split into two parts: Placing the pieces and moving the pieces. For moving the pieces, we will try to program the AI so that it will respond to the opponent, instead of having a large database of scenarios.

Expectations of this Project:
At the end of the project, we expect the game to be presentable, and working. We expect that if anyone would sit down and play the game against the computer. The computer needs to be able to put up enough of a fight so that the player must think. The AI must be able to function so that the computer can play the game well. If we can accomplish this game, we can use it as a springboard for more complicated AI schemes, and we will have a greater understanding of the development of AI.

Team Members: Vlado Ovtcharov and Brandon Oselio

Citations:
http://members.aol.com/farisles/guilds/merels.htm
http://www2.kumc.edu/itc/staff/rknight/Game4.htm
http://www.msri.org/publications/books/Book29/files/gasser.pdf
http://www.mastersgames.com/rules/morris-rules.htm
http://www.yorkcitylevy.com/modules.php?name=News&file=article&sid=6

Team Members: