You are invited to Log in or Register a free Frihost Account!

AI evaluation function

How do I create a strong AI for Baghchal?

I have used the minimax algorithm with alpha beta pruning and it seems to be working fine. However, the evaluation function doesn't seem to be accurate enough. Hence the program is not playing very strongly, as computers should. What is the process to find an accurate evaluation function? Confused
It is important that the evaluation function returns the highest value on a "win state" and the lowest value on a "loss state". I have never played this game but I was thinking that maybe you can use some of these in you evaluation function:
  • Number of goats left.
  • Number of goats that are safe and can't be captured at their current position.
  • Number of tigers that are blocked and can't move.

I think the accuracy of the evaluation function is more important if you can't look ahead very far. It can be worth having a quicker, less accurate evaluation function compared to a slower, more accurate evaluation function if that means you can look ahead further.
Thank you for your reply. I have used a few of those parameters. Here's the code:

int AI::TigerEvaluatePosition()
    if (TigerWinCheck())
        return +INF;
    if (GoatWinCheck(board))
        return -INF;

    return (5000 * aiDeadGoats + 200 * PossibleCaptures() - 100 * TigersTrapped(board) + 50 * cornersOccupied);

It can go upto a search depth of 10 in the highest level. However, it plays the initial stages of the game very slowly due to the high number of possibililies. Hence, I have edited the code so as to use a search depth of 6 when the number of goats to be placed is greater than 10 and then switch to the higher search depth after that.
To me it looks like the evaluation function cares too much about the dead goats compared to the trapped tigers. This will probably have the effect that the goat team will do everything it can to not lose a goat and is never prepared to sacrifice a goat in order to trap a tiger, and the tiger team will probably don't care very much if it is captured.

Well, I have not played the game so I could be totally wrong. Anyhow, I think optimizing it so that you can search deeper could greatly improve the AI.

Just to get the hang of the game I watched this youtube video.
What I don't understand is why the goat team doesn't win at 4:36.
I think the central tiger had a diagonal capture at 4:36.

Well, as you know, I have successfully completed the game. However, as they say, we never really finish coding a program, we just stop working on it.

So, I have decided to re-open the project files and begin improving the program. The evaluation function seems to be pretty solid. Many good Baghchal players that I know have lost multiple games to it.

However, I am now faced with a more difficult problem: one of repetition. This game seems to break down due to repetitive moves (especially when the AI is playing the goat side). The problem is that when it is losing, it creates a hole at the edge, one which the tigers cannot control. Then, it keeps moving a single goat back and forth in that empty square, no matter what the tiger side plays. I have tried very hard to prevent this, but have been unsuccessful so far.

My solution was to record the game state at every move. The game state consists of the board position as well as the turn. I created a new class for it. I also used a static function for comparing two game states and returning either true or false. Now, this only comes into effect after all the goats have been placed: At each move, a new game state is saved. Once the counter reaches 10, I start overwriting the previous game states. Also, before making any move the new game state is checked against all the previous game states, so as to avoid repetition.

In this way, I prevented repetition spanning 5 complete moves (10 ply). However, I faced a few problems. The most significant one was that there were a lot of cases where it gave a false positive, i.e. declared a state to be repeated even if it was not. Another problem was that it prevented a move even if it was the only move remaining, if it repeated the previous position.

Hence, I had to scratch the non-repetition feature from the program for now. How would you implement this feature? If you need to have a look at the code, I shall provide it to you.

Thanks in advance, and sorry for digging up this old topic.
I found a link and thought this might be helpful
It is such a great game.
Related topics
PHP Mail Function
PHP function(); &file=""?
Graphistes - J'ai besoin de vous!
Search function
ftp function
Algum Brazuca ai?
DotA - Alguem ai joga?
Dreamweaver or Golive?
Function "Rotate90", how do do it guys?
javascript function not being seen
un site sur des trucs que j'ai vendre
Help - SVG to AI or CDR Converter
Free board game
Reply to topic    Frihost Forum Index -> Scripting -> Others

© 2005-2011 Frihost, forums powered by phpBB.