The vanilla MCTS algorithm has been replaced with a deterministic one. This new algorithm aims to explore all possible board states of the Fishing Jigsaw game, computing an optimal solution for each of them.
Strategy
Firstly, this algorithm computes an optimal solution for each state instead of only one as MCTS does. Nevertheless, the heavy computation is done only once. Afterward, a solution for a specific state of the game is returned instantly.
Secondly, since all possible game states are explored, its solutions are more reliable than those generated by MCTS.
Performance
This algorithm has been implemented using some techniques for maximizing CPU pipeline, avoiding excessive branching. Additionally, I've done a parallel version of it to reduce execution time. However, it adds some complexity to the code, so I'm working on improving its readability in order to push these changes.
The time the algorithm takes to compute all solutions is not bad (17s in my computer), but it could be improved. I believe this execution time is acceptable, considering the increased reliability of the solutions.
GUI
Since I change most of the code, I also had to rewrite the GUI. Now I find it prettier and more user-friendly :-).
Deterministic Algorithm
The vanilla MCTS algorithm has been replaced with a deterministic one. This new algorithm aims to explore all possible board states of the Fishing Jigsaw game, computing an optimal solution for each of them.
Strategy
Firstly, this algorithm computes an optimal solution for each state instead of only one as MCTS does. Nevertheless, the heavy computation is done only once. Afterward, a solution for a specific state of the game is returned instantly.
Secondly, since all possible game states are explored, its solutions are more reliable than those generated by MCTS.
Performance
This algorithm has been implemented using some techniques for maximizing CPU pipeline, avoiding excessive branching. Additionally, I've done a parallel version of it to reduce execution time. However, it adds some complexity to the code, so I'm working on improving its readability in order to push these changes.
The time the algorithm takes to compute all solutions is not bad (17s in my computer), but it could be improved. I believe this execution time is acceptable, considering the increased reliability of the solutions.
GUI
Since I change most of the code, I also had to rewrite the GUI. Now I find it prettier and more user-friendly :-).