Mahjong-solitaire solver algorithm, which needs a speed-up

Question

Dears,

I'm developing a Mahjong-solitaire solver and so far, I'm doing pretty good. However, it is not so fast as I would like it to be so I'm asking for any additional optimization techniques you guys might know of.

All the tiles are known from the layouts, but the solution isn't. At the moment, I have few rules which guarantee safe removal of certain pairs of same tiles (which cannot be an obstacle to possible solution).

For clarity, a tile is free when it can be picked any time and tile is loose, when it doesn't bound any other tiles at all.

• If there's four free free tiles available, remove them immediately.
• If there's three tiles that can be picked up and at least one of them is a loose tile, remove the non-loose ones.
• If there's three tiles that can be picked up and only one free tile (two looses), remove the free and one random loose.
• If there's three loose tiles available, remove two of them (doesn't matter which ones).
• Since there is four times the exact same tile, if two of them are left, remove them since they're the only ones left.

My algorithm searches solution in multiple threads recursively. Once a branch is finished (to a position where there is no more moves) and it didn't lead to a solution, it puts the position in a vector containing bad ones. Now, every time a new branch is launched it'll iterate via the bad positions to check, if that particular position has been already checked.
This process continues until solution is found or all possible positions are being checked.

This works nicely on a layout which contains, say, 36 or 72 tiles. But when there's more, this algorithm becomes pretty much useless due to huge amount of positions to search from.

So, I ask you once more, if any of you have good ideas how to implement more rules for safe tile-removal or any other particular speed-up regarding the algorithm.

Very best regards, nhaa123

Answer 1

I don't completely understand how your solver works. When you have a choice of moves, how do you decide which possibility to explore first?

If you pick an arbitrary one, it's not good enough - it's just brute search, basically. You might need to explore the "better branches" first. To determine which branches are "better", you need a heuristic function that evaluates a position. Then, you can use one of popular heuristic search algorithms. Check these:

• A* search
• beam search

(Google is your friend)

Answer 2

Instead of a vector containing the "bad" positions, use a set which has a constant lookup time instead of a linear one.

Answer 3

When doing optimisations, definitively ask yourself if your threads are running on HW-threads and whether they can run independently, otherwise they can slow down instead of speeding up.

Also as mentionned by raindog-2. Order your search-paths. You have rules, so give points according to these rules. Go for maximum loose tiles and then for maximum free tiles. So try each step that you can do in a situation, order them and continue with the most optimal situation.

Answer 4

Some years ago, I wrote a program that solves Solitaire Mahjongg boards by peeking. I used it to examine one million turtles (took a day or something on half a computer: it had two cores) and it appeared that about 2.96 percent of them cannot be solved.

http://www.math.ru.nl/~debondt/mjsolver.html

Ok, that was not what you asked, but you might have a look at the code to find some pruning heuristics in it that did not cross your mind thus far. The program does not use more than a few megabytes of memory.