Minimax Evaluation Function

Question

I'm developing the mini-game Triple Triad seen in the game Final Fantasy VIII using Unity3D.

The basic game is a 3x3 grid, where the player and NPC hold 5 cards in their hand. The objective is to hold the most cards by the time the board is filled up. The cards hold 4 numbers on the top, bottom, left and right sides. A player places a card down on the grid and the other player can place one next to it, after which the numbers on the cards will be compared (e.g. if a card was in the middle and the opponent played one to the left of it, the right value of the opponent card would be compared with the left value of the card already there). If one card is greater than the other then the player will 'take' the opponents card.

More details about Triple Triad can be seen here: http://finalfantasy.wikia.com/wiki/Triple_Triad

I'm currently designing the AI for single-player usage so a human can play against an NPC. I have decided that the best way of developing the AI would be using a Minimax algorithm with alpha-beta pruning in order to work out the best possible move for the AI on their turn.

The problem I'm having is that the majority of examples I see on the internet show the evaluator function for tic-tac-toe. This is a lot simpler than the triple triad evaluator would be because the function would have to take into account the values on the card as well as the position it is being played in (e.g. taking an enemy card).

Does anyone have any tips on how I could code this evaluator function? Or at least how I could adapt the code from this site into one that would evaluate my board for triple triad?

http://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

A quick read of the linked page gave me the impression that a player has inclomplete information (unless the "open" variant is played) Imperfect information would imply that no "full" evaluation is possible. You could need UCT / MCTS. — wildplasser, Nov 14 '12 at 23:40
Possible duplicate of http://stackoverflow.com/questions/13237837/min-max-evaluation-function-for-a-game#comment18034812_13237837 — A. Webb, Nov 14 '12 at 23:41
[This answer](http://stackoverflow.com/questions/12666119/using-minimax-search-for-card-games-with-imperfect-information/12684468#12684468) is relevant to your situation, as the related card game has similarly incomplete information. — Kyle Jones, Nov 15 '12 at 21:23
In general an AI player of such a game should start out using hueristics and assume the other players are doing the same. Based on the other players actions, you can deduce their hands with increasing probability assuming that they are playing optimally. As the AI learns about the other players' hands, it can start incorporating search to explore possible endgames because knowledge of the players' hands makes the search tree sizes manageable. — Kyle Jones, Nov 15 '12 at 21:23

score 3 · Accepted Answer · answered Nov 14 '12 at 23:49

There are two flavors of evaluation function: If you can see the end of the game (as you always can with tic-tac-toe, even if you're running on a Commodore 64) you can base the result purely on whether the outcome is successful. The game engine will then only pick moves that win (or, if possible, tie).

If you can't see the endgame, which is by far more common in any interesting game, you need a function to score an intermediate board position in a way that measures how it favors each player. In Chess, for example, you might assign point values to each piece and add up how much material each side has and subtract. Thus the AI will favor ever greater material advantages. Then you give the evaluator bonus points for putting the opponent in check, and so on.

If you don't know much about how to play the game (I've written AIs for games I didn't know how to play more than once!) then you can simply tune your AI against humans or other AI players until it does well. I wrote a program specifically to play against the Microscope Puzzle in 7th Guest (it's a variation of Ataxx). I had to write it because my roommate and I couldn't beat the game! It was pretty clear that some function of board coverage was the right function, and I experimented with bonuses for connected groups and so on until my AI could beat the game's AI. I still can't beat Ataxx myself and my own AI is even more ruthless and slaughters me quickly.

Minimax Evaluation Function

1 Answers1