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.

Monday, January 2, 2017

CGT Facebook group

Simon Rubinstein-Salzedo started a Combinatorial Game Theory Facebook group!  Join us here: https://www.facebook.com/groups/413534538978745/

Happy New Year!

Friday, December 30, 2016

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!

Thursday, December 1, 2016

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.

Friday, September 30, 2016

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!