Hi. I'm new in checkers programing. I decided to program checkers with AI for my high school project. Today I get it works but I'm a little disappointed. AI play fine till endgame phase then it starts doing stupid moves or get in loop. I'm wondering if someone can take a look at my program and tell me what is (or can be) wrong or maybe isn't but program need more improvements. I analyzed source code many times and can't find any errors. I'm using min-max with alpha-beta and simple evaluation function(1 point for men, 3 points for king) AI move time is reduced to 1 sec. I get 10 to 15 depth depends on board situation witch in my opinion isn't so bad for first working version. I'll be grateful for any informations.
http://hotfile.com/dl/61812523/65a4c91/Release.rar.html
Checkers project
-
Ed Gilbert
- Posts: 859
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Re: Checkers project
Endgames in checkers are a lot about king mobility. You want to encourage kings to be near the center, and penalize kings that are at the edges and especially kings that are trapped, that cannot move at all or only can move within a small space. You also want to encourage men to advance closer to the king row, and detect if they are within a few rows of promotion without any opposition (runaways). Your relative weights for kings and men are too high for checkers. Most checkers programs use something between 1.3men and 1.5men for the value of a king, but if one side has a mobile king and the other does not then you can award a substantial bonus for that.
To avoid repeated moves you need some form of repetition detection. When you see a position in the search that has already appeared at a position closer to the root then that position can be returned as a draw value. To detect this you need to keep either an array of positions indexed by ply, or I think some programs do it with a hashtable.
Your graphics are nice. I found the side by side board configuration a little disorienting though. I like to see my side of the board at either the top or the bottom of the screen to be more like a game using a real checkerboard. Also it is hard to comment about the program's search because there are no search scores or pv displayed.
-- Ed
To avoid repeated moves you need some form of repetition detection. When you see a position in the search that has already appeared at a position closer to the root then that position can be returned as a draw value. To detect this you need to keep either an array of positions indexed by ply, or I think some programs do it with a hashtable.
Your graphics are nice. I found the side by side board configuration a little disorienting though. I like to see my side of the board at either the top or the bottom of the screen to be more like a game using a real checkerboard. Also it is hard to comment about the program's search because there are no search scores or pv displayed.
-- Ed
Re: Checkers project
Thank You for answer Ed. One more question. I noticed something weird. I let AI play both black and white side and watching results but sometime games look different and finish different way. I disabled time limitation and set constant depth. I'm little confuse, because in my opinion every time ai should play same way or maybe I'm wrong?
-
Ed Gilbert
- Posts: 859
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Re: Checkers project
This can happen if you have some program state that is not cleared between searches. For examples, a hashtable, history table, or killer move table. If you don't think you have any program state that is not cleared then I think you probably have a bug, as then every search from the same start position to the same depth should return the same search score and best move and visit the same number of nodes.I let AI play both black and white side and watching results but sometime games look different and finish different way. I disabled time limitation and set constant depth. I'm little confuse, because in my opinion every time ai should play same way or maybe I'm wrong?
-- Ed
