# Creating A Board Game AI

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).

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: http://stackoverflow.com/questions/4419628/creating-a-board-game-ai

-
You can use many AI algorithms, so "which one" is a design (or possibly engineering) tradeoff. Do you want a "perfect" AI that can "solve" the game (i.e. play optimally)? Or do you want a "game" AI that plays good enough to not embarrass itself, but weak enough that it is beatable (especially if you want several difficulty levels)? Or do you just want a bare-bones "dumb" AI that plays without logic so you can test the game? Lots of choices, none inherently right or wrong. –  Ian Schreiber Dec 13 '10 at 16:40
I would think you'd need an algorithm developed specifically for this problem, although you may be able to use various techniques/algorithms within it. You might get a good answer on ai.stackexchange.com –  Matthew Read Dec 13 '10 at 23:14
@Ian, i want that AI can play game itself acceptable. May be later i can add difficulty levels. So i need a start point. @Matthew i will add my question to there. Thank you all. –  bahadir arslan Dec 14 '10 at 17:33
Ouch! Seems like ai.stackexchange.com was closed, although that would have been the perfect place to ask... sad. –  bummzack Dec 22 '10 at 7:16
Minimax is not restricted to two players. It can be easily generalized to `n` players, by storing a vector of payoffs, so I think it could be a good algorithm here, coupled with an ad-hoc heuristic specially designed for the game. –  Alejandro Piad Nov 11 '12 at 3:13

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.

-
Here is an article about creating AI for Gin Rummy. It might prove some useful insights. aifactory.co.uk/newsletter/2007_02_imperfect_info.htm –  Tim Holt Dec 14 '10 at 14:38
I will look this as soon as possible. Thank you @Tim Holt and @skerslake –  bahadir arslan Dec 14 '10 at 17:34
I would also look around for MahJongg strategies. It's not quite as closely related but it's still close. –  Loren Pechtel Dec 23 '10 at 18:26

The well known multiplayer versions of minmax are MaxN and Paranoid Search

-
Great search terms, can you elaborate any more about these? Do you have experience with them? (edit your answer with the "edit" link just under it) –  Ricket Mar 30 '11 at 12:49