Thursday, March 24, 2016

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.

Monday, March 21, 2016

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.

Tuesday, March 15, 2016

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.

Sunday, March 13, 2016

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.

Saturday, March 12, 2016

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.

Friday, March 11, 2016

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!