Euclidea – Geometric construction game with straightedge and compass • Hacker News Board

Re: Euclidea – Geometric construction game with straightedge and compass

#21

Post by mihaifm » Sat, Oct 20, 2018, 3:55 PM UTC

obastani wrote: post #16

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.

Re: Euclidea – Geometric construction game with straightedge and compass

#22

Post by danbruc » Sat, Oct 20, 2018, 3:55 PM UTC

dandare wrote: post #3

I love this game, but I got stack at 1.7, unable to achieve the E star, unviling to give up or seek help :).

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.

[1] https://math.stackexchange.com/questions/1587861/inscribing-...

Re: Euclidea – Geometric construction game with straightedge and compass

#23

Post by 4rgento » Sat, Oct 20, 2018, 5:08 PM UTC

obastani wrote: post #16

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!

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).

Re: Euclidea – Geometric construction game with straightedge and compass

#24

Post by lifthrasiir » Sat, Oct 20, 2018, 5:23 PM UTC

obastani wrote: post #16

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!

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.

[1] https://en.wikipedia.org/wiki/Constructible_number

[2] https://mathoverflow.net/a/211556

Re: Euclidea – Geometric construction game with straightedge and compass

#25

Post by obastani » Sat, Oct 20, 2018, 5:32 PM UTC

lifthrasiir wrote: post #24

obastani wrote: post #16

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!

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 a…

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...

[1] https://en.wikipedia.org/wiki/List_of_interactive_geometry_s...

[2] https://dev.geogebra.org/trac/wiki/TheoremProving

Re: Euclidea – Geometric construction game with straightedge and compass

#26

Post by lifthrasiir » Sat, Oct 20, 2018, 5:42 PM UTC

obastani wrote: post #25

lifthrasiir wrote: post #24

Earlier quoted context omitted.

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 a…

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... [1] https://en.wikipedia.org/wiki/List_of_interactive_geometry_s... [2] https://dev.geogebra.org/trac/wiki/TheoremProving

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).

[1] http://ggb1.idm.jku.at/~kovzol/papers/Kovacs-Recio-Weitzhofe...

Re: Euclidea – Geometric construction game with straightedge and compass

#27

Post by cvoss » Sat, Oct 20, 2018, 6:31 PM UTC

obastani wrote: post #16

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!

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.

Re: Euclidea – Geometric construction game with straightedge and compass

#28

Post by spiralganglion » Sat, Oct 20, 2018, 7:39 PM UTC

Nursie wrote: post #8

This one is also fun, just challenges to create different shapes, and shapes-within shapes in under a certain number of moves - https://sciencevsmagic.net/geo/

Came here to post this — it's one of my favourite math games.

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...

Re: Euclidea – Geometric construction game with straightedge and compass

#29

Post by MauranKilom » Sun, Oct 21, 2018, 3:14 PM UTC

mihaifm wrote: post #21

obastani wrote: post #16

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…

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).