Have Geek Brain

Mahjong-solitaire algorithm algorithm that needs to be accelerated

I am developing a mahjong solitaire solver and so far, I am doing very well. However, it's not as fast as I would like, so I'm asking for additional optimization techniques that you guys might be aware of.

All tiles are known from layouts, but there is no solution. At the moment, I have few rules that guarantee the safe removal of certain pairs of identical slabs (which cannot be an obstacle to a possible solution).

For clarity, a tile is free when it can be selected at any time, and a tile is free when it does not link any other tiles at all.

  • If there are four free free tiles available, remove them immediately.
  • If there are three tiles to pick up and at least one of them is a loose tile, remove the loose ones.
  • If there are three tiles to pick up and only one free tile (two losses), remove the free tile and one random loose tile.
  • If there are three free tiles, remove two of them (it doesn't matter which one).
  • Since there are four times the same tile, if two of them are left, remove them as they are only left.

My algorithm solves the search for a solution in multiple threads. Once the branch is finished (to a position where there are no more movements) and that doesn't lead to a solution, it puts the position in the vector containing the bad ones. Now, whenever a new branch starts, it will iterate through bad positions to check if that particular position has already been checked out.
This process continues until a solution is found or all possible positions are checked.

This works well on a layout that contains, say, 36 or 72 tiles. But when there is more, this algorithm becomes almost useless due to the huge number of positions to search.

So, I ask you again if any of you have any good ideas on how to implement more rules for safely deleting fragments or any other speedup regarding the algorithm.

Best wishes nhaa123

+1


a source to share


4 answers


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

If you choose arbitrary, that's not good enough - it's just a rough search, basically. You may need to study the "best industries" first. To determine which branches are "best", you need a heuristic function that evaluates the position. Then you can use one of the popular heuristic search algorithms. Check them out:



  • A * search
  • Ray search

(Google is your friend)

+2


a source


Several years ago I wrote a program that solves the Solitaire Mahjongg boards by peeping. I used it to research a million turtles (took a day or something like a computer: it had two cores) and it turned out that about 2.96% of them could not be solved.

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



Ok, this is not what you asked for, but you can take a look at the code to find a sketch heuristic in it that hasn't passed to you so far. The program does not use more than a few megabytes of memory.

+2


a source


Instead of a vector containing "bad" positions, use a set that has a constant search time instead of a linear one.

0


a source


When doing optimizations, be sure to ask yourself if your threads are running in HW threads and can they run independently, otherwise they might slow down rather than speed up.

Also mentioned is raindog-2. Order your search paths. You have rules, so give directions according to those rules. Go for maximum loose tile and then for maximum loose tile. So try every step you can take in a situation, order them and proceed with the most optimal situation.

0


a source






More articles:


All Articles