Sprouts Explained | Hacker News Reader

Sprouts Explained

nrich.maths.org

90 pointscjg14 comments

Martin Gardner's "Mathematical Games" column that popularized this game also included a description of a variant: Brussels Sprouts (http://en.wikipedia.org/wiki/Sprouts_(game)#Brussels_Sprouts), played with small crosses instead of dots.

While appearing similar, in Brussels Sprouts the result is always fixed: if there are an odd number of crosses initially, the first player wins; otherwise, the second does.

I've thought it would be interesting to have an app to play this game. The hard part would be intersection detection on beziers or splines.

Maybe you could simply check whether the graph is planar?

Thought of that, but then there's the aesthetics. Perhaps, the answer is drop user-guided drawing and have an algorithm determine whether it is planar and do the routing. But, I still like the idea of user-guided drawing.

A user-guided force layout and the algorithmic check would be fine aesthetically if it were implemented well. For one thing, it would bring more attention to the mathematical abstraction by removing an unnecessary degree of freedom.

Seems like the sort of thing that some clever hacker could put together in a d3 fiddle.

That's insufficient. If you call enclosed areas (including the one 'at the putside') faces, you sometimes can draw an edge A-B either through face F or through face G.

For example, in http://en.wikipedia.org/wiki/File:Brussel_Sprouts_Game.png, position 3, you can draw a 'diagonal' vertically through the large enclosed area, but you can also draw a graph edge between the same two vertices 'around the outside'.

Similarly, you can have disconnected parts of the graph, where it is essential to know in what 'face' they lie. For example, starting with 3 points A, B, and C, draw a circular edge from A to itself. There are two ways to do that, one where B and C end up in the same face and one where they do not.

If you store the graph as a pair (V,E), you lose that information.

It doesn't deal with the UI, but for the back end game logic, you might find "How to Play Sprouts With Playing Cards" useful. http://www.takingthefun.com/2013/06/how-to-play-sprouts-with...

I made a start [1, 2]. No intersection detection yet though.

[1] - https://github.com/richardTowers/Sprou.ts [2] - http://richard-towers.com/Sprou.ts/Sprouts/

You may want to take a look at http://www.leemon.com/papers/2008bb2.pdf (via http://www.wgosa.org, a prime example of 'content is king'; no looks, but hours of reading)

Interesting: Co-inventor of Sprouts is John Conway, inventor of Conway's Game Of Life

Another trivia point is he's the inventor of surreal numbers, which Knuth (yeah, that Knuth not some other Knuth) wrote an enjoyable little semi-fictional novel about in the 70s. I thought it was a fun book, its not intense like TAOCP.

Conway's also the author of ONAG. On Numbers And Games. You'll probably run into that acronym in serious discussion about game theory, like computer game design or RPG system design. Its a pretty intense book. From memory its one of those "$50 for 100 pages" hardcovers. But, worth it.

http://www.amazon.com/On-Numbers-Games-John-Conway/dp/156881...

As a ten year old I played a game like this one but where you chose a fixed grid, and took turns filling in the edges of the component small squares. The winner enclosed the most squares, I think! As a chorister in a C11th cathedral there was a lot of time to be spent not listening to sermons, so we devised (or learned from someone's dad) these fun games. I think we usually used an 8x8 grid.

Edit: here we are: http://en.wikipedia.org/wiki/Dots_and_Boxes

People who like this might want to try Simon Tatham's puzzles. (the author of Putty)

    http://www.chiark.greenend.org.uk/~sgtatham/puzzles/

Bridges and perhaps Untangle might be most similar.

Reply on news.ycombinator.com