CS4341 Introduction to Artificial Intelligence
Due Date: Tuesday, February 8, 2000 at 6 pm.
PROJECT 1 - C 2000
This project consists of developing and implementing
a computer program that plays tic-tac-toe against another player.
Tic-tac-toe is a two player game (one of them being your computer
program). The two players take turns putting
marks on a 3x3 board. The player who first gets 3 of his/her marks in a row
(vertically, horizontally, or diagonally) wins
the game, and the other loses the game.
A game will consist of a sequence of the following actions:
- Initially, your program should ask the user
which marks the user prefers ("X" or "O").
The player that gets to play with the "X" marks will play first
(we call him/her player 1) and
the player that gets to play with the "O" marks will play second
(we call him/her player 2).
Player 1 and 2 take turns making moves.
A move (mark row column) should satisfy the following
- Time Limit
There is a 1 minute time limit for a player to make his/her move.
(1 min. user time, not CPU time.)
- Move preconditions
- mark is "X" if it is player 1's turn and
"O" if it is player 2's turn.
- The position (row, column)
on the board is empty.
- Move postconditions
- After the move, the position (row, column)
on the board will be occupied by a mark .
- It will be the other player's turn.
- The game ends when either:
one of the players wins the game, i.e. this player
gets three of his/her marks in
a row (vertically, horizontally, or diagonally).
- all the positions on the board are occupied. In this case,
the game ends in a draw.
The project assignment consists of the following:
- You should implement a computer program that plays tic-tac-toe following
the rules described above.
- Your program should use:
The better your game strategy, the better your grade in the project.
- minimax with alpha-beta pruning, and
- a game strategy:
- Use utility and evaluation functions of your choice
- Use a heuristic of your choice
(Finding a good static evaluation function and a good heuristic
depends heavily on the experience you have with the game.
I recommend you start playing the game and getting the flavor
of what a good tic-tac-toe strategy is. Also, research the strategies
that other people have used for this and other games.
Lots of information can be found in the references listed in
your syllabus, the web, and magazine articles.)
- You can design the program-user interface as you like, but make sure
that your program is *easy* to use (avoid having complicated input codes).
Shortly state the interface conventions to the user at the beginning of
and display the configuration of the board after each move.
- Your program should produce only valid moves.
- Your program should verify that each of the opponent's moves is
valid, and should execute them.
- Your program should detect if the game has come to an end, and if
so, it should print a message stating who wan.
REPORT AND DUE DATE
Project 1 is due on Tuesday, Feb. 8 at 6:00 pm.
Code documentation should follow the
Departmental Documentation Standard.
One (and only one) member of each group should submit the following
files using the
- proj1_readme.txt: Containing the list of members of the group
and the programming language used to write your code.
- proj1_code.txt: Containing
the source code of your program.
Your program should run on a UNIX platform on the CCC machines.
Make sure that any software that your program requires is available on the
Your report should discuss the following issues:
- the static evaluation used by your program,
- the heuristics employed,
- chosen ply for minimax and alpha beta pruning,
- describe which tests you run to try out your program.
Did you program played against human players?
How did your program do during those games?
- describe the strengths and the weaknesses of
- include a printout showing the execution of your program
on a couple of games.
- short user manual explaining how to install, run, and use your
- proj1_runs.txt: Containing a transcript
showing the execution of your program on a couple of games.
There are several web pages where you can find more information
about tic-tac-toe and/or where you can play tic-tac-toe.
Just a couple of this web pages are listed below. I encourage you to find
more sites about the game using a net search engine.
You may benefit from seeing other implementations of the game,
BUT YOU MUST DEVELOP YOUR OWN TIC-TAC-TOE PROGRAM.
Beware: some programs on line may use a set of rules
different to the one describe above.
If you find a web page with useful information about tic-tac-toe,
please let me know and I'll add it to the previous list.