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

Topics for this semester and questions about BIRS 2011

I still have plenty of topics to cover from the BIRS workshop about Combinatorial Games from January, but I want to do each of them justice. At the same time, I'm hoping to get more playable games up and running on my website. With any luck, I'll get some of this accomplished. There is a strong possibility posts will end a bit early this semester, as I'm expecting my first child the first week of May. :)

I haven't gotten to reply to the first comment here yet, so let me do that now.

What did Fan Xie said?
How strong is he?
How did the program worked? (Monte Carlo?)

Can you elaborate on that ? :)

Yes, I certainly can elaborate! I did not get to know Fan Xie terribly well, except to help badger him into joining the NoGo tournament. (He nearly did not play! Luckily, Neil McKay is a persuasive individual!) I didn't pay a great amount of attention to Fan's games, aside from his game against the winning NoGo program. This was a wonderful match, because Fan spent too much time analyzing and explaining whether the computer's moves were good or not (and he did not write that program). Instead of focusing on winning, he was answering everyone else's questions, so the computer came out ahead.

I believe all the computer programs used Monte Carlo (multiple random trial) techniques. From what I understand, they were all modified versions of UAlberta's Go-playing program FueGo. I would like to spend more time talking about this, but the most interesting thing is that these Monte Carlo programs are so easily adaptable from one game to the next. In fact, I believe much of the software is written independent of the different game rules. If you supply the rules, the simulations will run and choose a probable good move.

I am not convinced that this works well for all games, however! I'd like to know how well the algorithm plays Chess, or even Nim! (Maybe impartial games are tough...)

Yet another Table Update Post

Today I'm replacing a usual post here with another big round of updates to this table of game rules.

The biggest update is adding links to websites where you can play the game listed. I didn't find links for all of them, but if you know of one (or a better one than what I have listed) please let me know so I can add it to the list! Additionally, I added links to posts labelled: "Game Description: X" where X is that game.

Since no one complained to me, I removed the column about the complexity of winning the game on that turn, replacing it with a column for general game properties.

As usual, I make some errors here, so please let me know if you find anything I need to fix!

Next week Wittenberg has spring break, so I won't have any new posts until Monday the 14th.

More Tsuro Combinatorics

I keep coming back to the game Tsuro, which I've mentioned in this blog several times.

Let me describe the rules quickly. The game consists of a 6 x 6 grid of empty squares. The border of this grid has two white lines leading in to each side of a square (12 per side, so 48 lines total along the border). Players begin by putting their marker on one of these lines.

There are 35 tiles in the set, of the size of the empty squares on the board. Each side of each tile has two path ends that line up to the two white lines on the border (see the picture at the end for an example of some tiles). Each tile has four path pieces, each with two ends at different places on the boundary of the tile. These paths can cross, and there is a tile for each combination of paths (more on this later). Players keep hands of three tiles, drawing a new one every time they play one.

Each turn, the current player chooses a tile from their hand and lays it on the board in front of their marker. This new tile continues the path their piece was on, and they move their piece to follow that path until its end (it may link to other already-played tiles, so it could go longer than just one tile). The player also moves any other pieces that had their paths extended by this tile, again as far as they can until they reach their path's end.

For all those pieces that moved, if the path either leads them off the board or collides with another marker, then they have lost and are out of the game. The winner is the last one standing (or tie if multiple people lose on the last turn). Since there are only 35 tiles and 36 squares, it is possible all tiles can be played without anyone losing. In fact, the game comes with enough markers for 8 players. Can they all complete the game? Can they all complete it if they all have access to all tiles from the beginning (instead of having separate hands)?

While showing Tsuro to my aide this week, we raised this question. Ernie quickly became interested in trying out the combinations to see if he could get a working solution. This is an excellent challenge; I would guess the problem is NP-complete for general sets of tiles.

The question also came up of whether there are only 35 possible tiles, or whether the game is missing some possible combinations. I'm terrible at counting, but Ernie had some good insight and we worked it out. Here's a sketch of our logic:

Consider a single tile and count the possible configurations of paths in that tile. Choose one of the incoming path locations. There are 7 places that path could connect to. Now go clockwise around the tile to the next not-yet-connected path end. From here there are now 5 possible places this could connect to. After that, there are 3 more for the last one. In total that gives us 105 possible total configurations.

The game doesn't have this many, so there must be some symmetry that is not being considered. Since 35 = 105 / 3, it seems likely that rotational symmetric positions are not being used (which is the case). Now can we find cases where other symmetry is used? Yup!


Each right piece is symmetric with the corresponding left piece! I think the game uses all pieces. It's excellent that this works out to exactly 35 pieces, leaving that extra final open square. Very elegant!