Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Logic Behind Checkers AI
Index -> Programming, Turing -> Turing Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
np_123




PostPosted: Fri Oct 17, 2014 10:11 pm   Post subject: Logic Behind Checkers AI

What is it you are trying to achieve?
Started working on a Turing checkers game a while back. Been working on the program on and off, have already restarted a couple times to use a different approach. Finally decided about a few days ago to spend some time and try to finish the game up.

Functionality: already has working 2-player but the AI is a work in progress. AI is playable but kings somehow break the logic. Not too sure why.


What is the problem you are having?
Once kings are into play, whenever the player has a capturing opportunity, the AI almost always moves a second (or third) different piece into danger, sometimes opening up an opportunity for multiple jumps in the same turn.
When the AI gets a king, it only moves the king back and forth on the last row (as long as there are no imminent captures) and disregards all other pieces.


Just want to add I'm looking for more of a conceptual solution rather than code, because once I have an idea of where in the logic the problem is, I (hopefully) won't have any difficulty modifying the code responsible for implementing it.


Describe what you have tried to solve this problem

Summary of how points are assigned to moves:

Capturing a piece results in +2 points
Getting a king results in +5 points
Capturing a king results in +3 points


Logic behind choosing the best move:

Using nested for loops, the program iterates through all possible moves, and for each possible move it assigns a score using the above, performs a test move, re-evaluates and gives score of best possible opponent's move, performs test opponent's move then does the same thing one more time for added depth. The purpose of that is to try and get the AI to 'think' two moves ahead.

The score for a move is stored in an array with indices (start_x, start_y, end_x, end_y) so that the score is uniquely assigned to the individual moves. Iterating through the array with if statements returns the highest score and then the AI makes the move associated with that score.



If uploading code would help I can do that if requested, otherwise I will leave it out for the time being simply because the entirety of the program spans 2000+ lines of code and multiple files and would likely be difficult/confusing to follow due to a lack of noticeable lack of commenting in some areas.
Sponsor
Sponsor
Sponsor
sponsor
Tony




PostPosted: Sat Oct 18, 2014 12:00 am   Post subject: RE:Logic Behind Checkers AI

A way you can go about debugging this is to display the point score of the chosen moves (and maybe even of the next best alternative). See if those points are what you would expect.

Now, the point of the game is not about getting points, but getting to the win condition. The point implementation is a heuristic, and a greedy one at that https://en.wikipedia.org/wiki/Greedy_algorithm which just means "take the best scoring move right now". Such an approach can easily be lead into traps -- e.g. it would not be able to handle chess' http://en.wikipedia.org/wiki/Queen_sacrifice where the Queen is just worth too many points, but can be advantageous to give up in the long (or even short) run.

http://www.ted.com/talks/kenneth_cukier_big_data_is_better_data is a good talk on big data in general, but also has specific checkers example. Instead of points for a move, the idea was to guess at the probability that a specific board layout would lead to victory at the end. Of course this level of AI is way beyond the scope of Turing projects.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
np_123




PostPosted: Sat Oct 18, 2014 3:48 pm   Post subject: Re: Logic Behind Checkers AI

I get what you mean with the queen sacrifice example because a point system implementation would give precedence to the value of a queen over any positional gain.

Though I must say I doubt queen sacrifices are made by the average chess player unless there's some fairly immediate reward - as an average/decent chess player myself, I rarely make queen sacrifices or have good opportunity or reason to when I play but that's quite besides the point.


As for 'guessing' the probability of getting a winning board accurately, that would probably need a database of some sort to be able to cross-reference piece locations, right? And that would go on to lead to a brute-force solution where it evaluates the different board positions and the likelihood of winning for the possible resulting positions.

On a much more basic level, could you get a very rough probability by specifically checking for pieces that are past all opponent pieces and are therefore 'guaranteed' to get crowned, and by factoring in any imbalance of pieces between the two sides? Then add a search for pieces that are unlikely to reach the other side of the board anytime soon - ex. trapped on the edge of the board, unable to move without getting immediately captured. And then somehow factor all that into the AI's decision-making.
Tony




PostPosted: Sat Oct 18, 2014 4:54 pm   Post subject: RE:Logic Behind Checkers AI

Less brute-force then in a points-based approach, as you'd be looking just at just a single move (instead of your approach of looking 2 moves in). It's not so much a database search, as getting a "feel" for the board layout -- e.g. you can probably just tell that some boards are much easier to win than others. All of the complexity is in developing this guessing mechanism through practice (in machine learning case -- data), but once developed, accessing it is fast.

All of this is not the recommended approach, but just for your interest.

Step 1) make sure that the points are calculated as expected, with the kind of debugging I've mentioned first.

Step 2) you can implement some of the machine learning ideas, to adjust the point weight. E.g., right now getting a king is +5, and losing a king is -3. If you were to get this +5/-3 AI to play against +5/-5 AI, who would win more often? You can test all kind of point combinations to find the best parameters for your AI implementation.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
np_123




PostPosted: Sun Oct 19, 2014 12:27 am   Post subject: Re: Logic Behind Checkers AI

using the concept you suggested of 'guessing' the probability of a winning board, I rewrote the code for the AI. It didn't take that long to implement the new logic, plus it's working pretty good.

As far as I've noticed, the main problem is the endgame because the AI hangs around the edges of the board with its kings rather than trying to win the game. So unless it has a large piece advantage, that typically means that the human player ends up winning. If the AI has the advantage, then game doesn't end (and I close the program) because the AI currently has no interest in getting the win.

So my next step will likely be adding in an exception that when most of the pieces remaining are kings, the program goes into a secondary execution loop with a different evaluation scheme of the board. Shouldn't be overly difficult, seeing as I already pretty much just rewrote the entire AI.



Checkers.zip
 Description:
Checkers with AI

Download
 Filename:  Checkers.zip
 Filesize:  18.22 KB
 Downloaded:  229 Time(s)

Display posts from previous:   
   Index -> Programming, Turing -> Turing Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 5 Posts ]
Jump to:   


Style:  
Search: