GeSHi © 2004, Nigel McNie.
This is a Checkers AI backend. It is used to generate one move
in a checkers game.
Prog4 filename [levels] [R | B]
-filename This is the name of the file that contains
the properly formatted checkers board.
-levels This is an integer representing how many
levels of recursion the program should check.
[R | B] This is the color that the program should
play, Red or Black.
The program uses an Alpha-Beta pruned Min-Max tree to calculate
what the best move is. The algorithm is a standard one, that was
found on the internet in three different forms. By taking concepts
from each of the three sections of pseudo-code that I found, I was
able to make the algorithm work correctly.
The Heuristics algorithm that I used operates as follows:
1. Number of pieces you have left
2. Number of pieces they have left
3. Number of your pieces they can jump
4. Number of their pieces you can jump
5. Number of spaces on the Board you can no longer reach
6. Number of spaces on the Board they can no longer reach
7. Number of pieces on your back row
8. Number of pieces on their back row
9. Balance of your pieces, Left/Right
10. Balance of their pieces, Left/Right
1) When I originally wrote the program, I assumed that red pieces would
be on top, and black pieces would be on bottom. I didn't realize this
was opposite until about 2 hours before the time the program was due,
so I did a quick fix to get around this that involves reversing the
board a few times. As far as I know, this worked, but I was not able
to test this as much as I would have liked to, specifically, I'm no
longer sure if multiple jumps work properly. I am sure, however, that
multiple jumps do still ocurr, so it may still be functioning correctly.
2) I have included with the program a Front End that I wrote while testing.
This front end interacts directly with the classes that I wrote, and
skips the file I/O steps. If you wish to use it, you should be able to
use qmake to create a makefile and build the program. I have included
one called MakeGUI, but I don't know if it will compile on a different
version of QT. The front-end does not do any checking to see if you have
performed a legal move, but just passes the board in its current state
to the AI. Here are a few quick notes about this front end:
-Any square can be made any color, click them to cycle
-Click "Submit Move" to see what the AI's response is
to the current board state.
-The AI will play the black pieces