Senket — How Deep Is Senket?

The design goal of Senket is to have the simplest rules and the deepest gameplay possible. Based on the numbers alone it seems that Senket is far more complex than almost any other board game. For example, on a 31×31 board, the log10 of the state space (all possible board positions, legal or not) appears to be at least 500, compared to 171 for Go and 50 for Chess. The log10 of the game tree is at least 2450, compared to 360 for Go and 123 for Chess. The numbers for Go and Chess are from the wikipedia article on game complexity.

It remains to be determined whether the complexity class of Senket is in PSPACE (similar to Othello, Hex, or Connect6) or EXPTIME (similar to Chess, Go, or Checkers), but PSPACE seems possible. Strictly speaking this would mean that Senket is in this respect less complex than Chess or Go, but consider that Nine Men’s Morris is in EXPTIME, but has been solved because of its small state space.

Looking solely at the number of possible board configurations doesn’t accurately reflect the depth of a game. Another indicator is the depth possible in a local situation. One measure of this is the sequence of moves required to resolve the situation, and the breadth of the tree of move sequences the situation can lead to reasonably.

Based on experience, it would seem that local Senket gameplay is at least equivalent to Checkers. Certainly, sequences of five to ten moves are common, and it seems vision beyond that level is possible and beneficial. Simultaneous cost-benefit analysis of multiple positions is required. Until experts have played Senket for some time, the true depth and complexity of the game will remain unknown.

My next post will be a problem designed to illustrate local depth.

Advertisements

5 thoughts on “Senket — How Deep Is Senket?

  1. Pingback: Senket — A Complex Problem « Geoff Canyon’s Appeal to Authority

  2. Herman Hiddema

    Interesting question 🙂

    The number 500 for the state space is based on the number of points (31*31=961) and their possible colors (empty, red, blue), I guess? So 3^961 = 3.2623 * 10^458. This, of course, does not yet take into account which connections have been made.

    From each intersection there are 8 possible connections (except close to the edge), but then we’re counting each connection twice, so the upper bound (ignoring edges) on a 31*31 board is 961*4 = 3844. Taking edges into account makes this somewhat lower, and puts it at 3720.

    The possibility of a connection existing depends on the colors of both its ends. In a random position, each connection has about a 2/9 chance of being legal (2/3 that the first intersection is colored, 1/3 that the other is the same color), so on average there are 827 possible connections in a random position, each of which can be on or off. which extends the state space by about a factor of 2^827 = 9 * 10^248. So the total state space is probably over 10^700.

    I assume that the number 2450 as the log10 of the game tree is based on a simple factorial calculation of the number of points on the board, which is 961! = 8.5244 * 10^2451. Since there is no way for an occupied intersection ever to become unoccupied again (ie, there is no capture/removal rule), this should be a good estimate.

    The only extra thing I can think of is the fact that players can pass, adding some extra game sequences where there are one or more passes during the game (but never two in a row, as that would end the game).

    The game tree complexities of Go and Chess as given (from the Wikipedia article) are based on estimates on average number of legal moves and average game length (for go this is taken as 250 and 150, and for chess as 35 and 80), so I think for a comparison, it would be interesting if you could give an estimate of the average senket game length.

    (Side note: John Tromp and Gunnar Farnebäck have calculated a lower bound for the full game tree complexity of go, and its log10 is 10^48, a truly staggering number)

    Reply
    1. gcanyon Post author

      A very nice analysis. I went with 10^500 for the state space because although it’s possible for two connectable points not to be connected, in practice (so far a few hundred games) I’ve never seen an instance where a player wouldn’t make all possible connections. I came up with one problem where it’s necessary _not_ to connect two posts in order to succeed, but I was searching specifically for an example.

      Honestly I think the “complexity” of a game has more to do with local complexity than overall board complexity. You can make Go as complex as you want by playing on a large enough board, but as long as humans are playing I think there’s an upper limit: on a 500 x 500 board, play on one side of the board is very unlikely to have any predictable effect on play on on the other side of the board.

      Therefore I tend to think of complexity more in terms of Go puzzles — how much variation is possible in the problems a Go game presents you. One example of this for Senket would be: how many different shapes are there for an enclosed space that are secure? How many unsecure, with only one correct play to attack them? How many with two, etc.?

      In Chess nearly the whole board is involved in almost any near-endgame position. That gives, let’s say up to ten pieces, so roughly 64!/54! * 10^5 possibilities. That’s a large number but overstates the situation dramatically since most of those positions are likely to be nonsensical. I could do the same for Go, but the nonsensical position problem would (I think) be even worse there.

      In Senket I think it’s possible to come at it the other way at least a little. If we assume a territory to be evaluated has a border of 30 fences, how many possibilities are there? That’s a harder problem to solve, and the result is much smaller, but all the resulting positions are (at least theoretically) valid.

      One of my greatest concerns for Senket is the possibility that it might come up short on this measure. I just haven’t played (nearly) enough games to have a sense of whether the same positions might come up repeatedly.

      Reply
  3. Herman Hiddema

    I made a slight error, the number of possible connections on the board should be smaller (3478 instead of 3720), but I agree that it is probably not very useful to consider most cases where possible connections have not been made. The same probably goes for positions with more than a certain percentage of the intersections taken (any idea what percentage of intersections is usually taken in a normal end position?)

    I think that Senket is probably in the same general category of difficulty as chess, go, hex, etc. I agree that most of the difficulty of the game is probably localized, and the same is mostly true for go, I think. Chess boards are too small, and chess pieces to wide ranging, to have any sense of “local” play, so everything is basically local. If you look at another chess variant, Shogi, you find that it does have more scope for local battles, because the pieces are so much slower.

    Any chance of getting some kind of online Senket player? I’d love to try it 🙂

    Reply
    1. gcanyon Post author

      So far all the games played have (I suspect) been very thick in the end. Just as a Go master can know a position is secure while an amateur will add more stones to reinforce it, beginning Senket players (which includes me) tend to play by biting off small chunks one after the other, which is very inefficient. I suspect that more skillful players will lay down fewer fences.

      That said, a finished game of Senket will have many posts in place — on a 31 x 31 board, my guess would be at least 200, perhaps 300 or more total. This concerns me from a length-of-play standpoint — Go involves more moves in a typical game than Chess, and Senket likely even more. But a 31 x 31 board seems necessary to ensure strategic vs. tactical play. As you say the board size in Chess makes almost the whole board local, while Go avoids that.

      I am working on a desktop app that will allow two people to play Senket. It’s what I use to make the game board images. Making it automatically score a position turned out to be more difficult to program than I expected, but I think I have the algorithm worked out now. Then I need to clean it up a bit and add networking, and I’m set. I’m eager to play online. Finding people willing to play the game against me locally is difficult, even when I offer handicaps. I suspect once I get someone with your skill level in Go involved, my undefeated streak will come to a quick end. Certainly if I manage to entice an expert TwixT player, I’ll go down in flames — the game play is similar enough that I expect they’d destroy me.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s