All I want for Christmas is Tweets

In 2016, I joined the technology era of 2006 by getting myself a Wii and now a Twitter account.  Hooray!

This summer, I promised myself that I would sign up for Twitter after I submitted my tenure portfolio.  Well, I turned that all in back in October, so this is overdue.  Here's my Twitter-Sphere Presence: CGTKyle

I find myself noticing CGT things that don't quite warrant an entire blog post.  Then I forget about those things.  Now I can quickly say something about them in an attempt to garner attention.

I expect that I'll also be tweeting about general board games, teaching, voting systems, CS and math, and more.  Yikes.

My first tweet announced a little page I made for CGT events: http://turing.plymouth.edu/~kgb1013/CGTMeetings.php  I realized that I always needed the links to these previous and coming events.  As is common for me, I coded the whole thing up in Javascript (feel free to look at the underlying code) so events like CGTC II is currently in the "Future" section, but should move to "Past" after it's happened.  We'll see whether I did that right.  (Also, you should all be going to CGTC2!  I'm very disappointed that I'll be missing it.)

I think I'm missing some meetings on there (there was something at Kamloops a few years back, I believe) so help me fill it out.  I hope there's something coming up this summer also (I think Games at Dal will have to wait until 2018.)

Happy New Year!

LaTeXing Lecture Notes

I've been working hard the past 2.5 years teaching a bunch of new courses and improving old courses.  One of the things that's helped a ton is converting hand-written lecture notes into LaTeX. 

Many years ago, I started working on a style file to add a bunch of commands for lecture notes.  Most important, I created a question command to facilitate Socratic-style lectures.  I later modified this so that I could set a flag indicating that the output was for students.  Then it would hide the answers to those questions.  I started posting these versions online for students.

I've been adding stuff to this, but recently really wished I could add exercises that would put all the answers in an appendix, but hide those answers in the student version.  I recently discovered the exercise package (thanks, Stack Exchange) which can do this automatically.  Using that, I updated my style file, and recently posted the code on GitHub.  (If you're not familiar with GitHub, I made my own landing page.)

I find that it's really convenient to teach from the pdfs on a tablet, and it saves me tons of paper.  The only issue is that it's a bit more difficult to make notes on the pdfs than with a regular pen and paper.

Richard Guy is 100

Happy Birthday, Richard Guy!

Richard Guy turns 100 today.  He is one of the authors of the classic text Winning Ways for your Mathematical Plays.  At the CGT workshop at BIRS in 2011, he proposed a new subtraction game that I find myself thinking about on and off:

