The solution will rattle you! At least it did me. I happened to blindly stumble upon it while trying various approaches, but I’d love to know what sort of intuition it takes to find the solution short of brute-forcing/lucky-guessing it.
In case you eventually give up - as I just did - or somebody else is interested, here [1] ist the solution. It is definitely not a straight forward construction.
This is brilliant! What I really want is a list of such mathy games for my 6 year old. I found him a logic gates (XOR, AND, etc) game that he also likes.
What’s the logic game? I’d also love to find more games like these for my kids (they love playing with Euclidea, but it’s too abstract for them to grasp).
Another one they do manage to understand (and love) is Lightbot http://lightbot.com
It's not open source from the looks of it. It's a freemium game, they have in-app purchases on mobile where you can unlock all levels without completing the previous ones. Some of those levels are insanely difficult, so you have to either lookup the solutions online or pay for unlocking, otherwise it's pretty much impossible to advance.
Constructing '1.2 Perpendicular Bisector', I got stuck trying to use the hot key T. I switched to 'explore mode' to see the hint and realized I could complete the task using a compass. Then, on the next screen I 'discovered the Perpendicular Bisector tool'. Maybe greying out the different tools at the bottom would make the locked tool more apparent during the tutorial--I almost abandoned the site, but stubbornness compelled me to try again. hehe.
Does anyone know what are the algorithms behind this game, i.e., how does the game decide whether a given construction is valid? I'd appreciate any pointers!
I am intrigued by this as well. I think they check for the existence of certain primitives and a sequence in which they are drawn. For example for level 1.1 where you need the 60 degree angle, if you use Explorer mode to view the solution and then you draw a "cheated" line on top of it, it won't give you a completed level because you don't have the sequence (2 circles and an intersection point). It also doesn't allow you to draw another line on top of an existing line, so you'd have to restart the level in this case.
It won't give you a completed level because you're in explorer mode, not because the step sequence is wrong. Also, you don't have to restart to leave explorer mode (at least in the web version).
My guess is that it uses analytical geometry to compute the equations of the drawn items. This also may includes a mapping to some canonical dimension(size) and orientation(rotations).
My cursory analysis suggests that there are hidden constructions invisible in the game but used for the verification (you can see a base64-encoded task file flying through the network). The actual verification happens in an Emscripten-powered C++ engine and it is pretty opaque to me---the only thing I can identify is a parser for the task file.
My best guess without the actual source code is as follows: The perfect algorithm would involve the equality between two functions returning constructible numbers [1], where each function would map from unspecified points (that you can move around with the hand tool) to the result points. As far as I concerned comparing two constructible numbers is possible but inefficient [2], and comparing two functions is probably much harder. However for the purpose of game, we can approximate the equality by randomly evaluating a difference between two functions to the reasonable accuracy and checking if it is close to zero. Theoretically exact real arithmetic would be preferable, but adaptive fixed-precision real arithmetic may be also possible as long as rounding errors are tracked.
Thanks for the response! I think you're right that it's something along these lines. I didn't find any further information about Euclidea, but for anyone interested, I did find some information about open source engines that achieve similar purposes [1,2]. Need to do some more digging...
Thank you for the pointer to Geogebra, yeah, there ought to be someone already dealing this :-) It seems that there are some shortcuts for many functions (e.g. [1] only evaluates the function finite number of times).
As others in the thread have pointed out, Euclidean geometry is decidable, but the proof of that fact corresponds to a highly inefficient algorithm for actually checking whether two points are equal.
An alternative approach would be to "cheat" and do a numeric approximation. Constructible numbers (the coordinates of any point the player can make) are always the solution to a quadratic equation whose coefficients have been previously constructed. So, especially for constructions that aren't very "deep" (as would be found in this game), we can easily find the decimal approximation to high precision very quickly. In no time at all, this approach can determine with high confidence that the player's solution and a prototype solution are probably the same.
I would speculate that constructing a near-miss that is falsely deemed correct by this method would require an inordinately complex construction.
28 comments
[ 2.6 ms ] story [ 67.1 ms ] thread[1] https://math.stackexchange.com/questions/1587861/inscribing-...
Another one they do manage to understand (and love) is Lightbot http://lightbot.com
https://play.google.com/store/apps/details?id=com.Suborbital...
It's so good I managed to do all 135 puzzles in two days and another few hundred generated ones.
The generator might need some work. A lot of the ones it makes are too simple, solvable in 1 or two moves.
https://kasperpeulen.github.io
https://sciencevsmagic.net/geo/
For a really nice introduction to the more advanced uses of geometric algebra in three dimensions, there's this fantastic chapter in a book by Rudy Rucker, which you can read here: http://www.rudyrucker.com/infinityandthemind/#calibre_link-3...
My best guess without the actual source code is as follows: The perfect algorithm would involve the equality between two functions returning constructible numbers [1], where each function would map from unspecified points (that you can move around with the hand tool) to the result points. As far as I concerned comparing two constructible numbers is possible but inefficient [2], and comparing two functions is probably much harder. However for the purpose of game, we can approximate the equality by randomly evaluating a difference between two functions to the reasonable accuracy and checking if it is close to zero. Theoretically exact real arithmetic would be preferable, but adaptive fixed-precision real arithmetic may be also possible as long as rounding errors are tracked.
[1] https://en.wikipedia.org/wiki/Constructible_number
[2] https://mathoverflow.net/a/211556
[1] https://en.wikipedia.org/wiki/List_of_interactive_geometry_s...
[2] https://dev.geogebra.org/trac/wiki/TheoremProving
[1] http://ggb1.idm.jku.at/~kovzol/papers/Kovacs-Recio-Weitzhofe...
An alternative approach would be to "cheat" and do a numeric approximation. Constructible numbers (the coordinates of any point the player can make) are always the solution to a quadratic equation whose coefficients have been previously constructed. So, especially for constructions that aren't very "deep" (as would be found in this game), we can easily find the decimal approximation to high precision very quickly. In no time at all, this approach can determine with high confidence that the player's solution and a prototype solution are probably the same.
I would speculate that constructing a near-miss that is falsely deemed correct by this method would require an inordinately complex construction.