[Help] Board Game
Hi. I've written a board game (Awale) which only allows two human players to play against each other. What I want to do now is to write an AI for the computer. The problem is I haven't got any clue how to implement the AI. Do I need to calculate every possible move for the AI and determine the best move which leads to victory. Or do I need to use nested if ... else ... to code my winning strategy (the program will be very huge then, won't it?)? I'm very new to game programming. Could someone please help me? Thanks in advance.
[542 byte] By [
ngweihanga] at [2007-9-29 18:41:30]
Start with something simple: in your docs that you downloaded with the jdk/sdk you should have a folder called 'samples' and there you will have a tic tac toe game. Deconstruct the logic in the algorithms there. As for AI ... well some games do run through every permutation, though not always. And yes - the algorithms rely on boolean conditionals which may be if-else or case-switch.
- > Easiest to implement: beginner level, the computer makes a 'random' move.
- > Fun to implement! (which may be quite hard depending on the game, but definitely fun to work out if you like algorithms and logic): expert level, the computer makes the 'perfect' move.
- > Hardest to implement: intermediate level, the computer sometimes makes the perfect move and sometimes makes the 'second best' move available - tricky.
Without knowing what "Awale" is, we can't give you any specific help.
But you should do searches on the following topics:
- MinMax algorithms.
- Finite state machines (or FSMs).
- Neural nets (very advanced, so brace yourself).
A few nice links for AI:
http://www.generation5.org/
http://www.gamasutra.com/ (for general gaming issues, but there will be a lot of material on AI).
Hope this helps you,
shmoove
Thanks for your help guys.
Awale (http://www.doc.ic.ac.uk/lab/cs1/lab_area/GiveToStudents/Java_Owari.pdf) is a simple board game. Each player has 6 possible moves (provided there are stones in all bowls on his side). I've written a simple method which returns the move which captures most number of stones. It doesn't seem to be a good idea as I can beat the computer easily.
How to write an algorithm which computes the best move?
One way to do this is to make a tree. The root node is the current state of the board. You then compute every possible move the computer can make and create child nodes for the state of each of those moves. Then iterate over the children and do the same thing. You can continue this for a certain number of levels (3 moves ahead) or for the rest of the entire game. That decision would be based on how much processing would be required to compute every possible move.
The tricky part is finding an algorithm to give you a "score" of each node. Then you can iterate the leaves (end nodes) and find which has the best score. Then traverse up the tree to the first level and make that move.
Michael.
You could try a heuristic algorithm, each time the algorithm gets beaten make it change its behaviour in a number of ways. If you code this in such a way that you can serialise the algorithm object you can have a persistent 齜est?algorithm in your code. Also you can set one generation of the algorithm against other generations. Again like the other solutions there are design problems you need to overcome; in this case it is deciding what variables the algorithm uses to change its behaviour.
In this case you could use a weighting system where firstly you assign a weight to each of your 齪ockets? then assign a weight based on the number of 齜eans?in each pocket and finally assign a weight to your pockets based on the number of beans in each of the opposition齭 pockets. Your heuristic method would only modify these when it had lost a game. If it is beaten it would change some or all of the weights and hopefully play a better game.
Hope that is helpful and good luck :)
Thanks guys. =)
I guess MinMax algorithm is what I need. It's kinda similar to what Michael's suggested. As he's said, the only tricky part is assigning a "score" to each node.
I found the following MinMax pseudocode on the web. I don't quite get what EvalGameState(game, MAX) does. Could anyone help? Thanks.
MinMax (GamePosition game) {
return MaxMove (game);
}
MaxMove (GamePosition game) {
if (GameEnded(game) || DepthLimitReached()) {
return EvalGameState(game, MAX);
}
else {
best_move <- {};
moves <- GenerateMoves(game);
ForEach moves {
move <- MinMove(ApplyMove(game));
if (Value(move) > Value(best_move)) {
best_move <- move;
}
}
return best_move;
}
}
MinMove (GamePosition game) {
if (GameEnded(game) || DepthLimitReached()) {
return EvalGameState(game, MIN);
}
else {
best_move <- {};
moves <- GenerateMoves(game);
ForEach moves {
move <- MaxMove(ApplyMove(game));
if (Value(move) > Value(best_move)) {
best_move <- move;
}
}
return best_move;
}
}
>> I guess MinMax algorithm is what I need. It's kinda similar to what Michael's suggested.
Yup, it's exactly what Michael suggested.
>> the only tricky part is assigning a "score" to each node....
>> I don't quite get what EvalGameState(game, MAX) does.
EvalGameState would be the tricky score assigning method.
shmoove
Eval game state is a method that looks at a snapshot of the current game and analyzes which side is winning using heuristics instead of searches. For example, in a chess game, each type of piece could have a point value, and to evaluate the game, you could simply sum up the total for each player and use the difference. Of course, there could be better evaluation methods that take position into account, but it is up to the designer to decide how complicated to make the evaluation. The purpose for having this method is that usually, it is unfeasible to traverse the entire tree of possibilities, thus the evaluation can give an estimate of what may lead to a win.
On a side note, another nice thing about the MinMax algorithm is that it can be easily modified to prune off large chunks of the search tree (alpha-beta pruning). After you reach a leaf of the search tree, you have a floor and ceiling that if a calculated value is outside those bounds, nothing in that branch will be used anyways so stop searching that part of the tree and continue on.
I hope this helps!
-JBoeing
I've written the AI for my game. Thanks everyone for giving me idea. Cheers! =)
Hi. I have another question regarding the AI I've written. Basically, the aim of the game - Owari, is to capture more stones. The player who captures more than 24 stones wins. I used minimax algorithm in my code. And what my evalGameState method does is returning the difference of the scores between two players. MAX picks the way which the scores difference is > 0 (and MIN picks < 0). So far, no one's beaten my AI (myself, friends, and one of my friend's AI). And most of the time the scores are very close, say 24-22, 24-20. Now my friend is trying to do what I did (use minimax). My concern is, if he used minimax algorithm as well, would his AI beat my AI? Can I make my evalGameState method even better?
> Now my friend is trying to do what I did (use minimax). My
> concern is, if he used minimax algorithm as well,
> would his AI beat my AI? Can I make my evalGameState
> method even better?
Hard to say without seeing it, but if I recall Awari, isn't there
a way of "capturing" opponents stones by ending on an empty
pit ?
You could evaluate giving higher/lower scores for capturing
stones from his side, or leaving stones "vulnerable" on your
side.
The Owari I've written is a simplied version. One can capture stones in a bowl as long as there is only one stone in it before a move is made, and regarless of on which side the bowl is.
Perhaps I should read up more about minimax and to make it more efficient (now it only evaluates 10-ply deep).
