Gamesters: only Extroverts?

On my trip to BIRS in January, I met a slew of awesome gamesters. Everyone was extremely friendly and I had intense conversations with many different people. Perhaps this is easy when there is a common ice-breaker: "Want to play a game?" People only turned this down when it got late; otherwise they were all eager for the challenge.

Does this mean everyone there was an extrovert? Does combinatorial game theory lend itself more towards extroverts? Will introverts find a hard time breaking into the field?

As I think back to the workshop, I don't recall a single person that came across as shy. There may have been some language barriers, perhaps, but those don't usually cause a problem if both players know the rules to a game. Of course, if you sit down and play quietly, you may never find out whether your opponent is introverted.

I'm somewhat worried that introverts may have a hard time being interested in games and CGT as a result. (There are similar reasons I worry that introverted students aren't getting all the benefits my extroverted students are.) I can see that many people might be intimidated by a class based around something so inherently competitive. Despite the fact that no grades are determined by students' actual ability to play games, I understand the completely irrational fear of not wanting to die in a video game.

Perhaps I needn't worry. Perhaps games and puzzles attract an introverted personality. It is easy to confuse introverts with shy or quiet people; the two do not always go hand in hand.

Wikipedia describes introversion as "a personality trait involving a tendency to drive one's perceptions, actions, thoughts and emotions inside, resulting in reduced interest in activity directed to the outside world." Taking the time to study and consider a game state may induce the same sort of energy as spending time alone for some introverts.

Oh dear, I'm getting into a space I know nothing about. Anyone have any thoughts on this?

Recording games!

