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

Saturday, July 15, 2017

Sprouts 2017 Summaries, Session I

Here are summaries of the first round of presentations from Sprouts 2017!

Destiny Martin: The game of Locking Nim

Destiny presented a really cool version of Nim: Locking Nim.  The only difference between this and Nim is that players cannot play on heaps of the same size as another heap in the game.  First glance: this should be the same as Nim, right?  After all, in Nim, two equal-sized heaps cancel out in the Nim-sum.  This isn't the same here, though, because there could be three heaps with the same size, and now they're all irrelevant!

Destiny found that with three (non-zero) heaps, games are in P exactly when they nim-sum to zero and the piles have unique sizes.  If they are not unique, the position is in P exactly if they're all the same size.  For four heaps, the regular nim-sum-to-zero property holds for P, whether or not the four piles are unique.


Nick Paolini: Node Hackenbush disguised as a Chomp variant

Nick modified Hackenbush to create Polar Bear Plunge, a game played on a grid-graph.  On one node of the grid sits the polar bear, acting as the ground from Hackenbush.  Players take turns removing other nodes (ice bergs) from the graph.  If another node is not reachable from the bear, it disappears too.

Nick determined formulas for all 1-by-n and 2-by-n boards, no matter where the bear is located.  For other n-by-m grids (both greater than 2), all you need to know is the parity: the game is equal to * if n times m is even, and 0 otherwise!

Emilee Jurkowski: Crab & Gulls

Emilee built a variant of Queens: a game where players alternate turns placing non-threatening Queens onto a chessboard.  Crab and Gulls is similar, except that Bishops (Gulls) are placed instead of Queens and they don't need to threaten each other, but instead must threaten a separate Crab piece.  A turn consists of two parts: place a threatening Gull, then move crab to any other space (not necessarily adjacent) that isn't threatened.  (Both parts of the move need to be completed.)  She came up with two further variants: King & Gulls (the Crab moves like a King) and Rock & Gulls (Crab doesn't move, but each new Gull needs to threaten it).

Emilee calculated the nimbers for all Crab & Gulls starting positions on a 2-by-{2, ..., 8}, 3-by-{3, 4, 5, 6}, and 4-by-{4, 5}.  She also found the King & Gulls nimbers for starting boards for 2-by-{2, .., 11}, 3x{3, ... 7}, and 4-by-{4, 5}.  For Rock & Gulls, she realized that this game is just equivalent to Nim with 4 heaps.

Thursday, June 15, 2017

Game Description: Cutthroat and Impartial Cutthroat

A long time back, while going through Lessons in Play, I got hung up on the definition of Impartial Cutthroat in section 2.2.  I completely forgot about this until recently, when a student asked me to explain what was going on.  Today, I had a look back at Cutthroat and Impartial Cutthroat and confirmed my understanding with Richard Nowakowski.  In this post, I'll try to clarify both games.

Cutthroat is a partisan game played on a graph where each vertex is colored Blue or Red.  In addition, each connected component of the graph must include vertices of both colors.  Each turn a player chooses one of the vertices of their color and removes it from the board, including all incident edges.  Then, remove any connected component that includes only vertices of one color.

Here's a whiteboard sketch of a Cutthroat game tree I made today:

 
Notice that Red has an immediate move to zero by choosing the lower red vertex.  (The remaining two connected components are both mono-colored, so they are immediately removed.)

I've added this as it's own entry in the ruleset table.

Impartial Cutthroat is a bit different.  On one hand, it's the same game if you assume that players can choose vertices of any color AND all vertices are given a unique color.  

Another way to explain it is that a position is an uncolored graph where each vertex must have at least one neighbor.  On a player's turn, they choose a vertex and remove it and all incident edges.  Afterwards, all vertices with no neighbors are also removed.

Yet another way to explain Impartial Cutthroat is by considering it as a variant of Node Kayles.  In Kayles, a player chooses a vertex, then removes that vertex and all of its direct neighbors.  Here, there are two differences:
  • The player must choose a vertex that has at least one neighbor.
  • Only the chosen vertex is removed, not any of the neighbors.
Because of this similarity, I've included it in the ruleset table as a variant of Node Kayles, instead of a standalone game or a variant of Cutthroat.

Monday, May 1, 2017

Sprouts 2017: Overall Awesomeness

I spent all Saturday at Sprouts 2017, and it was excellent!

Craig Tennenhouse organized an amazing experience.  Everyone got a Gamester Pen, a program with a CGT quick-reference-page, a grid-lined notebook decked out with a gamey cover, and a nametag with the logo.

 Official Sprouts Notebook

His students gave amazing talks.  Each had created their own game, complete with actual pieces they had 3-D printed or otherwise manufactured!  It was clear they had spent lots of time analyzing their games, and had learned CGSuite to help get results.  One student had learned about Atomic Weights and applied that theory to their analysis!

Infinitiles

My student, Matt, also gave an excellent talk.  He discussed AI methods to play Chess and Go.  After all the talks, we got into working groups and looked at a few games more deeply.  I am definitely convinced that undergraduates can contribute to this field!

I'll post comments about the individual talks, though that may have to wait until the semester wraps up.  In the meantime, I've already started dreaming about Sprouts 2018.

Sunday, April 23, 2017

Sprouts 2017: A CGT Conference for Undergrads

Exciting news for New England Gamesters: Craig Tennenhouse is organizing the first Sprouts, a conference for undergrad CGT research.  (I helped by making the website.)  Sprouts 2017 will take place at the University of New England (Biddeford, ME) on April 29.  The basic plan is to continue hosting Sprouts every year at either UNE or Plymouth State (NH).

I know this announcement is a bit late, but things have come together only recently.  Inspired by our desire to get our gamester undergrads involved in research, we're harnessing the opportunity presented by Craig's research class.

Hopefully in the future, we'll be able to get the word out sooner to attract visitors from the region.