Registration

Proposals
Interims
Final Reports

Dates

Kickoff
Evaluations
Expo
STI
Wiki

School Map
Sponsors

Mail

Challenge
Technical Guide


Past Participant Survey

GUTS

Challenge Team Interim Report

Team Number: 023 School Name: Albuquerque Academy Area of Science: Computer Science/Artificial Intelligence Project Title: Decision Making Through Intelligent Imitation

PROBLEM DEFINITION: The first thing we learned in our Computer Science class was that computers are stupid. They are stupid but they are amazingly fast. This speed has allowed stupid computers to beat smart people in chess; it has allowed computers to continue to update the precision of pi even today. If we give computers simple instructions, they can convert them into complex calculations by repeating the instructions millions of times. Our team wants to see how we can use this power in the most complex board game in the world: chess. Computers have already been taught how to play chess--and they continue to get better. Can computers do other things in chess? We will find out. The big question in chess is whether it can be mastered or not. No one--computer or human--has been able to do it. The title "chess master" is only relative, because chess masters play each other all the time but only one of them wins.

Chess is known to have an infinite number of possible combinations in its play but in theory the number is finite. Someday there will be computers big enough to perform the task of finding, "the perfect game", a game where every move is "perfect" (meaning that there is no other move that could have been as good as the one made). Would there be a draw? Or would the fact that white gets to start first allow him a win? If the latter were true it would mean that a chess game is technically a game of chance: whoever gets to be white wins. Or it might be like tic-tac-toe where if the players know all the right moves no one will ever win. It depends on the mistakes made during the game. Someday a computer will reach this mastery and human players will never be able to beat computers again.

In conclusion, computers can teach us a lot about chess and we want to see what we can learn from them.

PROBLEM SOLUTION: We will write a program that abides by the rules of chess. It will consist of a virtual board and virtual pieces. The meat of the program will be in its array structure. Arrays are tables of data that can be of different dimensions. They are used in programs to store large amounts of information quickly and retrieve them quickly.

One of the reasons we chose Java is because it is the newest big computer language. It was written to fit modern needs, such as the Internet, but also to fix many of the problems in previous languages. Java has the best system to use arrays; they are easier to use, for one they automatically set every element in the array to zero. It is also easier to set up one array with several dimensions.

In our program the chessboard will be an array, we will write instructions and algorithms that make sure the rules of chess are followed. The program will then populate an array for every piece containing information on each piece’s legal moves. Each move in this array will correspond to another array that contains information on what each of the possible moves will accomplish. The move will then be given a rating based on many different parameters: what pieces the move ceases to protect, what pieces it will attack, what part of the board it’s attacking, and many more. Our program will have the computer randomly decide what each of these perimeters should be worth, and then it will make the move that gets the highest score based on the perimeters. The computer will play itself with two different guidelines selected by the computer randomly. Every time one side wins it will keep those guidelines and the losing side will randomly select others. The losing guidelines would be stored to prevent them from being used again.

This is our basic concept for a self-improving chess program. As we go on we might modify it to start to intelligently select guidelines based on comparisons between the guidelines that won games and lost games.

PROGRESS TO DATE: We have studied and learned a lot more about Java these past few months. Our knowledge of the language has grown drastically and has helped us come up with a much more concrete idea for our program. We have worked on simpler chess-based projects, including "The Nights Tour" problem, where we use computers to find what moves a knight has to make to be able to land on all 64 spaces on the chess board only once. We learned a lot about how to get the computer to move the knight. We devised algorithm’s that made sure the knight wouldn’t be moved off the board and algorithm’s that would make sure the moves made where completely random. We got the program to output every move the knight tried and where it got to every time it got stuck (when it gets to a place where there is no place the knight can move to without landing on a previously "touched" square). We learned from many mistakes we made and we realized how complex our program idea was going to be to complete. One positive aspect of our idea is that the program doesn’t have to be completed to perfection to work and teach us about chess. Seeing how the program works at a lower level of complexity can also give us an idea of how it would work at a higher level of complexity. The knight’s tour problem wasn’t very complex, but it accomplished a task that would take humans a long time. It would take a human less tries, but each try would take him 100 times more time than it would take a normal computer. What we have learned has allowed us to come up recently with our concept for the Super Computing project and we are in the process of writing the pseudo-code for it. The most exciting part will be to see what a supercomputer can do with our program, and what results we get.

We are currently in the process of learning the visual aspects of Java and we hope to be able to show the results of our program with Java GUI’s that give a visual representation of the board.

EXPECTED RESULTS: Our program will be able to teach us many things about chess. It will be interesting to see what the algorithm is for the best move in a chess game by looking only one move ahead. How well will a computer or human play by using this algorithm? An example is the well-known fact that the best way to start off well in a chess game is to gain control of the center. That is why the most common first move in a chess game is pawn to e4. Will our program figure this out? If not how can we modify the program to figure this out? These are some of the perplexing questions that we will answer, and as we continue with the program, more will come up. With the knowledge gained from our program we might be able to devise programs that would replace human jobs such as creating chess puzzles in newspapers. In truth, the core of chess is based on hard math. Math is what computers are best at, and we hope to see how they handle the calculations involved in chess.

Team Members

Team Mail

• Matt Mehne
• Aaron J Garcia
• Jason J. Cox
• Peter Cockran
• Ronald Nicks

Sponsoring Teachers

• Jim Mims

Project Advisor(s)

• Jim Mims