Hi this semester we have a project were we have to create a java p2p multiplayer implementation of the Malefiz game, (the english version is called barricade or obstruction; rules are here) well our actual implementation is coming along nicely, but we''ve been told that after christmas they want all teams to implement a computer-player and then let all those play against each other in a tournament, so i''m in the process of thinking up a good idea of how to create an AI for this game, which seems harder then i thought at first. The problem is i don''t even know where to start looking. Everything i know AI-related (given, that is not very much ) is not applicable for this type of game. My two main problems: - there is a dice. so it is impossible to use any techniques that compute possible future moves (at least for more then a very few rounds into the future since the number of possible moves each round can reach a few hundred..) - i have no idea how to even weight a move (or just how to decide if it''s good or not). this is because you can''t kick enemy figures out of the game, they just get thrown back to the start position, so it might not be very useful to kick them most times; then there are the barricades which you can set freely when you jumped on one with your own figure..but whereever you set them, it can be that later they''ll be in your own way. etc. so if i have the list of possible moves i have no real way to tell which one is better then another. as it is now (just a quick hack) we just give the fields a higher value the nearer they are to the finish field and have the AI take the move that gets to the highest-valued field, but this doesn''t exactly make an intelligent AI NNs would be nice to use of course, but our time-constraints, the fact that we use java, and that we may not use external libraries and none of us has any experience with NNs makes them look bad too... well, the AI doesn''t need to beat a human player, but i''d like to see it beat some other AI players at least, so i''d be happy if anyone has ideas of how to tackle such a problem, or knows of any resources with AI for similar, roll-and-move games

When _you_ play the game how do _you_ decide what move to make? Break it down and start making some rules on paper. Transfer these rules to state tables and use them in-game.

There is a way to use a game tree for these types of game, although I have never done it myself. These are called Games of Imperfect Knowledge and you''ll find something along these lines if you search google. There was a thread here awhile back on card games where I posted a link to a paper on this topic-- I just don''t remember what it is anymore.

Assuming you go with state tables, you could use a genetic algorithm to optimize or create new ones for you-- test them against the state tables you already have, and against different permutations of the GA generated state tables. You''re almost gauranteed some minor benfits by doing this, but don''t hold me to that.

Best of luck,
Will