Friday, February 3, 2012
Game Sum Demonstration Videos
Here are the links to videos:
Domineering + Clobber [6:32]
Domineering + Checkers (Draughts) [5:24] (Warning: this one is unsatisfying!)
Domineering + NoGo [4:14]
Y + NoGo [7:32] (Using the non-all-small Y)
Hex + NoGo [4:27] (Using the non-all-small Hex)
Hex + Clobber [13:16] (Using the all-small Hex!)
Tuesday, January 31, 2012
Clearly Combinatorializing Connection Games: Un-all-smalling
Unfortunately, some games add poorly or uninterestingly. Hex may be a good example, because the game is over when a path is created. The standard Hex rules cause the game to be all-small: if one player has a move option, then the other also does. As I mentioned before (late in the post) it's perhaps more exciting to redefine the game to make it more "sum-friendly" (very arguable). Instead of ending the game when one player has created a path, instead allow the path-creating player to keep painting uncolored hexagons. Thus, the rule is that you cannot play if the opposing color has formed a path. Now the game is no longer all-small.
Paul Ottaway and I had a conversation a year ago where we both argued for this change. I don't know how to change the rules to a 65-year old game, however. Luckily, when played atomically (not part of a sum), the new rules do not change the game play. Make the connecting path and you win.
This works for any connection game that I know of (Y, Twixt, etc). There are many inherently all-small games that cannot accommodate such a change, however. Clobber and MadRooks are games that are all-small and for which I don't see a method to fix that that doesn't change the original game.
The inherent problem here is that prior to combinatorial game theory, games were defined by explaining the conditions for one player to win the game. Under the normal play convention, that's not entirely relevant. Instead, the game author need only describe what the legal plays are for each player from any position. It's a subtle difference that is only important in the context of game sums.
Thursday, October 27, 2011
Integers liveblogging: Thursday
Today a lot happened. I talked and I listened to lots of games talks, many of which will become their own posts in the future. Instead, I'll quickly mention some highlights thus far.
Rebecca confused me yesterday by saying "in P" which I automatically translated as "efficiently solvable" instead of "in Zero". I had just met her, so I asked excitedly if she was in computer science. She said this misconception is even more dangerous because she is dealing with misere games, and need to consider both outcome classes. Those in Fuzzy when playing misere, but in Zero under normal play are in N-,P+, pronounced "NP" (which computational complexity theorists use for another well-studied complexity class). Dangerous!
I've also seen a great bunch of non-games talks, mostly number theory, which I've understood a bit of. Particularly, Carl Pomerance gave a talk I understood most of about product free subsets of the Naturals (if x and y are in S, then x*y is not in S... usually x*y (mod p)). Neil Hindman gave an impressive talk, mostly because I don't think he looked at any notes and covered a lot of complex stuff using only a whiteboard! I also found out yesterday that Beatty sequences/ratios were used to help discover quasicrystals, something which had a lot to do with this year's Nobel Prize! Wow!
I've mostly had a blast meeting people and playing games. While playing FLex with Marla yesterday, she commented, "This is all very important!" Everything I explained about what I was thinking was quickly absorbed by her and Rebecca. Awesome!
Meeting people---especially over games---is great! I played some impartial games with Yuval Tanny and Shira Giat. At one point I made a winning move, but was afraid I hadn't gotten the parity correct. Neil put me to ease, saying, "Yes, you counted to two correctly." That's about as high as I feel I can count these days.
Yuval and Shira are clearly awesome; this seems to be the norm for gamesters! There's a lot of energy in the group---all positive---especially from Jess Enright, who gave an awesome talk today about set representation games. Here is a picture of her realizing she won a game with Marla during the talk.
I feel like a bit of a reporter, trying to keep up with everything, but it's very helpful to help me stay on point in the talks. Seriously, they were great and I can't wait to get some of those posts up.
I will try to get a post up tomorrow before the evening, but if not, I'll put in my final fake-liveblog next week. I'm leaving on Saturday morning, so I won't be around for the last day of the conference, sadly.
Friday, September 16, 2011
Shifting Connection games
This really changes the game! You can see one point where I was about to lose because I hadn't anticipated the power of the shift. Ernie was nice enough to let me go back... :-D
Nick suggested another game to play, and then another reader, Marcos, suggested his own game. I guess Ernie and I have plenty on our plate! :)
I'm really interested in playing the shift version of Hex. Or the shift version of Adjex! Is there some ruleset to combine this with an adjacency restriction?
Thursday, September 8, 2011
Messing with Y
This game plays similarly to hex, except that there are, like, 1.5 sub hex games going on at the same time. Ernie has taken a quick liking to this game; he's very good at beating me before I know I'm beaten! To escape this dilemma, I proposed that we give this the same treatment we gave to Hex: let's force adjacent play. We spent a bunch of time trying out different starting positions, and unfortunately it always seemed that the first player to move had a strategic advantage, even if that first play was on different ends of the board (or smack in the center, of course). This means the second player always wants to evoke the pie rule. Earlier this week, we sat down for a few games and taped them. Our first game has Ernie starting in the center. Spoiler alert: he manages to get to all sides, but the game is quite close!
In the next two games, we try instead from the middle of one of the sides. These are both great games! We are already getting a handle on how this game works.
I'm not sure, however, that I like this as much as Adjacent Hex. Of course, I've gotten more interested in FLex (Follow-the-Leader Hex) so perhaps it's time for a game of FLY!
Does anyone have a story to share about trying out an "adjacent-enforced" version of another game?
Friday, April 22, 2011
Recording games!
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!
Friday, April 15, 2011
Game Description: FLex (Follow-the-Leader Hex)
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-
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.
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?
Friday, February 18, 2011
Game Description: Weak Hex (Whex)
Here is the description from the original Whex paper by Argimiro A. Arratia Quesada:
Players can not colour an arbitrary vertex but must proceed as follows: Player(If no adjacent moves are available, the next player immediately loses.)
1 begins the game and he must do it by colouring red a vertex adjacent to
the source. From this move and on, Player 2 must colour blue an uncoloured
vertex adjacent to the vertex last coloured red (i.e. coloured by Player 1), and
Player 1 replies by colouring red an uncoloured vertex adjacent to the vertex
that he coloured red last.
This game is intended for play on a graph instead of the standard hex board, but we can consider that also. In this case, the "source" is likely to be an entire red side (the sink, then, is the other red side). The goal for the red player is to connect the two red sides, and the goal for the blue player is to prevent such a connection. This matches up precisely with the winning conditions of standard Hex, so it is possible to play Whex on the regular hexagonal grid.
Additionally, the game is shown to be PSPACE-complete, so it is certainly hard to play in the general case! This is the same as with Hex and Adjex. In Hex, it is known that the first player has a winning strategy, but that strategy itself is not known. In Whex, however, not only does the first player have a winning strategy, but it can be described very quickly! In fact, I bet you can come up with it yourself!
(Find an opponent, see if you can come up with a method to always win playing first (as red), then come back and finish reading!)
Okay, on your first turn, play in the hexagon "on the bottom"

