During the last summer, to have some good relaxing moments, I continued to play with Ruzzle, on my way!
In fact, I adapted the Ruzzle Solver algorithm to write solutions directly in my phone: and this is how Ruzzle Solver 2 was born!
In that last version the phone is connected to the computer. This one does a screenshot in the phone, and extracts all the letters and multiplicators (TW, DW, …) with a simple but interesting OCR, that I implemented for this project (the other existing OCRs, despite that they are more general, sometimes do some mistakes).Then, it calculates all the solutions using the core solver, written in C++, that is the same that you can find in the classic Ruzzle Solver. Then, it writes all the words in the phone, seeming like Speedy Gonzales.
But the story did not end here! I extended the project, creating a simple artificial intelligence (known by friends as BOT).
This artificial player looks for available matches, and then plays in complete autonomy. If there aren’t any matches, it requests a new random opponent, and obviously it is polite, accepting all the invites becoming from other players.
To make a player that behaves like an human, the artificial player has some features:
- It uses the Beta Distribution to choose good, but not too good, words (to avoid all the suspects).
- It applies an instintive human reasoning: if the word that it is writing is “bet”, probably the next words will be “better” or “butter”. In this way, the final word list seems written by an human.
- It determines the current round, to change its behaviour.
- Sometimes it draws casual words. In this way it never gets 100% of accuracy.
- It limits the number of words (a casual limit, that varies with the current round).
- It limits the number of points (a casual limit, that varies with the current round).
- The dictionary is limited, only a subset of the complete one.
Finally, in December, I optimised the algorithms to be runnable in limited machines, and to be executable in the Raspberry Pi. This is the reason why I decided to make the videos that you can see in this page, labeling them as “Raspberry Pi Plays Ruzzle”.
# Some implementation details
# Letters extraction
The screenshot image is divided in 16 sub-images, one for letter. For each one, the algorithm makes a fingerprint that summarises its informative content, in this way:
- It analyses 81 points for each letter.
- It builds a fingerprint as a binary number of 81 bits
- A 0 represents a white zone (the background)
- A 1 represents a black zone (the part of letter)
With a little supervised training, I made a list
L, that can return the associated letter of a fingerprint.
Despite that, there are some noises caused by different factors: the fingerprint of a specified letter is not always the same over time.
For this reason I realised a simple similarity function, that decides how much two fingerprints are similar to each other. The algorithm works as the following:
- It sets a initial score as 0.
- It analyses all the bits in the fingerprints.
- If the i-th bits are equal it increments the score.
- If the i-th bits are not equal it decrements the score.
- In this way, the more is the score and the more the fingerprints are equal.
To summarise, to extract a letter
X from the game screenshot, it first calculates the fingerprint
f(X). Then, it searches in the list
L the most similar fingerprint of
f(X), and finally it determines that the letter is the correspondent one.