Thursday, October 26, 2017

Games and Graphs Workshop, Day 1 Talks

The Games and Graphs Workshop in Lyon was outstanding!  There were so many talks, but I think I understood at least the basics of most of them.  The first talks were on Monday.


Aviezri Fraenkel: "Problems and Results in Combinatorial Games and Combinatorics"

Aviezri presented a talk about games with some elements of (Economic) Game Theory (EGT).  For example, he considered playing Geography on a binary tree where all terminal nodes are after Alice's turn, except for a great many on the lowest level.  At each level, Alice has one instantly-winning move, but what if there are many other moves and Alice can't differentiate between them? Now she is essentially choosing at random because of some hidden information.  With enough of these extra edges, she is not going to be able to win the game, despite having a winning option each turn.

Aviezri showed many other connections to EGT and called for future work on infinite games in the partizan, scoring, and misere realms.


Craig Tennenhouse: "Three Graph Games"

Craig presented three new games: Tumbleweeds, Deletion/Contraction, and Total Conversion.  Tumbleweeds is a cool variant of Hackenbush without a static root.  Instead, whenever a player chooses an edge that breaks the graph up into multiple connected components, that player chooses either of the components to completely discard!

The partizan game Deletion/Contraction is played on a multigraph (but no loops).  The Left player moves by deleting an edge on their turn, while the Right player chooses an edge to contract (removing any loops that are created).

In Total Conversion, the position is a graph with a non-zero game embedded into each edge and each vertex colored either Red or Blue.  To take a turn, the player must make a move on each game where the edge has ends colored in opposing colors.  Edges with exactly 0 are then removed and both vertices are subsequently repainted with that player's color.

Craig already drew attention with these games and, as always, I suspect he has about three new projects as a result of the conference.


Loic Cellier: "The Game of Hex"

It always seems like there are new things to learn about Hex.  Loic presented just about everything I knew and lots that I didn't.  He covered the history---I did not know that Einstein was a supporter of the game!---the connection to Y, and even presented a variant of the Pie Rule, the Swap Rule:  Here, instead of swapping the identity of the players (if Player 2 wants), instead just swap the color of the piece on the board.  This is, of course, not always equivalent; it prevents the first player from playing in a position that would be too good for their opponent as well.

