Hello! I''ve sort of been working on a clone of the Playstation game Devil Dice. If you''re not familiar with the game (like most people ) its sort of a puzzle game payed in real time, solo or competitively with others. You play on a gameboard full of dice, and you roll or slide the dice around to match up them up. You can download a rough version at http://my.execpc.com/~zor/SneakyAmp/projects.htm . I''ve been thinking about a way to implement AI, and I wanted to get some opinions. So far I''ve tried a half implemented exhustive search of moves, up to a depth of between 2 and 8 moves. At low depths, it was just terrible, and at higher depths it was slow *and* terrible. All it used to evaluate moves was the number of matches the move would create, it would pick the move that potentially yielded the most matches. Theres a bit more to the game than just that, but I was hoping it''d at least how signs of intelligent play. It did sometimes, but usually it was hard to tell if it was just picking moves at random. So, I''ve been thinking about other ways to do it. I''ve thought about seeing if I could train an ANN to play, put I''m not sure how I''d design one. I could use the gameboard and player position as input vectors, but thats a lot of information. The gameboard is a minimum of 7x7, with each square having several possible states. More then just "This position has a 4 on the top of the die!". Being a real-time game, I wouldnt want a super huge ANN to slow things down , so I''m not sure about this. And I''m not sure about the output vector either, whether a game board evaluation ANN with 1 output value, to use in a search, would be better. Or, to use a ANN that outputs which move would be prefered (out of left, right, up, and down). I''ve also thought about creating some completely hand written evaluation function, that would maybe return a prefered position, and the steps needed to get there. This way I could run the AI routine once every few moves, making multiplayer less CPU intensive. But that sort of evaluation function would be a bear, and I wouldnt know how to even start. As simple as the game is, its awfully complex. So, any ideas?

Yeah, I''ve done a tiny bit of min/max stuff in the past, but I''m not sure it''d work well for this game. The more than 2 players thing is one problem. Also, while the game is sort of competetive, I dont think there would be anything to gain if the AI tried to take into account other players actions - which if I remember correctly, is what minimax is good for.

I think I''m going to try something complicated, but I''m still working it out... Heres the plan so far:
1) Every gameboard update, give each occupied space a score. For example, maybe a lone ''2'' would have a score of 2, while a clump of 5 ''6''s would each have a score of 500.
2) If the player is on a moveable peice, search through the die''s possible movements (should be much less search space than a general movement search, which is depth^4). Otherwise, move, um, somehere else...
3) At each search position, check if there is an adjacent die, and what its score is
4) Return path to ''best'' scoring position

This will get the AI to set up clumps of matches on its own, as well as complete matches. It may favor the highest scoring moves a little too much if the depth is too high, but that can be fiddled with later. Usually quick matches are better than high scoring matches (at least in my own strategy,

Then I''d just have to work on special cases. Like, being on top of dice is better than being on the floor, they''d want to find a way up. Setting up matches while on the floor might take a little work too. Things like that.

Yeah, the biggest draw for me was playing against other players. As far as I know, the only way to play it on the PC is using a PSX emulator, or use my crummy version.

As far as ANN inputs goes...

Currently, the die position itself is represented by one number: its ''mode''. There are 24 modes, because the die can be oriented 24 ways. The top value is mode/4+1. Then then we''d have a minimum of 49 inputs for the mode.

But, then there is the position''s state. There might be a die sitting there, or it might be empty. It may have a die sinking down or rising up from the floor. It may be involved with a moving die: it''s not occupied but will be soon, or occupied but will be free soon. Some of this could be simplified for AI''s sake, but not much.

Also, there''s a timer used for some states, so you can tell where a die is for sinkers/risers, and so you can tell how long a die will be in that state. The AI would need this information mostly for risers/sinkers. Will it be able to run to the riser in time to climb up onto it (cant get up if the riser is too high)? Will I be able to capture the sinker before its gone?

So put that all together, and you have 147 inputs.

But wait! Do we want the AI to have to learn the transition function? That is, if I''m on a die of mode 4 and roll it left, what mode is it now? We''d better add 4 more inputs, the mode of the rolled die for each direction. Although, it wont be able to roll the die all the time, hopefully it could figure that out.

151 inputs.

Oog. Player info! Where am I on the board? Thats 2 more inputs. Well, we could get around this by having the center always be my position, and shift the board in the ANN inputs accordingly. But then we''d have to be able to signal invalid board positions as well, and we woldnt be able to see the whole board at once. But that might not be a bad thing.

So, 153 inputs. Who knows how many hidden nodes I''d need, but I''d guess a LOT. I could decrease the size by limiting how much of the board the AI can see, but theres still no guarantee it would actually work.