Members - Reputation: 122
Posted 14 August 2007 - 10:05 AM
Members - Reputation: 869
Posted 14 August 2007 - 10:34 AM
You write a function that looks at the board and the possible moves and determines which move is the best. To determine the value of each move, you can use the same function to evaluate how good the board resulting from each move is for the opponent. Your goal is to maximize the value, and the opponent's goal is to minimize the value. The opponent will choose the move that results in the lowest value. To find the value of each of those moves, we're back at the beginning trying to evaluate the player's position, and choosing the move that results in the highest value.
The recursion can continue all the way to the end of the game (assuming that you can detect infinite loops and/or there are rules that would prevent them). When the player wins the value is high, and when the opponent wins the value is low. For small games this approach creates a perfect player that looks at every possible move and finds a way to force a win whenever possible. For large games the game tree is too big so the recursion needs to be terminated before the end of the game. Usually a heuristic function can be used which tries to evaluate how good a board is, with better boards having higher values. The tree can then be searched to some limited depth.
There are some tricks to speed things up, like alpha-beta culling, and searching to a lower depth but expanding interesting positions further to focus the search on the more interesting possibilities. There are also hashing tricks to avoid having to compute a value for a state that has already been visited. There's plenty more information about this stuff on the internet.
Members - Reputation: 824
Posted 14 August 2007 - 07:18 PM
Quote:AI for two-player games with perfect information (i.e. checkers or chess, but not poker or stratego) is typically implemented through variants of the minimax tree-search algorithm, so you want to start reading up on minimax (or one of its variants, such as alpha-beta search, MTD(f), etc).
Original post by Warhell
I was wondering if anyone knows of a good source or some good tips on programing AI for checkers? I would like to make an easy, medium, and hard AI.
If you want to go beyond the basics of implementing a bare-bones minimax search, you can start reading up on what others have done, in particular the publications on Chinook.
Members - Reputation: 505
Posted 15 August 2007 - 04:51 AM
For those interested, I just recently saw a publication in which checkers was solved. Much too much number crunching for your purposes, but interesting nonetheless.
Also, Blondie24 is another interesting read. In this one, they developed a neural network that evaluated the board and that was used as the score for a minimax algorithm. The neural network was developed using an evolutionary computation appraoch. Again, probably not a solution for you, but interesting stuff. 8^)
Moderators - Reputation: 3435
Posted 15 August 2007 - 09:25 AM
The next possible cut would be based on the number of opponent pieces left. Or the delta between the two sides. Even that can be problematic, however, since there isn't a definative move toward a board state. If you each had two pieces left, perhaps only 5% of the moves would change the board state. That leads to a pretty large explosion of branches. Hmmm...
So what are the criteria for an advantageous board?
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
Crossbones+ - Reputation: 19083
Posted 15 August 2007 - 10:11 AM
On top of that you can add a piece-square table that will give a higher value to pawns in the center and in the back row. You may need the help of a good player to adjust those values. Then you can start defining patterns that are worth some points. A pattern is described by a mask indicating what part of the board has to be compared, plus a description of what should be in that part of the board in order to get a match. If you use bitboards, you can describe a pattern with 4 of them (mask, white_pieces, black_pieces, kings) plus the associated bonus score. You can probably get something faster using a decision tree.
With patience and an expert player to help you, you can get pretty far with this scheme. Of course you'll need a good search algorithm to go with it. I would start with alphabeta with transposition tables, and then try PVS and maybe even MTD(f) (although I've never managed to make MTD(f) work well). Then you'll need to generate an endgame database (essential in this game), so you can access the theoretical value of any position with less than N pieces with a simple lookup. You can also work on an opening book, or on some mechanism to remember scores of positions you have visited before.
This can keep you busy for several years, and it's a lot of fun. However, it would probably be better to try with a less-understood game, like go.
Members - Reputation: 122
Posted 17 August 2007 - 06:58 AM
Crossbones+ - Reputation: 19083
Posted 17 August 2007 - 08:28 AM
* A representation of the board
* A representation of a move
* A function that generates all the legal moves from a given position
* A function that gives you an idea of who is ahead. You can start with material difference and build from there
Once you have that, you can read what Bruce Moreland wrote about chess programming. Most of it applies to checkers directly. Two notable exceptions are the null-move heuristic, which doesn't work well in games like checkers where Zugswang is common, and the quiescence search, which is really essential to make a chess program, but in checkers can be substituted by the simple rule of not stopping the search after a capture (you could substitute that rule by "not stopping the search if a capture is possible", but it's probably harder to program).
If you find Bruce's pages too overwhelming, I can write some pseudo-code for you, with only the basic things that you can implement in a couple of days.