Game Mechanics Match 3 AI questions

Hi guys,
I'm a puzzle match 3 that swap pieces similar to Puzzle League. One problem that I'm have is how to approach to CPU AI.
The game has a grid 7x11. At first I thought in do in "brute way". Like do a simulation test one of 66 possible moves, and in each outcome test another 66 moves, and repeat until I have 3 moves in advance. An find the best move , based a value (blocks removed, number of combos and chains). But the number of possibilities can be at max 66x66x66 = 287497 grids created, taht could extensive to a CPU.

I tried study chess and Tetris AI, that has some interested concepts of MiniMax (that look closer of what I did), genetic functions. But I think that arcarde games from Neo Geo and others (that has lower CPU power), it should have a best approach, but still uknown to me.

The AI that I'm seeking is to give a variable challenge to player, that somehow I could plan some sequence of chains.
 

FrostyCat

Redemption Seeker
If you do it only one at a time and reuse the grids after getting their heuristic value, at most there will only be 4 grids at any given time (root state plus 3 progressions). You will still calculate every permutation this way, but the total memory usage will not be the 287497 total grids you got.

In addition to Minimax, you should also look into MCTS. It does not have to evaluate all the permutations to play well, can tune its playing strength on a sliding scale, and can work from as little as the rules alone. I have had excellent results with it on 3 separate released projects (first 2 open-sourced in GMS 1.4):
You can look in the scripts of the open-sourced projects for how I implemented the functionality, particularly mcts_tree_evaluate and the ones starting with the name of the said game.

Around July, I will be releasing an expanded version of the engine used in the example, that also contains Minimax plus other configurations and utilities. You may want to keep an eye on my status for when that goes live.
 
Hi, thanks for all the info, it was some weeks that I was studying the material that you provided some far, and using as guide of where I need search more.
 
Top