Games@Dal 2016: Urban talks about Drawing Triangles

Games@Dal 2016 talks: "Hopeful Windows in Cellular Automata and Combinatorial Games" - Urban Larsson

Urban talked about the Hopeful Window Triangle-Placing Game, a very interesting game based on his work with cellular automata games.  In this game, there are multiple steps per turn revolving around drawing a digital 45-45-90 triangle on a grid.  The triangle always has one box at the top, and the hypotenuse descends on the left-hand side.  There is a single box lower in the grid that is the blocking box:

• No triangle can be drawn that contains that box, and
• The first player to draw a triangle past that box wins.

At the beginning of each turn, there are candidate boxes that the current player can start with are all in a horizontal row.  (I'll explain how those are generated as part of the turn below.)  The steps to each turn are:

• The current player chooses one of the candidate boxes for the top of the triangle, then draws it as far down as they want.  (If they start out to the left of the blocking box, then they can automatically win by drawing a large-enough triangle.  Otherwise, they can't cover up the blocking box.)
• Consider the boxes directly beneath the drawn triangle - the triangle's support, but increase this set by extending to the left and the right by two boxes on each side.  (This can be parameterized to be any l and r numbers.)
• Inside of this elongated support, the next player chooses a "hopeful window" of, say, 6 adjacent boxes.  (Again, this can be parameterized.)
• The previous player then gets to block, say, 3 of the boxes in that window.  (Parameterizeable again.)
• The remaining 3 (in this example) boxes from that window become the candidate top boxes for the next player to choose from on their turn.

The game is certainly a bit complex, but Urban found an extremely surprising relationship between this game and automata that generate Sierpinski-Triangle figures.  By using the l, r, w (window size), and b (number of block) parameters in the formula for the triangle-creating automata, the resulting pattern of triangles tells you exactly which boxes you should choose to start a new triangle from: choose one of exactly those which remain uncolored in the diagram.  Amazing!