I also (finally) learned why a Y game must end, by the self-reduction of each vertex into a hex on a slightly-smaller board.  This is surprisingly elegant and easy to explain, but with that little twist that makes it amazing.  It may be more likely to be in The Book than the Hex Theorem (that no Hex game can end in a tie.


Milos Stojakovic: "Maker-Breaker Games Played on Random Graphs"

Milos talked about Positional Games: maker-breaker games on a finite set of elements, X, where F, the winning set, is a subset of the power set of X.  The players alternate turns claiming one element of X.  Maker then wins if they claim all the elements in some set in F; Breaker wins otherwise.  Milos paid special attention games where X is the set of edges in a complete graph.

Unfortunately, for many common sets F (e.g. set of Triangles) it is too easy for Maker to win.  To balance things out, he considers adding biases for each player to change the frequency of turns.  (E.g. Maker takes 3 turns, then Breaker takes 7.)  The idea he took off with was to begin the game by removing a number of random edges.  If each edge remains with probability p, how low does p have to be before Breaker can (usually) win?  He calls this the Threshold Probability, and looked in to determining this value.


Mirjana Mikalacki: "Fast Winning in Positional Games on Graphs"

Mirjana is also interested in positional games, but is looking for other ways to give Breaker a chance to win.  Instead of removing some edges, she considers a "fast" variant where Maker only gets to make a certain number of moves before the game ends in Breaker's favor.  (Breaker still gets to move as normal too.)

Mirjana also combined this with the biases mentioned above.  These "combination" fast games generalize positional games significantly.

Sunday, July 30, 2017

Elwyn's CG Videos

Elwyn Berlekamp's video-talk at Fundy and Games, "A Program of Introductory Videos on Combinatorial Games", alerted me to something I didn't realize: Elwyn's been creating a bunch of videos to introduce CGT.  Since the meta-video presentation, I've been watching the videos.

He's using some good philosophy towards introducing concepts:
  • Examples come before the abstractions.  It's easier to motivate the abstract notions once you've seen some concrete examples.
  • Delay notation as long as possible.  The non-standard notation used while still showing the initial concepts works just fine.  For example, instead of using N and P (outcome classes), the impartial videos start off with just checkmarks (for N-positions) and circles (P).
Here's the sequence of videos on impartial games.  They use an impartial version of chess where each piece occupies it's own board and each piece can only move towards the southwest corner.  The first video describes what happens with one King, and the following videos show what happens as other pieces get added, each time adding a new concept to the theory of games.

Here's the sequence on partisan games.  I haven't watched as many of these yet.

These are a great resource for introducing CGT.  I'd really like to know how effective these are in a classroom setting (at any level).

Friday, July 28, 2017

Game Description: NoCanDo

For the tournament game at Fundy and Games, we played a variant of Domineering known as NoCanDo.  (We spent the first day deciding on the name.)  This is a very nice mix of Domineering with a little splash of NoGo: each domino on the board must be adjacent to at least one uncovered square.  That's it.  You're not allowed to play a domino if it would be completely surrounded or if would cause another domino (already played) to be completely surrounded.

This little rules change makes a huge difference! 
  • You can place pieces aggressively to force an opponent to leave spots open.
  • You need three spaces in a line for a free move, instead of two.  (And sometimes you can't play in those three anyways because it blocks other dominoes.)  Five in a line can often net you two plays, but I don't think I ever had a group worth three.
  • The "liberty" rule is still different from Go and NoGo, because each domino needs the free space, not just each connected group of similarly-oriented dominoes.
  • When the game breaks up into subregions, sometimes they're not all independent.
We held human and computer tournaments at Fundy and Games.  RJN won the human tournament, and my program won the computer tournament.  Richard handily beat my computer player to win the overall title.

Thursday, July 27, 2017

Game Description: Slimetrail

One of the games Ludus has used in their national tournaments is Slimetrail.  This game is simple enough that it can be played by a wide age range, but there are many complicated strategies that can be used by more advanced players.

Slimetrail is played on a connected graph, with one vertex colored Blue, another colored Red, and a third vertex with a moveable piece or token which will create the trail of slime.  The two players alternate turns moving the token one space, then marking the previous space (where the token was) a third color (usually green).  The token can never be moved back to one of these "slimed" spaces.

A player wins when the token is moved onto the space of their color.  Since we want to make sure that one player can still win, it's not allowed to move the token to a space where it can't reach at least one of the two goals.

In all the examples I've seen, Slimetrail is played on a grid, with adjacencies in all 8 directions.  Apparently, it's also played on hex grids.

I wrote a playable version using Javascript.  My auto-AI players are terrible at this game, but you can still try it out.  In order to make this strictly-combinatorial (the last player wins) I altered the rules slightly so that you can't move to your opponent's goal space. 

(Edit: the link to the game didn't auto-clickableify, so I added a clickable link.)

Tuesday, July 25, 2017

Fundy & Games 2017: Quick Highlights

Fundy and Games was excellent!  After driving through Saint John three times, I'm really happy that I got to experience it first-hand.  I love the fog!

Here are some quick highlights (from my perspective):
  • The talks were great!  I'll include another post summarizing these.
  • I worked with a group that solved a complexity problem on the first full day of working groups.  Both of the undergraduates from Plymouth State made significant contributions towards the result!
  • The game Richard proposed, NoCanDo, made for a great conference tournament game.  (I'll have a separate post describing the game, but it's a variant of Domineering.)  
  • My students were interested in participating in a NoCanDo computer tournament, so I wrote some code to model the game, then a display to show the progress in the game.  To give them something to play against, I wrote a very basic AI (just case-based, with no end-game wrangling).  Amie wrote a player with a very similar strategy.  In the computer finals, my code squeaked out a victory against her, winning 507 of 1000 games.  Yikes!
  • Amie also beat me in the human tournament.  I had a slightly better record, then got beaten by RJN in the finals.  RJN went on to handily defeat my computer player to be the Overall 2017 NoCanDo World Champion!
  • I saw the Reversing Falls go backwards!  Sweet!  (I saw them go forwards last year when we dropped Neil off.)
  • Neil and Rebecca McKay were excellent organizers!  I greedily ate many of the snacks they provided.  They even made certificates for the tournament winners!
  • I'm still not sure what a Seawolf is.  

  • I continue to enjoy traveling to Atlantic Canada for games!

Monday, July 17, 2017

Sprouts 2017 Summaries, Session III

After lunch we had three more talks to wrap up Sprouts 2017.

Matt Ferland: Applying Heuristics in Combinatorial Games

My own student, Matt, explained some of the tactics used by AI to play Chess and Go.  He talked about all the different heuristics used to approximate the values of Chess boards (I had no idea how deep this really was) and then gave a good overview of just how far computer Go players have come.

I learned a ton from this!  It's been great to have a student really interested in exploring Artificial Intelligence.

Ethan Wester: Protect the King

Ethan presented a game similar to Crab & Gulls.  This game is partisan, with two kings (one per player).  The bishops, however, now threaten both kings.  A turn consists of first moving your own king (like a King does in Chess) to an unthreatened location, then placing a new bishop that threatens the opposing king.

Ethan found a bunch of values for this ruleset: all integers, all switches, *, *2, Up, Down, 1/2 and 1/4.  Wow!

Cameron Hodgdon: Analysis of a New All-Small Game: An Introduction to Kanye

Cameron created the game Kanye (I think he named his before Ashlee named "Also Kanye").  This is very similar to Also Kanye, except that all pieces are the same color, so the game is dicotic (all-small).  The is still partisan, though: Right chooses a column and moves that column North.  Left chooses a row and moves it West.

Cameron evaluated games for a bunch of different patterns of starting configurations.  Then he even found the atomic weights for these games!


As you can see, it was very easy to get excited about all of the great work these undergrads had done!

Sunday, July 16, 2017

Sprouts 2017 Summaries, Session II

Two talks were given in the second session at Sprouts 2017.

Kristen Falcinelli: Undecidability demonstrated by a tiling game

Kristen showed a new game, Infinitiles, where players each have their own library of Wang Tiles.  The starting position is a finite or infinite grid with at least one tile already on the board.  Each turn consists of a player choosing one of their tiles, then placing a copy of it onto the board somewhere adjacent to one of the tiles already on the board.  The placed tile must match all the other tiles it touches.

Kristen was able to find many values in the game: all integers, all switches, *, Up, Down, and 1/2.  One issue she found was that on an infinite board, it is undecidable to determine whether the game will finish on an infinite board!

Ashlee Tiberio: Also Kanye: Examining patterns in a strip game variant

Ashlee created a grid game similar to Drag Over, but in two dimensions.  On a grid with red and blue pieces, you move by choosing a row or column, then you move all pieces in that space.  If it's a column, you move all pieces up ("North"); if it's a row, you move all the pieces left ("West").  If the pieces fall off the board, they are removed.  You can only make a move if you have pieces left on the board.

Ashlee found number values for all 1-by-n strips where either all spaces had a token (of the same color) or one space had a token.  She also found values for 1-by-n strips with two tokens of separate colors.

Ashlee also noted that the misere version of this game should be called "Imma Let you Finish".