On each subsequent turn, play in one of the hexagons directly towards the upper-right-hand (red) side. Blue can only choose to occupy (at most) one of those on their turn, so you will get to take the other. Since you don't have to worry about playing adjacent to them, they can't deter you (as is possible in Adjex). Enjoy your march to victory!
If you play with the pie rule, I'm not sure what happens!
Friday, January 28, 2011
Game Description: Adjacent Hex
The game is exactly like standard Hex, except it mimics the play restrictions like Atropos: after an opponent paints a hexagon their color, you must play adjacent to their last move. If all the adjacent hexagons are already colored, you may choose to play in any uncolored hexagon on the board. (We've been referring to this as a "jump".)
Ryan and I played one game with these rules. At one point, I thought I was doomed, but Ryan pointed out a really good move for me. I can't recall whether that move led me to win, but either way it was clear his Hex skills were helping out. We proceeded to play two other games using different rules for jumping, but both agreed the original game was best.
Since returning to Wittenberg, I am undefeated. (My aide, Ernie, would like to add: "So far.") I've played against a number of students, and even beat the combined talents of my aide and teaching assistant, Patrick, earlier this week. Obed, the director of our math resource center, has vowed to get a set to practice with his own students.
This game plays very nicely: knowledge of Hex will help out, though knowing that playing in one hexagon will win you the game doesn't always help if your opponent never plays adjacent to that spot. In most of the games I've played, players are usually fighting to be the one working on their own path, which is sometimes harder than it sounds. Usually one player is currently working on a path, while the other player is just trying to derail that path using the adjacency rule. If their derailing is successful (this can be quite tricky) then that player starts building a path fragment and the other player is now trying to thwart that plan.
Sometimes play moves into an area that is closed off where the color of the hexagons does not matter. Now both players are competing to force their opponent to paint the last hexagon in the region, ensuring that they will be the one to "get the jump" and play wherever they want. A few times I've been in great situations where I decided not to connect two of my important paths because doing so would give my opponent a jump. This is a tough choice!
In my office, I have a 14 x 14 hex board, just ready for adjacent-minded opponents!
Friday, January 15, 2010
Bonus-play Hex
Alternatively, we could define Either-Color-Hex, which allows a player to paint either red or blue on their turn, but you still only win if a path uses your color. That doesn't change much of anything from standard Hex (why play the other person's color instead of your own?). Now, however, Misere Either-Color-Hex has similar strategies to regular Hex; you're always going to try to create a bridge with the other player's color.
... depending on how you define "winning" and "losing". It seems like we'd like to say that in Hex, you win if you complete your path. However, as we've covered before on this blog, we define this by describing when no further moves are available. Then, under Normal play, you lose if you cannot play on your turn. With Misere play, the opposite is true: you win if you cannot play on your turn. Hex games are "over" when a connecting path is created. Thus, you create your path and now the other player cannot make a move.
Unfortunately, now Either-Color-Hex doesn't work as anticipated. If the Left (Blue) player is about to complete a blue path, the Red (Right) player can color the last open hex blue to complete it. Then a path is complete and Right wins, despite the fact that the path was blue. That doesn't work as expected! (In fact, this game is now an impartial game, which isn't what was expected either.)
Misere Hex still works pretty correctly. Instead of trying to avoid creating a path in your color, you try to avoid creating a path of either color. However, since you can't play opposing pieces, their path will never end the game against your favor. Misere Either-Color-Hex, though, just has the same problem as Either-Color-Hex: both players will avoid creating a path of any color.
Let's see if we can fix this by changing the rules slightly. Instead of ending a game when a path is created, let's rule that a player cannot make a move when a path of the opposing color exists.
Now the Either-Color version of this game works just fine. Right can play the blue hexagon if they want, but the blue path "belongs" to Left. Left will continue to be able to make plays on the board, but Right will not. On their next turn, Left will paint a hexagon and then Right will have no more legal moves. Left wins.
Now the Misere Either-Color version does something strange: players are actively trying to create a path in only the opposing color. Once that is complete, the opponent will have another turn, but you won't have any. This works almost the same as standard Hex, but with the player roles switched! (The exception is on the last move. If Left makes the last hexagon and completes the red path, they won't be able to make any more moves. Unfortunately, since there are no more hexagons, Right wins anyways.)
This Bonus-play Hex has another nice property. When adding with other combinatorial games, it offers a bunch of extra free moves to the player who completes their path. If the board is mostly empty, the winner can keep making moves on that board later on in the game sum. This gives the Hex summand more priority: the winner will be able to use those extra plays later.
I should print out a board for Hex!
Have a great weekend, everyone!
Friday, October 30, 2009
Misere Hardness
Early on, I asked them to include both nim and misere nim. As with all misere games, misere nim is the same game, except that the person who makes the last move loses. Thame Plambeck used to maintain Advances in Losing, a blog solely about misere games. My first combinatorial game, Atropos, was misere: the first player to create a 3-colored simplex (triangle) loses. The misere notion is very intuitive for many games.
As we continue with the ongoing class project, I have continued to add difficult parts but at some point I stopped asking them to add more games to the suite. Oops! Currently, I've given them another tricky task: have users make moves through a series of mouse clicks (instead of entering choices in text boxes). I figured it was time to throw in some new games along with that. At the same time, I hope they realize they can apply "misereness" with any games, and not just with Nim.
Solution? They've already programmed a simple version of Kayles and Hex, so why not include misere Kayles and misere Hex? Even after thinking about that, I became immediately interested in misere Hex. How does that game work? Whichever player first creates their bridge between both sides loses? Weird! Who wins misere Hex? What is the complexity of this game?
In 1999, Jeffrey Lagarias and Daniel Sleator tackled that first question. They find the immediate intuition---that the first player never has a winning strategy---incorrect and instead base the winnability on the parity of the board size. They do this by showing that the losing player can stretch out the game play until the final hexagon has been colored. Thus, on boards with an even number of hexagons, the first player can win! The proof they give applies to games starting from the initial (empty) game configuration.
Does this answer the complexity question? Not in any obvious way. In order for the complexity to be solved, an algorithm would have to work for any game state. One can invoke a board where the game cannot be dragged out to fill in all the cells. (Give red two nearly-complete paths with only one hex missing, and let the rest of the board be filled in. If it's red's turn, what can they do?) It could be that the proof generalizes well into an algorithm.
Thinking from the complexity angle, as this blog (too?) often does, is there anything we can say about the relationship between the complexity of a game and it's misere counterpart? Again, I am interested in considering Atropos, which is already misere. The non-misere version means that the first player to create a 3-colored triangle wins. In this impartial game, each player may choose to color one circle any of the three available colors. The circles are laid out similarly to hex---so that each has six neighbors---inside a triangle with borders colored to suffice for Sperner's Lemma. This means that any play along the borders can win: there are always two different neighboring colors, so simply paint that circle with the remaining color.
Thus, the strategy from the initial position is easy. Choose one of those bordering circles and paint it the third color. Game over. In mid-game positions, however, a player must choose to paint a circle that neighbors the last-painted circle (if an open circle exists). Thus, the game might not be quite as simple from any given situation; one of the border circles may not be adjacent to the last play. (But why wouldn't the first player have just won the game? Why would you ever get to this situation?)
In general, are there any results about misere games and complexity? It's been a while since we phrased a question, so let's do it: (I've been marking the relevant posts with question# labels).
Question (2): Given a game G and it's misere version, M, must the complexity of determining the winner of one of these games be in P?
I think this is the best way to phrase the "What is the relationship between the complexity of G and M?" question. Consider nim and misere nim: both are easy. With Hex and Atropos, each has a PSPACE-complete version, but the opposite looks like it might be easy. Is there a game I'm overlooking which is hard both normally and misere...ishly? (someone help me out with French!)
Of course, I'm still curious about misere Hex.
Question (3): What is the complexity of determining whether the current player in misere Hex has a winning strategy?
For those interested, user Zickzack at boardgamegeek.com has a good description and list of misere games.
Friday, October 16, 2009
Complexity of Games with Randomness
I'm also interested in trying to analyze some games by removing their sources of randomness. Instead of relying on die rolls, for example, give each player the set of potential die rolls and let them choose one at a time, then removing that "roll" from their set of available moves. Once all options are chosen, either the player has no more moves or they get a new set of false rolls. I don't know of any analytical results like this, but I would love to see them!
On the other hand, I also have some interest in answering complexity questions of games that include randomness. For example: What is the probability that the current player has a winning strategy? Alternatively, rephrasing as a decision question, does the current player have a strategy that will allow them to win with probability > .5?
I don't know of any results like this. Do they exist?
Wednesday, October 14, 2009
Programming Hex
Two weeks ago I assigned my software engineering students a new project: they were to add Hex to their collection of combinatorial games. To this point they had only implemented impartial games; this was to be a bit of a wrench in the mix.
Unfortunately, I picked a poor partisan game. Hex itself is an excellent game, but I forgot that it was a bit difficult to determine whether the game is over. The obvious approach to determine this comes down to graph connectivity, something beyond the scope of the project. Oops!
Luckily, I quickly recalled the proof of the Hex Theorem: when all hexes are colored, there will be exactly one winner of the game. The late David Gale does an excellent job of describing the theorem in this paper, showing the link between Hex and Brouwer's Fixed-Point theorem. I explained to the students that they should follow the boundaries from one of the corners of the board and see which corner it ends up at. For example, if they choose a corner where the blue side is on the left and red on the right, they can hug either the blue or red boundary (this might be the same if most of the board is colored).
First note that this path created by the boundary cannot end; it will exit through one of the other board corners. Note next that it cannot exit through the corner exactly opposite; the colors there are on the opposite sides! Thus, the path will veer either right or left (from the point of view of the entering corner). If, like we said, blue is on the left and red the right and while hugging the blue boundary we exit to the left, it means blue has not yet won the game. If, on the other hand, the path exits to the right, then there are blue hexes connecting the two sides of the board: blue wins! The opposite is true for red.
My students coded up their project and it works very nicely! Still, next time I think I'll assign Clobber instead!
Wednesday, August 26, 2009
Bigger Hex: clear. Bigger Chess...?
I've gotten a number of emails from people reading the blog, and perhaps I should clarify something about the complexity of games.
For playing Chess, the game is of a set size, and thus there are a constant number of possible move options each turn (it's a big constant). The input size is always bounded above: we know how big the game board is and what the maximum number of each piece there can be, etc. We can come up with an algorithm that will take a maximum amount of time (and space) to determine whether a player has a winning strategy.
When we talk about games (and problems in general) being "complete", this means refers to how the amount of time (and space) needed for a solving algorithm to finish increases as the size of the problem grows. With Chess, the board never gets bigger. There are only so many different configurations we can have on that 8x8 board.
Hex is a bit different. There is a standard size (11 x 11) but it's easy to see how this game extends to any given size: just increase the size of the board. Thus, assuming we can play on variable-sized boards, it makes sense to talk about the complexity of this game. Using this, it was shown that Hex is PSPACE-complete.
I've stated this before, but I haven't made it clear that I am considering the generalized, extendable versions of these games. I am, and I will likely continue to do so. There's a problem with this, however: I don't always know how those extensions work.
I claimed at one point that Chess is EXPTIME-complete, but I have no idea how Chess is generalized to an n x n board. I know only that there is a generalization and that it leads to the requirement of an exponential-time algorithm to solve it (I have a lot of reading to do).
Aside from this, though, does anyone actually play n x n Chess? I've seen a few variants: a hexagon-based variant and a weird three-player version, but I've never seen anyone play on a board larger than 8 x 8.
(Thanks to Aviezri Fraenkel for reading and mentioning this. I still have a lot of emailed comments to get to!)