1

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

nhaa123
  • 9,570
  • 11
  • 42
  • 63

4 Answers4

2

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.

Michiel
  • 21
  • 1
  • Hi! Welcome to stack overflow. I think this is a fairly good answer/comment. The only thing I'd mention is that you should also include some relevant text/code from links in case the link dies. – Parris Dec 09 '12 at 22:12
2

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)

Igor Krivokon
  • 10,145
  • 1
  • 37
  • 41
  • Yes, this is pretty much brute force, what I'm doing here. ATM, I don't have nothing to evaluate current position. I'll check your advices from Google. Thanks. – nhaa123 May 27 '09 at 08:02
0

If 4 Tiles are visible but can not be picked up, the other Tiles around have to be removed first. The Path should use your Rules to remove a minimum of Tiles, towards these Tiles, to open them up.

If Tiles are hidden by other Tiles, the Problem has no full Information to find a Path and a Probability of remaining Tiles needs to be calculated.

Very nice Problem!

Zykrates
  • 61
  • 4
0

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

Georg Schölly
  • 124,188
  • 49
  • 220
  • 267