pazusoba / core Goto Github PK

Try to solve Puzzle & Dragons with C++

License: MIT License

C++ 79.76% Python 16.49% C 0.34% CMake 3.40%

cpp python beam-search opencv pyautogui puzzle-and-dragons automation

core's Introduction

🍜 パズそば・スーパー

Puzzle & Dragons is a mobile game developed by GungHo Online Entertainment,Inc. In this game, there is a board and you can erase orbs to make combos and damage dungeon monsters. Every combo will increase your attack by 25%. Also, there are skyfall orbs that might potentially make more combos.

Some demo on YouTube mostly in Japanese.

Projects

pazusoba, the core algorithm
pazulove, machine learning
pazuauto, automation
pazuflata, pazusoba with Flutter
pazusoba-android, pazusoba and automation on Android

The goal

There are 30 * 3 ^ 25 possible states for a 6 x 5 board (with max steps of 25) so it is impossible to find the true optimal path. Therefore, the goal is to find a good path quickly. Ideally, it should be short, cascading and aiming for the max combo (except that it is never that ideal).

Show more information

My approach

A priority queue is used which limits the size to a fixed number and only states with a better score can be inserted to the queue. Thus, this is a very greedy approach and it is callled BEAM SEARCH. Overall, it has surpassed many pro players but it is not perfect. I will keep making it better over times.

Why beam search

Greedy DFS -> Greedy B(best)FS -> My special greedy BFS -> Beam Search

As you can see, they are all greedy algorithms based on a heuristic. The reason is that the end goal is unknown and there are also negative values. Simply choosing the local maxima may result in poor solutions.

Best first search improves the overall performance but it consumes too much memory and is extremely slow in computation. That's why I wanted to prune useless branches because a better path is guaranteed to have a better score.

My special BFS was thus introduced. It can be seen as my attempt on the Beam Search algorithm but it has a problem, shortsighted. With size 1000, it can only check 6 steps (3^6) and after that, it only inserts if a state is better than the current best state. However, states with more potential might be blocked by local maxima because currently, it has less score.

Introducing beam search, it checks more states compared to my special BFS and accepts states with a lower score. For a beam size of 1000, it always checks for 3000 states per step and chooses the best 1000 and continue with the next step. It is not optimal but often, really close. This algorithm makes the complexity from 30 _ 3 ^ 25 to 25 _ 1000 * 3 (step 25, size 1000 and no diagonal moves).

Now, with compiler optimisation and multi-threading, it runs quite fast. On my main desktop, it is even faster than padopt due to multi-threading. I am certain that with a better eraseOrb() function, pazusoba can be even faster.

Improvements

Safe thread
Better heuristic for OrbProfile and VoidPenProfile
Prevent a cycle especially when the step is more than 60
Better queue and loop

