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

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

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)

Leave a Reply

Your email address will not be published. Required fields are marked *