Given a pile of n tokens, and a subtraction set, S, each turn, you move to a new position, n (< n'), S', where either:

• Normal thing: S = S' and n' = n - s, for some s in S or,
• Weird thing: S' = { x } U S and n' = n - x and there are some y and z in S such that x = y + z.

...I haven't gotten anywhere with it either.

I was alerted to an excellent birthday video for Richard, highlighting his work in Geometry.

Richard is one of the nicest people I've ever met, and he continues to be active in research today!

Integers 2016

Integers is back!

Integers is a conference in combinatorial number theory.  Traditionally it's been held every other year on the odd years, but it had to be skipped last year.  Integers is a great, low-key conference held at the University of West Georgia.  It has an associated electronic journal with no paywalls (so convenient!).  It's well run and everyone is very nice.  This year, they've moved it up to early October (6th-9th).  Here's the official Integers 2016 announcement.

Historically, there's been a contingent of gamesters attending Integers.  In 2011, I brought an undergraduate and met many of Richard Nowakowski's students.  In 2013, I met Silvia Heubach and Matthieu Dufour.

Unfortunately, I don't know of anyone attending Integers this time around.  This is partly due to the number of CGT events popping up.  Games@Dal has returned, and CGTC2 will be happening in January 2017 in Lisbon.

If you're planning to go for Combinatorial Games, please comment below (or email me).  At this point, it looks like we might not have any gamester attendees.

Games@Dal 2016: Tanya talks about Cookie Monster Games

Games@Dal 2016 talk: "Cookie Monster Plays Games" - Tanya Khosanova w/Leigh Marie Braswell, Eric Nie, Alok Puranik, Joshua Ziong, and Dhroova Aiylam

Tanya Khovanova shared some work with a bunch of high schoolers (whoa!) on patterns in Cookie Monster games.  Cookie Monster games are Nim games where k sticks (cookies) can be removed from multiple heaps.  Each ruleset has a different restriction on which sets of piles can be removed from.

She and her students considered rulesets where you can take from...:

• No restriction
• One-or-all piles
• One-or-two piles
• Any consecutive piles (assuming the piles are in a list)
• One or two consecutive piles
• Any set of piles including the first jar
• Any odd number of piles.  (It turns out that the P positions are the same as in Nim!)
• Any set of piles except all of them.
• ... and more!

In one of these games, she noticed a surprising correlation with an automaton problem!  A sequence of the number of P positions is related to the number of new cells born from the Ulam-Warburton automaton.  She then looked more closely at other relationships to automaton!

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!

Games@Dal 2016: Alda and Carlos talk about Short Sums

Games@Dal 2016 talk: "Some notes on Disjunctive Short Sum" - Alda Carvalho & Carlos Santos

Alda and Carlos presented their work on Disjunctive Short sums.  They started from Paul Ottaway's definition of the difference from a short sum (to a normal long sum): The game ends when a player chooses a component in which they have no legal move.  This doesn't make a difference in Normal play (because players don't want to choose one of those games) but it's important for Misere.  In misere, this is equivalent to: The game ends when there is a component in which the current player has no legal move.

Now, instead of starting from zero as the terminal position, they start with two games that have no options: Infinity (Inf) and negative Infinity (-Inf).  Inf is the game with no options for Right, and -Inf has no moves for Left.  These are the only games born on day 0.  Then the day 1 games are:

• Inf* = {Inf | Inf}
• +/- Inf = {Inf | -Inf}  (like a switch)
• 0 = {-Inf | Inf}
• -Inf* = {-Inf | -Inf}

They showed a bunch of the birthday lattice for day 2, which is very large, then started talking about Color Nim: a short disjunctive sum of Nim games.  Another way to say this is that each pile has a color (not necessarily unique) and the game ends when one of the colors is gone.  In the Misere case, this means that each color behaves like Penultimate Nim.  (For some reason, Penultimate Nim kept coming up at this meeting!)

Games @ Dal 2016 Wrap Up

Yesterday morning, I put myself and three other Muppets back into my car and departed Games @ Dal.  675 miles, 16 hours (just under 12:45 actually behind the wheel) and three drop-offs later, and I was back at home. 

There are still more talk summaries to come over the next few days, don't worry.  We even had an unexpected bonus talk by Tanya Khovanova on Friday, so there are three more to go! :)

Here's a few things I learned:

• I got a result!  It's not about the computational complexity of a game... who am I?
• There are lots of very obvious rulesets that we still need to find the computational complexity for.  Even just impartializations or other variations of common rulesets need to be figured out.
• Halifax Citadel's noon gun is loud if you're standing near the citadel entrance.  (Good choice, Amie!)
• Hanabi is pronounced differently in Canada.
• CGT is still a really good field to introduce to mathy undergrads.  (Also, I should really take a look at Tom Ferguson's book.) 
• It would be very nice to have a list of gamesters.  I should probably make this.
• It would be very nice to have a list of past and future CGT conferences/events.  I should probably make this.
• I should spend more time working on the ruleset table.
• I would really like to go to a workshop where my only job is to update the table.  I'd like this to be a CGT event because I'd like to be surrounded by Gamesters while doing it. 
• A post on the Gamester Pen would not be worthless.
• I should probably get on Twitter and tweet little things like these.

Thanks to Richard Nowkowski, AARMS, and Dalhousie for hosting such a great event!

Games@Dal 2016: Israel talks about Picaria

Games@Dal 2016 talk: "Eternal Picaria" - Israel Rocha w/Urban Larsson

Israel Rocha presented a new game to me: Picaria.  Picaria is a traditional board game of the Zuni tribe from the American southwest, but it also pops up in other parts of the world, including southwest Sweden (known there as a type of Luffarshack).  It plays a bit like a Three Mens Morris mixed with Tic-Tac-Toe.

Players play on a graph, usually set up in a 3x3 grid like Tic-Tac-Toe, but with diagonal connections as well.  In the first six turns, players are playing pieces, trying to make three-in-a-row.  After those pieces are played, players instead slide pieces to an adjacent location, still trying to make a line of three.

Israel explained that he and Urban Larsson showed that Picaria is a draw, via exhaustive search. (And without a computer!)  They then considered some variants, including giving a player more stones and playing on bigger boards.

Games@Dal 2016: Carlos talks about 3-player Nim

Games@Dal 2016 talk: "3-player Nim with podium rule" - Carlos Santos w/Richard J. Nowakowski and Alexandre M. Silva

Carlos's talk entered the somewhat-forbidden world of three-player games.  He spoke of different ways of considering these games, but continued using Lee's Podium Rule from 1978: If you can't come in first, you should instead try to come in second.  (Try to get as high up the podium as you can.)

In impartial games, this leads to a third outcome class: O ("Other") which has no P options, but at least one N option.  Playing on Nim heaps, to find P positions, we now have to perform the nim sum, but mod 3 instead of mod 2.  Thus, *7 + *17 + *22 + *23 is a P position.  Zeroness in the sum only actually tells us about P positions; non-zero values might be O or N, so we need further criteria.

Carlos described these further criteria, then continued by describing how to define canonical forms for Nim.

Games@Dal 2016: Craig talks about PenFib Nim

Games@Dal 2016 talk: "Penultimate Nim and Conjoined Games" - Craig Tennenhouse, w/ Kelsey Mihachik

Craig talked about Conjoined Games, another type of "sum" extending the notion of sequential sums.  The sequential sum of G and H works that both players must play as normal on G until the game ends, at which point the next player makes a move on H.  Conjoined Games are special in that the second summand (H) is not defined until G ends; H is based on the state terminal position from G.  The nicest games to play are those where the state of the terminal position is exactly the state of H.  Craig suggested Colobber: Col followed by Clobber.

Craig then described Penultimate Nim (AKA Gale's Nim), which is just like Nim except that there are no moves when there's only one heap.  Pen(ultimate) Nim is solved for all games with 3 or less heaps.  He then showed Fibonacci Nim: a single-heap subtraction game with the following rules:

* For the first turn, the first player may take any number of sticks aside from the entire heap.
* On any subsequent turn, the current player may take any sticks up to twice the amount the previous player took.

Craig then presented PenFib Nim, which is Penultimate Nim followed by Fibonacci Nim.  He's working on trying to categorize the P-positions.  

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.

AlphaGo 3-0 (vs Lee Sedol)

AlphaGo sealed the match against Lee Sedol with a third straight win.  Wow.  YouTube link to the game. 

Is this the end of humans competing with computers in Go?  Not exactly.  I just read a great reddit post about Chess after Garry Kasparov vs. Deep Blue in 1997.   Humans certainly didn't give up and only six years later, Kasparov drew against a more powerful Deep Junior.

I expect that humans will get more used to playing computer opponents and perhaps tip the scales back.  As more games with strong computer players are played, the new strategies can be studied and humans can adapt to them.

It'll be interesting to see how that plays out.  The next two games between AlphaGo and Lee might be indicative of how quickly humans can adapt to the new Go gamescape.

SmartGo article: AlphaGo Don't Care

Bob Hearn shared this wonderful article on smartgo.com by Anders Kierulf: AlphaGo don't care. 

I loved this piece, mostly because it really hits on an important aspect of the theoretical study of combinatorial games.  There is a real "psychology" aspect to a lot of the strategies.  I am not familiar with the Go terminology of the different move/structure types in the article (e.g. "tenuki", "extend at the bottom", and "peep").  These are human ways to describe different strategies and patterns. 

As the article reiterates: "AlphaGo don't care."  It doesn't lose universal focus to get stuck in local duels.  Each turn, it reevaluates the gameboard as a whole.  It doesn't care about the order of the previous plays, data that doesn't change the outcome of the game.

The same is true in CGT.  The options from a position depend only on the information of that position, not the history of plays nor the psychological battle between the two players.  The value of the game is irrelevant (though it may be very hard to calculate exactly).

From the article:

Lee Sedol threatens the territory at the top with 166? AlphaGo don’t care, it just secures points in the center instead. Points are points, it doesn’t matter where on the board they are.

It doesn't matter that Lee Sedol last moved near the top, AlphaGo just goes wherever it thinks it can amass the most points, not where it thinks the other player is going to focus their efforts.  The actual temperature of the regions is more important than which pieces were the most recent plays.

The third game is tonight!

AlphaGo 2-0 (vs Lee Sedol)

AlphaGo defeated Lee Sedol again last night.  BBC has a nice story about the game.  It looks like AlphaGo's moves in this game were a bit less shocking to the 9-dan champion Lee.  My second-hand perspective on this is a bit dire; I'll admit that I'm rooting for humanity here.  If Lee has a hard time reviewing this game and figuring out where he might have made some grand mistakes, the likelihood of improvement in the next two days (before the next game) is low.  Unless he can spot a weakness in AlphaGo's play, the Holy Grail of Go might fall.

YouTube has a video of the second game.

Good luck to Lee in the next game!

AlphaGo 1-0 (AlphaGo vs Lee Sedol)

Last night, the computer program AlphaGo defeated professional 9-dan Go player Lee Sedol in the first game of a five-game match.  This is the first time a computer player has defeated a 9-dan player without a handicap.  The second game occurs tonight.  YouTube has the video of the first game and Wikipedia has a good article for the entire 5-game challenge.

This match is highly anticipated after AlphaGo defeated 2-dan Fan Hui back in October.  That was the first time a computer defeated a professional Go player on a full sized (19 x 19) board.  It was at this point that it became clear that AlphaGo had a chance against even the strongest human opponent.  The hype was set for the challenge with Lee Sedol.  The New York Times published a good article in the aftermath of the victory over Fan Hui.  They brought in some experts (including my colleague Bob Hearn) to explain better how AlphaGo works.

AlphaGo uses a combination of Monte Carlo Tree Search (MCTS) algorithms and newer Deep Learning techniques to win.  The MCTS algorithms have been around for about a decade or so, and brought about the first victories by computer players on 9x9 boards.  The basic idea behind this is that it randomly plays a bunch of complete games to their end, using the win/loss result of the last game to decide which game to explore next.  By playing a few thousand games and intelligently choosing which game to try next, the search can help narrow down which move to make.

Deep Learning comes in to play in two ways in AlphaGo.  First, it can approximate the win/loss value of each game early enough that the entire thing doesn't need to be played out.  (This may sound like a bad idea, but the game played by a pure MCTS algorithm is an approximation anyways, as the later moves are chosen completely at random.)  Second, it helps choose which of the games to simulate.  I don't know enough about deep learning (yet) to better describe the details of how it solves each of these problems.

This match is very reminiscent of Garry Kasparov's loss against Deep Blue in 1997.  That was the first time the reigning human world Chess champion lost to a computer.  At that time, Go was still unreachable by computer players, a Holy Grail that would require stronger computers and more sophisticated algorithms to attain.  After AlphaGo's win yesterday, perhaps the Grail will be captured soon.

As Bob Hearn points out in the NYT article:

Go was the last bastion of human superiority at what’s historically been viewed as quintessentially intellectual. This is it. We’re out of games now. This is seen by some as a harbinger of the approaching singularity.

I'm very anxious to see what happens over the course of the next week!

Update: post about the second game.

2016 Portuguese CG Tournaments

Yesterday, Ludus ran the annual Math Games tournament for elementary, middle, and high school students.

Here's the English version of the site with lots of pictures: http://www.di.fc.ul.pt/~jpn/cnjm12/  (I'm only familiar with two of the games they played.)

Swiss Museum of Games

Planning a trip to Switzerland soon?  If you're on Lake Geneva near Montreux, you might be surprised to find a museum dedicated to board games!  The Swiss Museum of Games (Musee Suisse de Jeu) occupies a castle directly on the lake and it looks like they have great exhibits and activities!

I hope someday I can get over there and check things out first-hand.  It looks like right now they're doing a cool exhibition on Mahjong that ends this month.  Their permanent collection has a potpourri of games from many different cultures.