Many improvements have been done so far. Thread is causing some issues and some profiles can be better (they are worse than me and that's not acceptable). There are many duplicate board what should I do about it? If size 20000 only takes about 3s or less, it would be amazing.

Profiles

There are many playstyles in Puzzle & Dragons and profile is just for that. Now, it supports combo, colour, shape and orb based profiles.

Combo focuses on doing more combo with cascading and skyfall (this is the best so far)
Colour focuses on erasing more kinds of orbs (ideally, it should have a weight)
Shape encourages a certain shape (2U, +, L, one row, void damage pen)
Orb encourages to have less orbs remaining (this one doesn't work that well)

You can mix everything together and use for many teams.

Show all profiles

ComboProfile
ColourProfile
ShapeProfile
- TwoWayProfile
- LProfile
- PlusProfile
- VoidPenProfile (doesn't work at the moment)
- SoybeanProfile
- OneRowProfile
OrbProfile (not good enough)

It is quite simple to add more profiles so feel free to fork this repo and add even more profiles.

How to compile

This project was originally developed on Windows 10 with MinGW. Later, I also tried on Mac OS and Linux. Now, I am using CMake to make it easier to build across all three platforms.

Setup

On Windows, MinGW is recommened as this is what I am using. MCVS is also supported but remember to add --config when building. On Mac OS and Linux, g++/clang++ is preferred. Xcode also works on Mac OS.

Requirements

CMake (3.10+)
MinGW/g++/clang++ with C++17 support
- C++11 is the minimum requirement as lambda is used
- Nested namespace requires C++17 but can be easily updated

Setup CMake

cmake -B release
cd release
make pazusoba_binary
./pazusoba_binary.exe

Add -DCMAKE_BUILD_TYPE=Debug to debug or test pazusoba.

cmake -B debug -G -DCMAKE_BUILD_TYPE=Debug
cd debug
make test_pazusoba
./test_pazusoba.exe

Alternatively, you can use make.py.

Build

On Windows, it is recommened to use -G "MinGW Makefiles" instead of MSVC. On Mac OS and Linux, simply use the default. Go to the debug or release folder and run make [target].

The program accepts 4 arguments for now (more might be added later)

Path to the board / board string
Minimum erase condition (by default 3)
Max step (by default 50)
Max beam size (by default 5000)

$ ./a.out GLHLGGLBDHDDDHGHHRDRLDDLGLDDRG 3 25 1000
$ ./a.out assets/sample_board_65.txt 3

By increasing the beam size, it will take more time (linear space) to compute. With more CPU cores, it runs significantly faster.

Benchmark

Binaries are compiled locally and overall time are used based on the same board, max step 50 and beam size 5000. This might not be accurate. Use it as a reference.

Version	A12Z Bionic	i5-9400	Note
0.1α	213.54s	110.34s	Proof of Concept
0.2α	92.46s	39.97s	General Improvement
0.3α	12.06s	10.51s	Compiler Optimisation
0.4α	2.79s	2.15s	Multi-Threading
0.5α	3.06s	1.79s	Profile & OpenCV
0.6β	3.35s	2.04s	Automation
0.7.1β	1.71s	0.91s	General Improvement
0.7.5β	-	-	Full Automation
0.8γ	-	0.77s	Rework

Resources

Things that were helpful during my experiments.

https://www.slideshare.net/mobile/tnkt37/6-37838644, tnkt37 さんのスライド
- tnkt37 さん made a fancy robot that can solve the board in realtime
- He also has a repo with the code behind it
- The introduction of beam search really inspired me and it took me less than 5 min to implement it but it had improved the performance significantly
http://maaak.net/pad/ for basic simulation
https://pad.dawnglare.com/ for better simulation (support 7x6, replay, share and more)
- https://pad.dawnglare.com/?height=6&width=7 (7x6)
https://padopt.macboy.me/, an optimal PAD solver
- This is an amazing optimizer
- https://github.com/matthargett/padopt
https://github.com/alexknutson/Combo.Tips
https://github.com/ethanlu/pazudora-solver
https://puzzleanddragonsforum.com/threads/genetic-algorithm-for-pad.95084/, a great discussion
https://cory.li/puzzle-and-dragons/, a great post
https://github.com/koduma/puzzdra_solver by koduma さん
flood fill & union find
beam search

tnkt37さん's video really inspired me and it was the reason why I started this project.

License

MIT License for pazusoba
LGPL License for QT
BSD License for opencv
BSD License for pyautogui
NumPy License
{fmt}

Legacy Code

They have been removed now. Check here if needed.

Miscellaneous

2000 days

I have been playing this game (the Japanese version) for more than 2000 days (until 2/7/2020). I started playing in 2013 and it was also when I started programming and learning the Japanese language. Lots of great memories back then with my Japanese friend. C++ reminds me of my good old days with C programming. You feel like you can do anything with it. C is special because it was my first programming language but it was a tough way to start programming, lol. Lately, I have been using JS, Python, Dart, Swift and Kotlin. They are modern, nice and easier to write but it is nice to stop and go back to the origin once a while. たま~ たま~

core's People

Contributors

Stargazers

Watchers

Forkers

harjeb

core's Issues

V2 - Improved Performance

Total: 5.82s

mutex::lock(), 1.66s
mutex::unlock(), 1.24s
PState::getChildren(), 1.79s

This is gonna be another 2x improvement if I can improve the getChildren() and use openmp for multithreading.

Update README

The README is outdated. The link for legacy code should also be included.

V2 - CMake

Experiment with CMake and see if it is better than current makefile.

LPJBHDDRBJBPJGRGRJHBJBGLLPBJHD

This board is a very tricky one because looking at least 10 or 20 steps is needed, but it might be a great time to analyze the 52 steps solution. https://twitter.com/blackyukimi/status/1514588139972558852

V1 - Benchmark

Use python to time the total time taken and track the speed in its readme.

Now, a basic one is completed. I will add some result to README later.

Create a list for the benchmark
Test all versions since the first alpha

I will test it on my main desktop later.
It has been added.

V2 - SAT solver

Satisfaction problem.

From my understanding, the algorithm will not stop until a certain condition is met. The condition can be all orbs must be connected with 2 other orbs if possible and bring orbs closer if possible. This is an interesting approach because you don't really need a heuristic and erase combo. This will lose the ability to do cascade puzzle and another issue is that the route might be too long. However, the speed is probably faster because we don't need to do heuristic and erase combo at all. This is more like a static analyser.

See below for my discussion with koduma san. It was a great conversation.

V2 - Profile Update

Profiles should be updated. Currently, Combo Profile is the main one and others are just adding scores based on it. This isn't bad but the score I am giving is definitely not accurate. For example, 2U connected 4 orbs so you should give it more scores (1000 for 3 orbs so 1333 for 2U). However, one row needs to connect 6 orbs in a row but you can do 8 orbs as well. Here, it should discourage connecting more than 6 orbs. There are more examples.
Overall, the algorithm is too greedy. This should be fixed to improve the overall results.

V1 - Performance

The function bool PBoard::eraseCombo(ComboList *list, int ox, int oy) is really slow and takes up almost 70% of the run time. This was captured by the instruments profiler. There are two main issues, queue & map. By improving these two, there should be significant performance boost.

Improve eraseCombo function
Queue optimisation of use something faster
Use unordered_map instead of map

After some optimisations, I realised that the algorithm itself is slow. Mainly around the erase orb and count combo part. There are also some issues with it so I should fix them before moving to v2.

eraseCombo is called too many times and by improving it, the overall performance can be greatly improved. The focus should be on how to erase orbs more efficiently. Other things should be done in V2.

Flood fill is now implemented. It is surprisingly easy to write with recursion. I will fix my desktop and see how much it improved.

V5 - Dart Support/Better API design

Call pazusoba with dart ffi and improve the API of pazusoba.

Added so in Makefile to build a shared library for Dart
Return the route to dart/python
Improve the API design so that, it is easier to be called
- this will add more parameters to the function (profile list included)
- route should use 64bit integers instead (easier to pass back) (one number can do 21 steps so 5 should be enough)
Dynamic profile support (change profile by passing in a different struct?)
- using a 32bit integer should also be fine (4 bits for which profile + 14 bits for colour or the number), an integer list can be passed in as well, just need to unpack it from C++
- if I am doing the integer list, I need to do a script for it as well just to make it easy
Better hash function of the board
Better threading because results are different everytime, this should be fixed
and More...

It is now able to call the method but data is not returned. Surprisingly, Dart FFI is very easy to use.

V2 - Flood Fill Bug Fixes

The main issue now is what's the termination state. If the entire board only has one colour, the algorithm will loop indefinitely. The old implementation is slow but it tracks if the current orb has been visited or not. When to stop and when to erase the orb are the main problem now.

With v2-perfirmance, the board is now flattened and is just an array. This way, it is easier to track visited nodes. This will solve the final issue with flood fill. Also, somehow, 7000 routes are no longer visible. Maybe there are some issues with the flood fill as well.

Bug Fixes

There seem to be some issues with the flood fill algorithm. Sometimes, it might consider a single combo as two combos. This doesn't happen all the time but throughout my testings, it occurs from time to time. Further investigation is needed.

Fix the major combo counting issue
Fix a bug where it considers this a combo

xxx
  xx <- only two orbs so it is not attached to the combo

This can be solved by passing in the direction instead of erased parameter.

When min erase condition is 4, this should be considered as a combo

xxx
  x
  x

Another parameter and a return value should be added to handle this situation. if min erase condition is more than 3, as long as 3 orbs are connected, we should do a flood fill so that the overall connected might be more than the min erase condition. Now, more testings should be done.

Fix a bug where 十字 is never considered as a combo

  X
Xxxx
  X

This should be the final bug to be solved. Combining this and the one above. Flood fill should work 100%.

Testing in process, all issues should be resolved I hope. There seems to a small issue with 十字.

Fix this issue when necessary

 X
Xxxx
 XY

Y is considered as part of X somehow. I might need to check if it is can erase a full board now and try fixed this.

Fix the T issue

  x
yyx
  x

The y part is not considered as part of x. This is critical.

The main issue I guess is still with min erase 4 and 5. I am reconsidering how to do it currently. Flood Fill has improved the performance significantly but it is also important to make it right.

Release - 0.9.0δ

The all new rework of pazusoba. This version is tested and working extremely well compared to previous versions.

Support different profiles
Use std::thread instead of OpenMP

Archived folder and previous implementation will be deleted in 0.9.0.

V4 - OpenCV in C++

This is an early idea to share code between Desktop and Mobile. I am not sure how hard it will be to use OpenCV in C++. Currently, it is only recognizing the board and it can be a bit slow sometimes. In the future, Japanese OCR and a more advanced game state might be added to achieve simple full automation.

V2 - Structure Update

Update the code structure to be more versatile. V1 was great but it is still limited sometimes because some features were added late.

Monte Carlo tree search

This can be something interesting to do some research on. I really want to add some randomness in my algorithm. Currently, a smaller beam search can output a better result. This means that a larger width is not necessary a good thing.

V2 - Reduce Memory Usage

For a small beam size, the clean up is almost instant because there aren't many states. However, when the beam size is over 100,000. The clean up will become slow and also the memory usage is crazy. I tried beam size 2,000,000 with max 25 steps. 50Gb was used. My machine was out of memory so it had to store it on the SSD. This slows down the program massively.

It might be better to store the routes in every single state so that the parent state can be cleaned after children states are created. This will reduce memory usage significantly.

V1 - Heuristic

The efficiency is greatly improved by 2x compared to 0.6β. However, outputs are getting worse. The algorithm should at least always do max combo or close to it. I need to find a way.

This will be resolved in V2.

V2 - Planning

With instrument profiler, I have improved V1 efficiency but my main desktop is down so I haven't tested it on it. I am also getting more ideas about what to do for V2.

Fix GitHub Action

It seems that using thread breaks the build. This should be fixed. Adding -pthread flag doesn't work.

V4 - Android

The ultimate goal of this project is porting it to Android and automate on the device without a computer.
This is similar to V3 but on Android. There are 3 main challenges.

The main goal is to assist the player when needed.

Doing one combo for 999 turns
Clear the same dungeon repeatedly
黒闇と曇

Another potential issue is performance. Android phones tend to have lots of cores nowadays. If multithreading works on Android, performance is not an issue. In the worse case, depth/width can be reduced.

V2 - Score Estimation

The algorithm should know the max possible score based on profiles and this is necessary for early restart and early exit. However, the score might not be accurate sometimes. When to stop is indeed an interesting question. I guess when no better results can be found in a few steps. It can restart or quit based on some conditions.

This should be done before the algorithm update.

V2 - Different Algorithms

V1 is mainly focused on beam search which is a greedy best first search. There are still many issues with it but I want to experiment with different algorithms

I used to do a greedy depth first search. A goal score should be set and the program will terminate as soon as one result is found. This is optimised for speed but routes are not as good.

Overall, the heuristic should be improved. This way even with a smaller beam size, routes should be better generally.

New direction

When I first started working pazusoba, I was only thinking about fancy cascading. It was really fancy, but max combo wasn't achievable most of the time because the algorithm was extremely greedy. I will try a different approach from now on.

V2 - Python

Rewriting the solver in Python as a base for V2. Mainly experimenting with structure and different algorithms.
Python is a bit too slow so... maybe not. I will just do it in C++.

Seperate automation to a different repo?

This repo has already too many things in one. It might be great to add a new repo, pazuauto.

V2 - Shorten Path

Have a look at padopt. It is removing intermediate points so 1, 2, 3, 4 -> 1, 4.

Simplify

Simplifying worked and it is just amazing.
The moves are more robot like because a human cannot be this quick and accurate at the same time.

Shorten

Currently, I have no idea how to to do it. Maybe it is not possible to shorten the path.

Machine Learning

https://github.com/HenryQuan/pazusoba/tree/machine-learning/machine%20learning

V2 - Safer Thread

V1 crashes sometimes so somehow, the thread should be safer so that it will rarely crash or never.
After adding -pthread flag, it seems that it is a lot more stable. Not 100% sure for now.
Now, it is a lot better and crashing is quite rare. Still not 100% safe but good enough.

When width is 500, sometimes there is a deadlock so the program doesn't terminate at all.
More testing needed.

V2 - Better Routes

V1 couldn't solve some board because it will get stuck in local maxima.
V2 will update the algorithm to solve the local maxima issue.

See Algorithm Discussion for more.

V2 - Hash

Currently, the board hash is used but this prevents other state from checking this board. Different state might reach the same board somehow so the hash should also include the current index of the state. The hash was meant to prevent the same state going in circles.

V2 - Better Route

Pazusoba is good in certain areas but in terms of the raw combo count, it still needs some major improvements.

Solve RHLBDGDRHDRJDJRHHJGRDRHLGLDHBB in less than 50 steps, 10 combo
- For this board, light, jammer and green are not erased. It feels like they were ignored somehow

The algorithm is really weak at doing max combo now. Especially, when it is a 10 combo board. This is understandable because it doesn't know about the board. It should scan through the board first before finding the best route.

The algorithm knows too large about the board. Every step should have a deeper meaning. I shouldn't only use combo as the only indication of a good move. The heuristic can still be improved. It should consider the meaning and what does it matter. Maybe I should also look ahead. For example, a quick simulation can be run. It will move towards the end randomly and get the store of that board. By taking the average, it can know roughly how well this path will perform. This will help to avoid local maxima.

Think out of the box and you might find better solutions.

More algorithms

pazusoba is focused on beam search ever since the beginning. It might be the time to try something new. Monte Carlo, Simulated Annealing and there are more. I am fully aware of the issues with beam search.
The challenge is that the heuristic isn't great as it doesn't consider the future that much. Beam Search can find great solutions, but it takes time to do that. Some randomness is definitely needed, but it cannot be fully random. The heuristic is still good to determine if the current board is good or not.

V2 - Multithreading

The mutex lock is using too much time at the moment. This makes my 24 thread machine slower than a 4 thread machine due to 6x more lock and unlock actions. Insert shouldn't be blocking because this makes multithreading useless because the rest 23 threads need to wait for the first thread to finish.
My idea is to make a custom queue base on how many thread the program is using. Each thread will insert to its own vector so no locking is needed. In the end, the queue will insert all and get the top ones.

Release - 0.7.5β

It has been more than half a year since the last release. Currently, pazusoba doesn't work at all so it is great to find the latest commit before the refactor and tag it as v0.7.5-beta.

This seems to be the last commit before automation is moved, a358b63. I will do some testings and publish 0.7.5 later today.

V2 - Better C++ CI

There should be a better CI than the current one. How to improve it though?

V2 - Refactor

V2 - Profile Improvement

Profile is the heuristic and the core of the algorithm. A good heuristic leads to better solutions. However, it is challenging to find a great heuristic by hand. Ideally, I should train the AI to learn it by itself. This is exactly what pazulove tries to achieve.

In V2, profile should work better with each other and also it should be used to analyse the board even before find the solution. This way, the search can stop early if we want to since a good solution may be found already.

Also, more profiles will be added. It is challenging to balance between different profiles. For example, 2U and combo. 2U needs to connect in 4 but combo aims to connect in 3 only. Unless, it is necessary to do 2U, combo should take over. Sometimes, it is fine to do less combo but does more attack. Profile should focus on surviving in game.

unordered_map crashes on Windows

The reason is unknown, pazusoba crashes if the map is over a certain size. This is introduced after switching back to std::Thread.

V3 - Automation for other games

There are many games similar to Puzzle & Dragons. The automation should also work for them with some minor tweaks. Tower of Saviours is probably the one I will try.

V2 - Performance

The performance has greatly reduced in the V2 rework. It takes about 3 - 5 times more and worse route are usually found that before. However, the memory consumption has been reduced and with CMake, it is more versatile than before. Since pazusoba will be working on Android, performance is quite critical now.

Accurate and Time are both part of performance. Improving anyone of them will improve the overall performance.