Basic Checkers AI

[Sm0e]

I am a relative beginner at C++. I make no claims that AI is easy- I know for a fact coding AI is hard. However, I would still like to try, so how would I go about a basic checkers AI that can at least play the game?

[hamsterman]

checkers is a fairly complex game. You may want to start with tic tac toe, connect four, etc.

[nano511]

When i made a tic tac toe game my AI did this..

First check if i can attack( in this case, eat a player )
Next check if i can be attacked( in this case, move out of the way of a possible attack )
If neither of those, then random move

[Sm0e]

@nano511, what kind of code would I need for that variety of AI?

[nano511]

A whole lot of if statements lol.

No seriousy, a LOT of if statements

EDIT: I dont think this would be a good project for a beginner though :/

[hamsterman]

With any kind of AI, the most simple method is
find all possible moves
for each move, decide how good or bad it is
find the best one.

Second step is, as hard as you want it to be. You can remove it entirely and pick a random move. The last one is trivial. The first one may be hard, depending on how skilled you are and how complex the game is. Choose any game where you think you can figure it out, then play around with the second step. It might be fun.

[quirkyusername]

look into the minimax tree search, to give you a clue as to how you would use a tree for AI imagine the empty board at the start of a game being the root node of the tree and each node coming off of it being a different starting move. You can plot all possible moves up to the point of a game over and return the best as hamsterman said using a minimax search.

EDIT - also I agree with hamsterman that checkers is hard for a beginner, tic tac toe is perfect for a minimax search.

[jsmith]

Nay, tic tac toe is too simple for minimax. Connect four is better for minimax.

But in reality, all 2-player turn-based abstract strategy games like this can be coded using the same (extremely) high-level algorithm:

Given the current board position, player-to-move, and search depth
0.  If the search depth is 0, call an evaluator function to assign a value to given position, expressed as a positive number if the player-to-move has the better position, negative number if the player-to-move has a worse position, or zero if the position is equal, and return the value.
1.  Generate a list of all possible legal moves
2.  For each move:
     a.  Make the move
     b.  Recursively call this function, with the new board position, other player-to-move, and search depth - 1.
     c.  Store off the negative value of the board position (returned by the recursive call).
     d.  Unmake the move
3.  Return the maximum of all the values you stored, along with the move that was associated with it.
4.  Finally, after the initial call returns, make the move returned.

Pick a search depth of say 7 or 8, or higher if it doesn't think too long. Start by making your evaluator function very simple: Count +1 for every checker of your color, +2 for every king of your color, -1 for every checker of your opponent's color, and -2 for every king of your opponent's color.

You'll find that even with this simplistic evaluator, the fact that the computer can "think" ahead perfectly 7 or 8 plies makes it a reasonable opponent for the average player.

[Note that with this evaluator, the computer will not win, because it won't know how to win 2-1 or 3-2 king positions, but it won't be beaten that easily either. You can worry about that part later.]