Creating A Board Game AI

Question

I want to code a board game that name is Okey and mostly popular in Turkey. http://en.wikipedia.org/wiki/Okey

But i have got some problems about AI.

Firslty let me explain the game..

The game is played by 4 players.

In this game there are 106 tiles, 2 of them are fake joker. Other 104 tiles are divided 4 colours generally green, black, blue and red. All colours have two sets of tiles. A set ise contains 13 tiles that numbered sequentially 1 to 13.

Each player start 14 tiles (one is start 15 and starts first) and throws one of the most unwanted tile the next player. Next player can get this tile or can get another tile from stack in the middle of table. The game played in anti-clockwise..

The aim of this game is find the valid sequence of 14 tiles as soon as possible. Player can align tiles by sequential numbers in the same colour until 13. For examle Green 1, Green 2, Green 3. There is an exception here, 1 can be follow to 13. For example Red 12, Red 13 and Red 1 is a valid set. But Red 13, Red 1 and Red 2 is not valid.

Or player can align tiles by colors in the same number. For examle Green 1, Black 1, Red 1, Blue 1.

Each set need to be 3 or more tiles to be valid and each of this set named as "Per". Less then 3 tiles is not valid for the finish. A valid finish set can be like this. G: Green, B:Blue, R:Red, BL: Black G1|G2|G3 B2|R2|BL2 R9|R10|R11|R12 BL13|R13|G13

Last thing, when starting game a tile selected to determine joker (okey). For example if you select Blue 3; Blue 4 will be joker (okey) and player can use this tile instead of any tile that player needs to win or complete a set (per).

Of course these rules are general rules and summarized to explain question. If you can read English you can check this link for more information http://tr.wikipedia.org/wiki/Okey or translated page by Google Translate http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&sl=tr&tl=en&u=http://tr.wikipedia.org/wiki/Okey

So which AI algorithm that i can used? I searched for minimax theory and alpha beta pruning. But these theories are generally about 2 players game like chess or tic-tac-toe.

Original Question is at stackoverflow: https://stackoverflow.com/questions/4419628/creating-a-board-game-ai

Answer 1

If you swap tiles for cards the description of the game sounds incredibly similar to the card game Gin Rummy. You may be able to find some direct AI resources by searching against that.

One option for AI that is agnostic to the number of players and can be used to create different AI personalities:

1. Play the board game, ideally with some friends, although you can play all the hands yourself, but with a computer handy and Excel open.
2. Talk out load what your thought process is. There will be a number of discrete points that you consider when making a decision. Things like "does the unwanted tile give me a playable set", or "get me a step close to a set", or "add to an existing playable set".
3. Then once you have the list of all the items you consider when making a decision of what tile to pick up and what tile to discard start to create number weights for them based on what is most important to you.
   1. Example: It might be three times as important for you to get the 3rd tile in a sequence as it is to get the 4th tile in an existing sequence.
4. Once you have all these weights for all the things you look at when making a decision you can use Excel to calculate a score for each action. So you have a worksheet where each row represents an action choice and each column represents a deciding factor. If that factor is true for that action you multiply it times the weight, if that factor is false you score it zero. Then you add up all the scores and the one with the highest value is what the AI will choose to do.
5. Play the game with Excel open. Each turn see if the score outcome matches the outcome you would choose. If it doesn't adjust the weights based on your thinking until it does. After several games the AI should play the game the same way you do. If you've been playing consistently with a group of friends who all have different weights then you'll have AI's with various personalities.

You can then control difficulty by not always selecting the highest rated option. Since the lower the score the worse the decision.