The enormous branching factor that results from compound moves is a serious obstacle to the success of minimax in certain games, as I mentioned in my first response. So MCTS seems promising. You can consider each separate piece moving as a proper move, since MCTS doesn't require turns to alternate, the way minimax does. If the nature of the game is such that random moves will progress towards the end of the game, you might be able to set something up without too much effort. If not, you either need to implement a biased playout policy that will make progress towards the end of the game, or you may have to combine an evaluation function with MCTS, so after a few moves from each side you'll use the evaluation function as reward.

Please, let us know if you are making any progress. Also, it would be cool if you could post a full description of the rules.

Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.

Yeah, that was my thought too, and it might work, but there are some situations that confuse me. E.g.,

XXXX XXXX XXXX XXXX
XX X XX X XX X XX1X
X 2X -> X2 X -> X21X -> X2 X
XX1X XX1X XX X XX X
XXXX XXXX XXXX XXXX


(1, 2, and X denote pieces; spaces denote empty space; this is a three-move sequence where the order of 1 and 2's moves matter.)

[Aside: The code tags do weird things, adding and removing spaces; getting ASCII art to look right is a pain...]

I'm not saying that there isn't an efficient way to resolve this so that you keep the attractive properties of just considering what squares are reachable (in which case you just get something like 3k moves), but how to do it doesn't jump out at me.

[quote name='Plusekwal' timestamp='1310884380' post='4836264']
Analysing the potential moves by even only one turn after the AI will take way too much computing time. It looks like I'll have to use MCTS

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.
[/quote]
Well, three moves per turn can have many possiblities and as far as I understood from that website, minimax needs at least three to four turns to compute. Also, there's some pretty complicated math involved when creating new pieces.

[quote name='Plusekwal' timestamp='1310884380' post='4836264']
I was asking if minimax can use only the results from one turn ahead.

Oh, ok, gotcha.

From the sound of what little you have told us about your game, your state space can't possibly be THAT big. Either that or your are running the game on a platform with the computing power of an abacus.

I'm not sure about that. The board is small, but each turn is 3 moves long. Naively, he'd have to search 6 plys just to see a full turn ahead -- not so much "min-max" as "min-min-min-max-max-max." Naively, this gives a min-max branching factor of (4*10)^3 , which is huge.* So it's not trivial.

That said, many of these turn sequences result, after 3 moves, in identical gamestates, so I don't think the "true" branching factor needs to be so high. It could be kept down e.g. by hashing visited states, or perhaps by thinking carefully about what states are reachable.

*(I'm assuming 10 pieces, each of which can move in one of 4 directions.)
[/quote]
I was actually considering maximum three moves per piece to be considered - one for eliminating maximum number of enemy pieces, one for colouring(see below) and one for escaping/defending own pieces.

The enormous branching factor that results from compound moves is a serious obstacle to the success of minimax in certain games, as I mentioned in my first response. So MCTS seems promising. You can consider each separate piece moving as a proper move, since MCTS doesn't require turns to alternate, the way minimax does. If the nature of the game is such that random moves will progress towards the end of the game, you might be able to set something up without too much effort. If not, you either need to implement a biased playout policy that will make progress towards the end of the game, or you may have to combine an evaluation function with MCTS, so after a few moves from each side you'll use the evaluation function as reward.

Please, let us know if you are making any progress. Also, it would be cool if you could post a full description of the rules.

I'm still wondering if switching to MTCS will be worth it. I dont know if MCTS will be applieble to this game. Also, computing time might not be that big after all. As for the rules:
-the board is 9x6 squares big
-the game ends when there are pieces of only one player left
-every player starts with one piece only
-one piece can do five actions - moving in the four directions and colouring the square which it is currently on in the colour of the player
-upon colouring if the new coloured square makes a row, a column or a diagonal of three colourd squares in the colour of the player, new pieces are spawned at the empty places

[quote name='ApochPiQ' timestamp='1310950886' post='4836567']
Per piece, you compute a list of potentially reachable spaces on the board (do I move this guy 1, 2, or 3 times?). Then you prune conflicts (i.e. two pieces land on the same square). Then you prune the number of valid combinations using a simple allowance metric (i.e. only 3 moves are allowed per turn). This gives you a finite, bounded set of moves which is not substantially larger than the set of potential moves in an average chess game, if my napkin mathematics does not betray me.

Yeah, that was my thought too, and it might work, but there are some situations that confuse me. E.g.,

XXXX XXXX XXXX XXXX
XX X XX X XX X XX1X
X 2X -> X2 X -> X21X -> X2 X
XX1X XX1X XX X XX X
XXXX XXXX XXXX XXXX


(1, 2, and X denote pieces; spaces denote empty space; this is a three-move sequence where the order of 1 and 2's moves matter.)

[Aside: The code tags do weird things, adding and removing spaces; getting ASCII art to look right is a pain...]

I'm not saying that there isn't an efficient way to resolve this so that you keep the attractive properties of just considering what squares are reachable (in which case you just get something like 3k moves), but how to do it doesn't jump out at me.
[/quote]As for this situation, piece 2 can move upwards an piece 1 upwards and then leftwards - there is no difference. Besides, due to the nature of the game the board will never get that crowded.

How do you lose pieces? Also, after a new piece is spawned, the coloring of the squares involved goes away?

How do you lose pieces? Also, after a new piece is spawned, the coloring of the squares involved goes away?

You just move onto enemy pieces to destroy them. And the colour doesnt go away, so this is a kind of limit for the number of possible pieces. However, the enemy player can always change the squares in your colour into his colour.