Can someone give me some pointers on how I should implement the artificial intelligence (human vs. computer gameplay) for a Puyo Puyo game? Is this project even worth pursuing?
The point of the game is to form chains of 4 or more beans of the same color that trigger other chains. The longer your chain is, the more points you get. My description isn't that great so here's a simple video of a game in progress: http://www.youtube.com/watch?v=K1JQQbDKTd8&feature=related
Thanks!
The first answer that comes to mind is a lookahead search with alpha-beta pruning. Is it worth doing? Perhaps as a learning exercise.
You could also design a fairly simple expert system for a low-level difficulty. Something like:
1) Place the pieces anywhere that would result in clearing blocks
2) Otherwise, place the pieces adjacent to same-color pieces.
3) Otherwise, place the pieces anywhere.
This is the basic strategy a person would employ just after becoming familiar with the game. It will be passable as a computer opponent, but it's unlikely to beat anybody who has played more than 20 minutes. You also won't learn much by implementing it.
Best strategy is not to kill every single chain as soon as possible, but assemble in a way, that when you brake something on top everything collapse and you get lot of combos. So problem is in assembling whit this combo strategy. It is also important that there is probably better to make 4 combos whit 5 peaces that 5 combos whit 4 peaces (but i am not sure, check whit scoring)
You should build big structure that allows this super combo moves. When building this structure you have also problem, that you do not know, which peace you will you get (except for next peace), so there is little probability involved.
This is very interesting problem.
You can apply:
Dynamic programming to check the current score.
Monte Carlo for probability needs.
Little heuristics (heuristics always solve problem faster)
In general I would describe this problem as optimal positioning of peaces to maximise probability of win. There is no single strategy, because building bigger "heap" brings greater risk for loosing game.
One parameter of how good your heap is can be "entropy" - number of single/buried peaces, after making combo.