AI Algorithm

[ultddave]

Hey everybody.

At the moment I'm programming the board game "Settlers of Catan" in C++. We (me and a friend) were thinking about using a (min/max) 'game tree' for an AI player. (If that's the correct english term?) A tree that contains each possible board setup.

But our teachers said that using a game tree for a board game that relies on random variables (in this case: the 2 dices) is not recommended. Does anyone know a good AI algorithm that can be used for board games where players need to use dices each turn?

I've downloaded allot of e-books already. But as I'm still a student, I don't really have a clue which algorithm is better than others. (This is the first time I need to make an AI that needs to be a "strong" opponent).

(Link to the wikipage of the game: http://en.wikipedia.org/wiki/The_Settlers_of_Catan )

Thanks in advance.

Greetz,
Dave

[Zachm]

Refer to this persentation on game-playing, specifically slides 26 to 30.
You can incorporate probability into a min/max tree. The question is - do you know the probabilities of different events ?

Regards,
Zachm

[ultddave]

Thanks for the presentation!! It's very helpful.

As far as I know, Settlers of Catan only has 1 event that is "random". That's rolling the dice. The player rolls 2 dices. The values of both dices are added. And all the fields on the board with that number are "activated". Meaning that every player who has a city next to a field with that number, will get the resource corresponding to that field.

So I think I only need to calculate 11 probabilities. (Getting a '2' with 2 dices, a 3 with 2 dices, a 4 ..., etc etc) (= possible outcomes by adding 2 dice values).

(PS: If people know any other algorithms, feel free to let me know. So I can try multiple algorithms and see which one is better than the other. )

Greetz,
Dave