Games@Dal 2016: Neil talks about Transitive Games

Games@Dal 2016 talk: "A unique form for hereditarily transitive games" - Neil McKay

Neil McKay spoke about a new term: Transitive Games.  A game, G, is left-transitive if all positions that could be reached from a series of left-only moves from G are also (immediate) options of G.  Right-transitive is defined analagously, and a position is transitive if it's both left and right-transitive.  Games are hereditarily transitive if their subpositions are also transitive.

The ruleset MAZE is transitive, because players can move as many spaces in their direction as they want during their turn.  (At some point, I should write a Game Description post about MAZE and MAIZE.)

Neil defined closures for (hereditary) left-transitivity, by recursively adding, as new Left options, all Left options of Left options.  Again, the right closure is analagous.  Speaking in terms of rulesets, MAZE is the hereditary transitive closure of MAIZE.  It's still not known which rulesets have a transitive version that's equivalent.

Games at Dal 2016

I arrived in Halifax for Games at Dal 2016.  The trip was extremely fun: I drove from Plymouth, New Hampshire, and picked up Craig Tennenhouse, my student Amelia, and Neil McKay all in separate places.  As Craig said, we were like the Muppets, getting the band back together.



We had six talks yesterday; I'll write something about each of them in the coming days.  We have some new people, including Israel, a nice Brazilian graph theorist who studied a traditional game with Urban.

The working sessions begin today, and I'm hoping I can convince some people to look at some computational complexity problems with me.  We'll see about that. ;)  Last year, Games@Dal was extremely kind to me.  I started a new research project with Svenja, Silvia, and Melissa, and we had the paper submitted just two months later.  That's my fastest turn around research-to-submission ever!

Either way, Dalhousie and Halifax is a beautiful setting for thinking about games.  Huge thanks to Richard, Melissa, and Svenja for organizing and running the conference!

I failed to announce this conference beforehand, unfortnately.  After this trip, I'll post about upcoming conferences, including Integers 2016 and CGTC2.  This next academic year will definitely not be devoid of CGT gathering opportunities!

Game Description: Manalath

Thanks to an old email from Svenja, I just started playing an excellent game today: Manalath.

Manalath is played on a hex of hexes (though I've just been playing on a rectangular(ish) hex grid since that's all I have today).   

• Each player has their own color, but can play either color piece.
• You're not allowed to create connected components of one color of size 6 or bigger.  
• If you (or your opponent) creates a connected component in your color of 5 pieces, you win immediately.  
• However, if at the end of your turn, a connected component of your color of 4 pieces exists, you lose (unless you've already won).

The game is super fun.  As Juan Beltrán said after playing a bunch, "This game has really high fun per minute."

This was apparently designed by a fan of Yavalath, not by one of Cameron Browne's programs. :)  After having played Yavalath a bunch the past two years, I find this to be a bunch more fun.  There are all sorts of unexpected winning moves and also unexpected escapes. 

It definitely belongs on the table.

Upcoming CGT Events

There are a bunch of academic CGT events coming up!

2016:

June 24-27 (Fri-Mon) is the CMS Summer meeting at the University of Alberta, Edmonton.  There's going to be a special session on CGT in honor of Richard Guy's 100th birthday!  It sounds like Richard will be there!  Sweet!  It's not yet clear which day will have the special session.


Aug 10-13 (Wed-Sat): Games-at-Dal(housie) 2016 in Halifax, NS.  Last year's was really productive for me; I really hope to make it to this one.


Oct 6-9 (Thurs-Sun): INTEGERS 2016 at University of West Georgia.  Integers is back on the menu! :)


2017:

Jan 25-27 (probably): CGTC2 in Lisbon.

June or July (maybe): CGT and/or Games on Graphs in Lyon, France.

July 24-28: 2nd Mathematical Congress of the Americas in Montreal.  There is the chance of having a CGT special session here.

Two different Anti-Clobbers

In a post many years ago about Martian Chess, I mentioned trying to play a Clobber variant where each clobbering move destroys your own piece instead of the opponent's.  In the comments, Michael Albert replied that he had already studied this game a bit and was referring to it as Anti-Clobber. 

I liked that name and ran with it, and mentioned it in some talks, etc.  Then, a few months ago, I found out that there's already a different game with this name and it's implemented in CGSuite.  Clearly that's enough reason to change the name of the game I've been calling Anti-Clobber.

The actual Anti-Clobber is really like playing Clobber in reverse: each turn, instead of clobbering an adjacent opposing piece, you move a piece into an adjacent unoccupied spot and place a new opponent piece in the space you just left.  It's definitely non-trivial, interesting, and fun.  There are some sneaky moves you can make.

Good news:  This is a great game!

Bad news: It is definitely more Anti-Clobber than the game I was considering before.  It's also better for some other names I was thinking of:

• Reverse Clobber
• Unclobber
• Backwards Clobber

So, I need to change the name to something different.  Here's what I've brainstormed so far:

• Self-Clobber
• Suicide-Clobber  (too morbid?)

Got any other good ideas?  Got any feelings towards these?  Let me know via email or in the comments.

Final Result: AlphaGo wins 4-1 vs Lee Sedol

AlphaGo won the final game vs Lee Sedol last night.  After Lee won the fourth game, I was really hoping he would also claim the fifth, showing that he'd figured out how to beat the new AI, even after an initial string of losses.

One of AlphaGo's early moves was seen by many as a mistake.  The AI rallied, however, to win the game.

My biggest question now is: how long until a human player can defeat AlphaGo?  By the time a human can, however, there will almost certainly be another machine able to defeat that player.  Perhaps human players will be able to see flaws somehow inherent to the new Go algorithms.  Probably by that time, a new algorithm will be spun off of the MCTS + Deep Learning combo that fixes the flaw.

I know a bit about Arimaa, a game specifically designed to be more difficult for computers to play.  I hoped that perhaps this would be a game where humans still outpaced our AI opponents.  Unfortunately, the computers seem to have overtaken the humans last year.

We had a good run.  Looks like the computers will be in control soon.

Lee Sedol wins Game 4! (1-3 vs AlphaGo)

Lee Sedol took home the victory late last night/early this morning.  He started the game very copying his opening moves from Game 2, expecting AlphaGo to follow suit, which it did.  Lee didn't follow his old moves for very long, however.  From reading some commentary on GoGameGuru, it sounds like he went for a tough all-or-nothing strategy instead of letting the field get divided up into lots of little battles that AlphaGo could weigh and evaluate well. 

Around 78 moves in, he made a move that was really highly regarded by others, and 10 moves later, AlphaGo started making a bunch of moves that onlookers thought were very bad.  Is it because there's an inherent weakness in algorithms that utilize Monte Carlo Tree Search?  Or is it because AlphaGo couldn't properly see the strength in Lee's move at 78?  If that move only works if a few other exact plays get made, then perhaps AlphaGo never tried those paths and didn't see what was coming. 

I am really excited to see that Lee, representing Team Humans, managed to recognize and exploit a weakness in AlphaGo.  Although he might not have another winning strategy to employ in the next game (as he'll be playing as Black instead of White) I still hope he can manage to push out a win.