# Programming a good puzzle game (Puyo Puyo) AI

I’m trying to build a strong AI for a game called Puyo Puyo, in Matlab (I know… but it’s the only language I know well).

Basically it’s like Tetris but you get falling pairs of 2 puyos (blobs) of different (or same) color, among 4 possible colors. You can move them around and place them however you like. Fill the screen (more precisely the upmost case on the 3rd column) and you’re dead. Put 4 puyos of the same color that connect vertically or horizontally (no diagonals, 4-connectivity) and they will pop, disappearing of the screen. The puyos above the popping ones fall downward until it reaches another puyo or the ground. You get to work with your current falling pair as well as the two next pairs as info.

The aim of the game is to produce a large chain by stacking puyos so that breaking one group will also trigger other groups afterwards. Good human players reach 19-chain in endless training which is the maximum possible on the 13×6 board, but the max chain is typically around 12-13 in human matches. I’m limiting my AI to a 12×6 board (the 13th row has special properties I don’t want to deal with now), and aim at my AI building 13-chains or more which is suitable for battle against strong human players.

So I’ve been trying different things like heuristics but I feel like depth-3 search (we got 3 pairs we know of) should give good results, as it uses all info available to the player. However I’m coding in Matlab and there are 5 for loops imbricated into each other (one for the number of games I make the AI play, one for each move I allow the AI, and three for the depth-3 search). So the code runs sloooow… and in the future I’d like to combine depth-3 search with other heuristic parameters and optimize the whole thing with a genetic algorithm.

Anybody got advice on things I could speed up, possibly vectorize some operations? Would coding in another language speed up the for loops? by a factor of how much?