On Monday I played some great games of FLex with Ernie and about midway through the first one, I wished we had been recording our experience. We were trying to determine what a good first play looks like, and were testing out playing right smack in the middle. We played 3.5 great games (the last one is on pause in my office until next week's meeting) but took the time to really talk about moves and discuss whether each one looked like a mistake to the other person. Many times we backed up to try another game path. So far, my general feeling is that playing in the middle is a really strong opening move... so you shouldn't do it. With the Pie Rule in place, the second player can choose to take that move from you.

Since Monday, I considered getting a webcam to point at my table to record the games. Then I realized I also want sound (I have an old webcam; does it even work?) so I thought it would be nice to use my phone and upload the videos to YouTube. Unfortunately, I'm not about to hold my phone up for such a long time and I didn't find a stand online that would support it directly above a game board.

So yesterday I got a bit inventive. I brought some wire hangers into the office and spent my lunch (eating and) building this contraption.


(Images courtesy of Patrick Copeland.)

With the wire hangers and some books, I suspended my phone above the game board, then wrangled one of my students into playing a few games with me. We played three games of FLex, one is here, and the end of another is here. The tests went very well and the board is quite visible. I hope to post more videos using this in the future! Many thanks to Patrick for testing this wobbly contraption with me!

Game Description: FLex (Follow-the-Leader Hex)

After talking about Weak Hex (Whex) a few months ago, I tried playing it with some comrades here at Wittenberg. As a reminder, Whex is the version of Hex where both the first and second players must play adjacent to the first player's last move, with the winning condition exactly the same as before. Argimiro Quesada showed that this game is PSPACE-complete on general graphs, without needing to describe what happens if no adjacent move is possible (the graphs in his reduction are designed so that this never happens). When I asked him what the rule should be, he came up with the rule: if you can't play adjacent, then you lose.

This is a common first response for how to deal with this situation. While designing Atropos, I first considered using this same rule: if you can't play adjacent because there are no free spaces, you lose. Luckily, my advisor didn't like this and suggested the jumping: then you can play anywhere. These jumps greatly improve the game, and are also a big part of Adjex (Adjacent Hex).

While first sitting down with some other gamesters to play Whex, we tried the lose-when-no-adjacent-moves-

are-possible option, but found that to be a little unsatisfying. It is most exciting to have the game end when one player has built a path between their sides, not beforehand! We decided to add a jump rule here too.

Handling the jumps was a bit more tricky here, however, since the players have very different roles in Whex. Both players have to move adjacent to only the first player, not to whomever happened to play last. If the first player got to make a jump, then there is little question how to continue play. But what should you do if the second player gets to make the jump? Can they play anywhere they want? If so, are there any restrictions on where the first player goes afterwards? Can they play wherever they want, or do they have to play adjacent to where the second player just moved?

We came up with a nice solution for this case: switch the roles of the players. If the second player gets to jump, then they become the player who both have to play adjacent to instead of the first player.

Here are some more descriptive rules for the game, which we call Follow-the-Leader Hex (FLex):

This game is just like Hex, except at any time one player is the Leader and one is the Follower. On your turn, if possible you must play adjacent to the hexagon painted on the Leader's last move. If none are available, you may play on any unpainted hexagons on the board, and then you become the Leader, while your opponent becomes the Follower.

This game plays very nicely. In the first two games played between myself and Ernie, I won the first one without losing the "Leader" status, then won the second one starting as the Follower, fighting to become the Leader, getting the jump (and becoming the Leader) and using that to win. Having said that, in other games, we have seen the Follower force a win, so it's not clear which role is better. In fact, lately Ernie has had great insight into this game and playing as the Follower, who appears to have some advantage! Most of the games we play nowadays are determined by which player can get a jump first.

While playing, it is vital to use the Pie Rule to avoid a very simple immediate win (see this post on Whex). Unlike regular Hex, in FLex it may be more clear whether the second player should invoke the Pie Rule to win... maybe.

The credit for this game is really due to Argimiro; FLex is a minor tweak on Whex for a situation he had not previously considered. The tweak is due to Ernie, Obed and myself.

Enjoy! I am especially interested in hearing comparisons between Adjex and FLex. Which is more fun to play?

Combinatorial Games: a first-year class

The past few months I have been working on some basic planning for teaching combinatorial games as a first-year college class. At Wittenberg, we have "WittSem" courses; each incoming freshman must take one. This is finally really coming together, so I will likely teach this course in the fall. Woohoo!

This is a bit of a tricky task. Last semester my course started off as too difficult because we were using a graduate-level math text and I didn't convert the book problems enough for the students. (Not to mention I was learning some of the material only slightly before teaching it.) My next batch of students will have less math background so I'm going to have to be even more careful. I will probably rely more heavily on worksheets and less on the book problems, though Lessons in Play will continue to be an excellent reference for the class.

I still plan on devoting one day per week to playing games and discovering outcome classes/values for different states. Each week we'll try to add some new evaluation tools and I'll look for great game examples of those tools.

All in all, the class will likely look a bit like the last, but without emphasis on proofs and programming. This last bit will be replaced by some discussion of cultural aspects of games throughout history. This is definitely a bigger task than I had last semester, but I'm already looking forward to it!

Once the semester starts, I'll link to the class page. Of course, if you are an incoming Wittenberg student and have any questions about how you can be allowed to play board games during class, please ask me!

PSPACE problems versus NP problems

I've recently been paying attention to community theoretical computer science forums, including on sites such as StackExchange. This question recently came up:

Are PSPACE-complete problems inherently less tractable than NP-complete problems?

Naturally, since we don't know whether PSPACE is not equal to NP, there is not yet a formal answer to this question. Intuitively, however, this becomes a question of whether it is harder to figure out which player can win a game than to find the solution to a (one-player) puzzle. The link above provides a wonderful bunch of points, but let me mention a few specifically. :)

* Ryan Williams notes that some randomized game tree solvers are very effective, and perhaps solving games isn't quite as terrifying as many might think.

* Neil de Beaudrap notes that verifying solutions is still extremely important, which we know how to do for NP-complete problems. Aaron Sterling backs this up with a great comment about humans being able to remember and describe proofs.

* Lance Fortnow points out that we know how to create average-case PSPACE-complete problems, but don't yet know how to do this for NP.

* Suresh Venkat mentions that in practice, NP-solvers are actually often very fast, and NP-completeness is not always seen as a barrier to computing.

This is one of the few questions on the forum that I have actually read multiple answers to, and it's one I feel I can read over and over. Personally, I find it hard to believe that PSPACE isn't much harder than NP, and professionally I'm partly banking on it by spending my time finding PSPACE-complete games!

No posts this week, and slimming down for a bit

Sorry to my readers (all seven of you, perhaps?) but I haven't had time to post this week due to some extra responsibilities. With doctor's appointments for pre-birth checkups increasing, I can already see I will need to slim down for the rest of the semester.

Next week and for the rest of the spring, I will be posting once per week.

Have a great weekend!

Game Description: Col

Col is another "classic" game that was first deeply analyzed by John H. Conway. It is a game that is inherently a graph game, but is often played on a whole piece of paper divided up into regions by drawn shapes. Each turn, a player chooses a blank region and paints it their own color. You may not choose a region that is adjacent to any other regions of the same color. (You can see some turns of the game in this very descriptive wikipedia page.) I'm sure whenever my future children are learning to draw in the lines, I'll try to coax a few games of Col out of them.

Col has an amazing, but beautiful property for evaluation: each position has a value equal to either a number or a number plus star. No Ups, Downs, *k's (for k > 1), etc. The elegant proof is based completely on the simplicity of the game value, showing that all left options are less-than-or-equal-to all right options for any game. With this Col fact, you can inductively assert that game values of the form {x | x + *} cannot exist (when x is a number). The only remaining options are numbers and numbers plus a star. Check out pages 47 and 48 of Winning Ways for all the details.

I was recently asked whether I knew the computational complexity of Col. I don't know that this analysis exists, but it could be that it is not computationally hard since the different game values have the nice property above. So far I don't know of any relationship between game value ranges and computational complexity (aside from impartial games with only values of 0 and *---those are solvable in Polynomial-Time because you never have a choice on your turn).