Showing posts with label hex. Show all posts
Showing posts with label hex. Show all posts

Friday, February 3, 2012

Game Sum Demonstration Videos

A few weeks back, my aide, Ernie, and I played some game sums as demonstrations. Of special note, you may not have agreed with the non-all-smalling of Hex, and that may make you want to watch the last three!

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

Game sums are at the heart of Combinatorial Game Theory. If you give me two different rulesets, a third exists that is the sum of those two and you don't have to specify anything new.

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

After last Friday's post, reader Nick Bentley suggested playing again but allowing each player to not only place a new piece, but also shift an old piece each turn. Ernie and I easily spent all of our Monday meeting trying this out. Here's one of those games. During the game, we had a lot of questions about what was legal (e.g. declining the shift, etc). Hopefully Nick can answer those for us!

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

Y is a game that is very similar to Hex: players take turns claiming hexagons with the hope of connecting sides. In Y, however, the board is a triangular array of hexagons, and the goal of each player is to connect all three sides instead of just their two sides. Perhaps more surprising than the Hex Theorem is the Y Theorem: if all hexagons are colored, exactly one contiguous group of same-color hexagons touches all three sides.

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!

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!

Friday, April 15, 2011

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?

Friday, February 18, 2011

Game Description: Weak Hex (Whex)

When I was first interested in Adjacent Hex (Adjex) a few years back, a friend of mine pointed out another similar game to me: Weak Hex. Weak Hex, or Whex, is extremely similar to adjacent hex because both players must move adjacent to another player's move. Instead of playing next to the last move of either player, however, both must play adjacent to the last move of the red player!

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
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.
(If no adjacent moves are available, the next player immediately loses.)

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

While at the CGT (Combinatorial Game Theory) workshop earlier this month, I watched Ryan Hayward give an excellent talk about Hex and "Rex" (Misere Hex). Ryan is an excellent Hex player and even better Hex theorist (and also a good curling skipper). I was determined to play some Hex with him, but needed a little extra help since I had played so little. Thus, I suggested we play a variant: 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.

I convinced Alan Guo to play a few games with me. We went back and forth, winning and losing, but building up some good intuitive strategies for the game.

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!

One nice property of this game is (I think) that it is "automatically" PSPACE-complete. If I understand Stefan Reisch's original "Hex is PSPACE-complete" proof, the gadgets in the reduction don't have any adjacent uncolored hexagons [citation needed], thus ensuring that each move gives the opponent a jump and the adjacency rule doesn't come into play. (I wonder how helpful it would be to produce a translation of Reisch's paper.)

In my office, I have a 14 x 14 hex board, just ready for adjacent-minded opponents!

Friday, January 15, 2010

Bonus-play Hex

Though I keep talking about the game Hex, please do not assume that I'm a good player at all! I don't know why I have this fascination with a game I rarely play, but apparently I do. Perhaps the reason I like it is that you can define interesting variations on it. The study of Misere Hex has a nice proof that from the staring position, optimal strategies will force the board to fill up.

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

I'm very pleased with the way my software engineering class is going. I've accidentally asked the students to code up some difficult games at times, but they've done a good job of figuring out exactly how to fix these issues. For the most part, using a game suite as the continuing project has worked extremely well!

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

It is known that Hex is a PSPACE-hard game. (See this page, it is the "Hex ist PSPACE-vollstaendig" paper by Stefan Reisch.) Once we add a bit of randomness, however, the strategies suddenly become far easier! As I think I've mentioned before, if you change the game so that the current player is chosen by the flip of a coin, the winning strategy becomes simple.

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

Oops!

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'm posting late on Wednesday. I'll have to learn to post while eating lunch in the future...

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!)