Hi all, I have a challenge that is puzzling me. Maybe it's not that hard, but I'm new to AI programming, so... I have to develop an AI for a game of my own, a turn-based puzzle game. It's something chess-like, as it needs a CPU opponent to think ahead of what the player will be doing the next turn to be effective. The challenge is that the game board is divided into areas that rotate, so the AI has to make a hard guess for the gaming world can change after every move. The game is a multiplayer 1 vs 1 now, and I need help to make the AI for the single-player. WHAT I NEED IS NOT PROGRAMMING. I will do that. I need some AI expert which wants to step up and help me in solving this challenge with the theory and the basis for this AI. I won't pay him because I can't now, although the game has great plans and anyone involved will be rewarded in some way. The game is currently made in Flash but we want to port it to the iPhone or DS (hopefully). Credit is of course guaranteed, I will make clear who made the AI anywhere on the site and the product if it ships for the intended platform. Enough talk now! If you want, the game is online and you can try it on http://www.ufho.it It's one vs one but it's also turn-based, so you can open two windows and play in both as guest (user: guest and password: guest). In the site there's a guide that explains the game. It's located at http://www.ufho.it/guida2_en.php?lang=en#3 If you want to help, I'd simply like some hint like an algorithm adapted for this game. I will take care of the programming afterwards, I only need theoric implementation. Thanks in advance to anyone who accepts this challenge! And feel free to ask me for anything! Ciro Continisio UFHO

First of all, let me say this looks very nicely polished!

I'd only suggest to change the site's layout to make it more clear you need to log in to play. In my impatient visit, I had to watch the YouTube video to find that out [smile] Also, your webserver seems a bit busy, which can cause the 'enter image' on the frontpage to fail to load, which in turn might put off visitors. For anyone else reading this, reload the page and enter, it's worth a look!

Anyway, I think the very basic step would be to have the AI find paths to the nearest gems each turn using a conventional algortithm like A* with the rooms as nodes. If any paths are available, the optimal path might be the shortest path, but it might also be worth using a heuristic to check which gems are close to the player and avoid these to avoid conflict. Likewise, this heuristic (or complete player -> gems paths found using A*) might also be used to change the board to actively hinder the player.

This obviously leaves out the rotations to form paths and that's where things get tricky. You could determine all possible future states of the board over a number of turns and examine the paths in all these states. The obvious problem however is that the number of possible states after N turns is ( (7 areas + 49 rooms ) * 4 possible rotations1 ) ^ N. So to even look ahead to your next turn, you'd have to examine the paths on 50176 possible board layouts, which would quickly become infeasible. Please correct me if I'm way off on my math though.

A rough idea on handling the rotations might be to add a subgoal for the AI to get onto areas where a gem is located (again using A*). If it can get there in < 6 moves, it obviously should simply move there. This way it can be certain the player won't interfere by rotating areas in its path. Likewise, it might be a good heuristic to have the AI plan its path over the areas (so considering the areas as nodes for A*, using some added mean cost for rotating rooms to make the area traversable). Then once it gets into an area containing a gem, you can move back to the simpler task of getting to its room. This should boil down to examining some possible room rotations within the area, with an early-out when you find *any* path to the gem.

Once the AI has a subgoal to move from one area to another, you can consider the small number of rotations related to the area it's currently in and the area it wants to move to. When only considering these two, the brute force approach should be feasible and it should be fairly simple to determine whether something can be gained by rotating any one of the two areas or border rooms. Intuitively, I'd say it should be possible to move from any area to the next each turn, so this should be the goal for the AI.

I just realized an additional factor might be to move between rotations, since this obviously would make subsequent rotations more or less useful. Pondering this a bit, I think it should be possible with the brute force approach to construct equivalent paths at similar costs without taking this into account, so I don't think this is something to worry about much.

Using this general approach the AI should be able to find its way regardless of player intervention and without wasting a lot of moves on contructing a path the player may ruin. It should handle most negative powerups fairly well too, since the area subgoals make 'Blocked rooms' or 'Rotate rooms' less of a problem. I don't think the AI should concern itself with getting powerups too much, but there are probably some basic rules of thumb to make it put them to good use.

To summarize:

1. Determine the shortest path over the areas to an area with a gem
   
   
   
   • Don't worry about the rooms configuration when planning the path
     
   • Use a subgoal of getting from one area to the next each turn
     
   • Consider rotations when moving from one area to the next (brute force)
     
   
   
2. When on an area with a gem
   
   
   
   • Determine if there's a path to the gem; get it if possible
     
   • If not, consider various room rotations (brute force) to find a path
     
   
   

I do hope this helps [grin]


1. Those 4 rotations would be 0, 60, 120 or 180 degrees


[Edited by - remigius on July 15, 2008 2:48:33 AM]