Developing an alpha-beta search for “Colorito”, which has the characteristic that sometimes simple hill-climbing is impossible; so a sequence of 2 or 3 moves is the only way to make progress.

I came up with an endgame position where, with a 6 ply search, it’s possible to make
good progress in 2 moves but the third move must be the “bad” move of a new sequence. It’s also possible to make the same 2-move sequence take 3 moves, avoiding the “bad” move on
the horizon. This 3-moves which could be 2-moves becomes the principle variation.

The problem is that this same analysis applies to the next move, too; so the AI becomes
stuck, making no progress.

The search framework serves a lot of different games, so I’m most interested in generic approaches to detecting/avoiding this problem, but also game-specific ideas that might
avoid this particular problem.

Edit: After some thought, a reasonable and somewhat general approach is to allow “pass” moves at the terminal level of the search, even if the game does not. These artificial passes can be valued at zero, or slightly positive, so instead of finding a “bad” move at the search depth limit, the search will find a pass.