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