Developing a heuristic: Constraint Programming for Puyo

Last off, I was talking about the brute-force MCTS methodology was coming up with nice 7-chains at a reasonable pace. However, expert human Puyo players can build 15+ chains in actual combat, so while the MCTS was successful in some sense, it is clearly too weak to challenge human players still, by an order of magnitude. As such, I set off looking for a heuristic to improve MCTS.

I eventually came across constraint programming, the AI-methodology for representing problems in terms of a series of variables, domains, and constraints. A constraint solver tries to assign variables values that satisfy constraints.

For example, Sudoku can be described as 81 variables, each with domain 1-9, with the 27 constraints of:

* All different(X11, X12, X13, X14 ... X19)

* All different(X21, X22, X23 ...)

* ... repeat the above for all rows

* All different(X11, X21, X31, ... X91)

* All different(X12, X22, X32...)

* ... repeat the above for all columns

* All different (X11, X12, X13, X21, X22, X23... X33)

* ... repeat the above for all squares.

Anyway, solving Sudoku in this way is very "human" and "intuitive". Once the problem is stated in this manner, its a simple process of elimination between all variables to figure out what the values each variable should have, or if a solution even exists.

So how to represent this in terms of PuyoPuyo?

Well, applying constraints to PuyoPuyo is pretty easy. A constraint of "Doesn't_Pop" between variables would describe 4 variables with at least one value being different (or be an empty space). The domain of any particular variable would be the 4-colors or an empty spot (a total of domain-size 5). It would seem natural to describe chains in a form of "These variables don't pop" and "These variables MUST pop".

The hard part then, is not finding a solution. But estimating the NUMBER of solutions. After all, PuyoPuyo isn't about just building a chain, its about building a chain given the pieces from the random-number generator. As such, a good "base" is not just a base which has potential to become a 15, 16, or 18-chain... but also one which  has a large potential and flexibility to become a 15+ chain.

In addition, the potential to create hellfires (power-2 chains), or counter-formations, can be represented as constraints as well.

Funny story: Constraint Programming, as powerful as it is, is an NP complete problem. Finding a solution will likely take longer than polynomial time, and finding all exact solutions will take exponentially more time. The only hope is to estimate the number of solutions in some way.

But that's fine! All I'm looking for is a powerful chain-building heuristic. I'll write up a few more posts later that better describe how this Constraint Programming framework will work in my Puyo AI.