Finally Calculated: All the Legal Positions In a 19x19 Game of Go (github.io)

Reader John Tromp points to an explanation posted at GitHub of a computational challenge Tromp coordinated that makes a nice companion to the recent discovery of a 22 million-digit Mersenne prime. A distributed effort using pooled computers from two centers at Princeton, and more contributed from the HP Helion cloud, after "many hiccups and a few catastrophes" calculated the number of legal positions in a 19x19 game of Go. Simple as Go board layout is, the permutations allowed by the rules are anything but simple to calculate: "For running an L19 job, a beefy server with 15TB of fast scratch diskspace, 8 to 16 cores, and 192GB of RAM, is recommended. Expect a few months of running time." More: Large numbers have a way of popping up in the game of Go. Few people believe that a tiny 2x2 Go board allows for more than a few hundred games. Yet 2x2 games number not in the hundreds, nor in the thousands, nor even in the millions. They number in the hundreds of billions! 386356909593 to be precise. Things only get crazier as you go up in boardsize. A lower bound of 10^{10^48} on the number of 19x19 games, as proved in our paper, was recently improved to a googolplex. (For anyone who wants to double check his work, Tromp has posted as open source the software used.)

Comments

Is it solved then?

[menkhaura]

Can we consider the traditional game of Go solved, then? And how about chess, what about calculating 32-piece EGTBs?

Re:Is it solved then?

[Anonymous Coward]

I have not read TFA, as is.tradition. It may just be an existence proof.

Re:Is it solved then?

[Anonymous Coward]

This is a count of legal[1] positions, or how many games you can end up with.

A "solved" game would be one with efficient real-time evaluation of the next "winning moves", which is entirely a different job.

[1] That should also depend on the regional rule variation. A legal move by the Chinese rule may not be one by the Korean rule.

Re:Is it solved then?

[Anonymous Coward]

No- they computed what all the possible boards are. "Solving" Go would involve finding an optimal move for each of those possible boards, which is much harder.

Re:Is it solved then?

[Anonymous Coward]

TFS makes it sound like they didn't even do that much - they merely calculated how MANY there are, which to be clear, is an impressive accomplishment, but there's no amount of storage in the world that can actually hold them all.

Re:Is it solved then?

[Anonymous Coward]

what if google stored them

Re:Is it solved then?

[ledow]

Do you realise how big a number 10^(10^48) actually is?

The bit in brackets has 48 digits (say 47 zeroes after a number). Then the total is actually THAT NUMBER of digits.

10^48 = 100000000000000000000000000000000000000000000000

10^(10^48) has ^^^^^^ that many decimal digits in it's expression.

For reference, Giga is 10^9. Tera is 10^12. Exa is 10^18.

And THIS number, has 10^48 DIGITS when you say how big it is. It would take more than the storage of the world to write out how big that number was.

Re:Is it solved then?

[Megane]

It's like asking for the Answer to the Ultimate Question of Life, the Universe, and Everything, getting an answer of "42", then realizing you didn't actually know what the question was.

Re:Is it solved then?

[Anonymous Coward]

A solution for Go would involve creating a directed graph, with cycles allowed. The result found in this article is the number of nodes in this graph. The edges in the graph would be legal moves, moving from one legal board configuration to another.

You would have to additionally label each node in the graph with the scoring value of that position for each player, if the players agreed to end the game at that position. (The game of go does not have an explicit winning goal like "checkmate" in chess, rather the players agree that any more moves are pointless, and then count their territory.) It would probably also be a good idea to have a label for a position not being a reasonable place to end a game.

Each edge (move) would also have to be labelled with the number of captured stones.

Counting the number of legal games (with no handicap) would be counting all possible non-cyclic paths through the graph, starting from the blank board node, going to every position where it would be reasonable to end the game in. For each path, count the number of captures for each player, and add those + handicap/komi to the territory values of the position. Then you can determine who the winner is for that game.

The number of edges required in that game graph is likely many times larger than the number of nodes. I would rather not think about the number of paths.

Re:Is it solved then?

[ecotax]

Impressive as it is, it's just the number of legal positions. It doesn't say anything about whether optimal play always results in black or white always winning or not. Compare to the number 26,830 for tic-tac-toe, compared to saying it's a draw.

Re:Is it solved then?

[SuricouRaven]

This does not solve Go. It does make it possible to estimate how feasible solving Go is: Roughly how many universe-lifetimes will it take for your computer to calculate the next move?

Re:Is it solved then?

[Amouth]

You know i've always thought about the beauty that i the simplicity of Go which creates a complexity for formulaic solving.

But i just thought of a new level, everything you said is dead one, but when you mentioned "without handicaps".. just made me stop and realize that once you figure out how to solve the base, you will need to go back and re do everything for each handicap possibility winch is 1-9 stones, and while they are traditionally placed on star points, that isn't a requirement.

yea wow, i'ts amazing how such a simple rule variation explodes into possibilities

Re: Is it solved then?

[Anonymous Coward]

If you could envision the complete Graham's number your head would literally turn into a black hole (Numberphile).

Re:Is it solved then?

[Imrik]

One of the rules of Go is that you can't repeat an earlier board position, meaning cycles are not allowed.

Re:Is it solved then?

[Vermonter]

While some rule sets may allow for moves that are illegal in other sets (such as playing a suicide move), after all captured stones are removed from the board, the remaining position will be legal in all rule sets.

Re: Is it solved then?

[Anonymous Coward]

Then for a 2x2 board I only see 3^4 permutations (unoccupied, black, white). Where do the hundreds of billions come from?

Re:Is it solved then?

[johntromp]

The notion of legal position namely "every group of connected stones of the same color having an empty point adjacent to it" is NOT dependent on any particular choice of go rules.

Only legality of moves is...

Re:Is it solved then?

[Impy the Impiuos Imp]

A long time ago, I read that a universe jammed with subatomic particle-sized computing components, about 10^^120 (for solid neutrons), running for the age of the universe at the speed of light, couldn't come close to playing a perfect game of chess, which has many powers fewer moves to consider.

Re: Is it solved then?

[Gorobei]

The board can be in one of 81 states (well, less, cos some are illegal.) The number of paths for the initial board to all ending boards is in the hundreds of billions.

Re:Is it solved then?

[John Allsup]

Think before you type... 10^1=10 has TWO digits, and ONE zero _after_ the 1. 10^2 =100 has THREE digits, and TWO zeros _after_ the 1. So 10^48 has 49 digits, and in base 10 has a 1 followed by 48 digits. But yes, so big we don't have a sensible 'giga' or 'mega' adjective even for the base10 logarithm...

Re: Is it solved then?

[angel'o'sphere]

The board can be in (19*19)^3 states.

Re: Is it solved then?

[johntromp]

You mean 3^(19*19), a MUCH bigger number.

Re:Is it solved then?

[Anonymous Coward]

Can we consider the traditional game of Go solved, then?

No, I don't think so. Knowing that there are somewhat fewer, but not significantly fewer, possible board positions that could occur through a sequence of legal moves doesn't really do anything except provide a more precise upper bound on what everyone who is familiar with the game already understood to be an insanely large number. It may not be 3 to the 361 power, but even so the number of legal boards is still wildly impractical to search effectively or even just to store in memory. The game has so many branches with both winning and losing end games that board evaluation functions, which worked well in Chess, are essentially useless for game tree analysis in Go. Moreover, what techniques do exist in GO playing programs are still relatively weak and don't produce very strong play, especially on the full 19x19 board. A reasonably intelligent human player who plays and studies the game for a few years will beat the programs on the 19x19 board regularly, even with stone handicaps. This is not the case for Chess, where commercially available programs, like Fritz, regularly achieve master levels of strength in play on personal computing devices.

Re: Is it solved then?

[camperdave]

Explain how that is possible on a 2x2 board.

Re: Is it solved then?

[camperdave]

I don't know the game of Go, but it seems to me that the first player has four choices of where to put her stone. The second player has three, the first two, and the last one is forced. That's 4! or 24 possibilities, not millions or billions.

Re: Is it solved then?

[angel'o'sphere]

Right, my bad ;)

Re: Is it solved then?

[angel'o'sphere]

By adding 17 grid positions both directions.
If you want to talk about 2x2 boards, say so, the topic/subject line e.g. would be a good place to mention it.

Re:Is it solved then?

[Anonymous Coward]

Well that leads to the question of whether every Go state that satisfies your condition is actually possible given the initial conditions of Go.

I think that's true of every version of Go I'm familiar with, but I'm not familiar with them all and there are certainly many games where a position itself is legal but there is no possible sequence to achieve that state. Consider: chess, where black has 8 pawns and two bishops which are both on black squares, and nobody is in check. The position itself is "legal" in some sense but there is no sequence of events in standard chess that could achieve that.

Re: Is it solved then?

[Anonymous Coward]

They did say so.

Re: Is it solved then?

[Your.Master]

The first player has 4 choices (all equivalent), the second player has 3, but only one of those choices leads to the deadlock you described. Actually, a case could perhaps be made that the final state is not a deadlock because it removes all of the other player's liberties; but the same case could be made that this violates the suicide rule. I'm just going to call two parallel solid blocks a deadlock rather than look up a ruling.

The other two choices leave the third player with the choice to either immediately win the game, or to deadlock. If you consider exactly equivalent board positions (differing only by rotation or reflection, which in Go is not a different board position), then there are only 3 possible games I believe on a 2x2 grid.

Re:Is it solved then?

[niftymitch]

; 10^(10^48)
Raising to very large power

Re:Is it solved then?

[RockDoctor]

So, we all know (hopefully) what a fencepost error is.

Now we can quantify how much worse a "Go board error" is than a fencepost error. Quite a lot worse.

I like the idea of writing a sparse ternary array of 361x361x361, and then having to take the 363rd power of that. TFA's suggestion that Go counting could make a decent server benchmark: * The task is well defined, easily understood, and non-artificial. * The program code is small and self-contained. * The generated data sets are huge. * The problem is a typical instance of map-reduce, and thus representative of a wide class of popular problems. * The computation requires a good balance of multi-core processing power, memory for sorting, and disk-IO. * The board size parameter gives an entire family of benchmarks, where each increment corresponds to a factor of about 5 in effort. He knows how to dangle a Babelfish in front of a nerd's ear!

Re:Is it solved then?

[RockDoctor]

Hmm, [code] tag fails on Slashdot ; works in WordPress.

I shall break the knuckles of the next web developer I meet. Pass the encouragement on to anyone you know at Slashcode and/ or WordPress.

Re: Is it solved then?

[RockDoctor]

Where do the hundreds of billions come from?

When you play a stone onto the final remaining liberty of a stone or group of stones, then that group is removed from the board. Then the move is ended and you have to consider whether the board position is legal.

The atom of the game is "play stone and remove any prisoners captured, then consider if the board is legal", not "play stone, consider legality, then remove prisoners".

Re:Is it solved then?

[RockDoctor]

That varies between rule sets. It is certainly a popular rule set, but there are others - for example the Nihon Kiin rule set has much more complex rules on kos which allows for some repetitions of the boar position if either player forces a triple ko. How to score, or decide on whether the game is ended is then very different.

I can't remember any particular stories, but I would suspect that people have died - disembowelled and/ or beheaded - over some of these rule disputes. Which is why the rules have been suggested.

It is important to establish your rules before starting a game. Particularly if you or your opponent has both swords.

Re: Is it solved then?

[camperdave]

Liberties? Deadlocks? Suicide rule?

I don't know GO, but one thing I have found out is that as play progresses, pieces are removed from the board. That throws my 4! analysis out the window.

Re: Is it solved then?

[camperdave]

There are 81 final board positions. However, not all of them are legal. With captures and removing stones from the board, there are multiple ways of getting from the start position to the final position. Apparently, there are as many as 386,356,909,593 games on the tiny 2x2 board if you do not eliminate rotations and reflections. Don't ask me how though. I don't play Go.

Re:Is it solved then?

[johntromp]

One of my major gripes about slashdot is that it doesn't allow editing of one's comments.

PLEASE LET US EDIT!

Re: Is it solved then?

[Anonymous Coward]

I can live without being able to edit comments. One ought to think before one posts.
The lack of non-Latin script is more annoying.
The lack of reminders of allowed-HTML in the mobile - comment screen is annoying too, but I don't often post from mobile.
By coincidence, I re-joined the Brit.Go.Assoc. just last month. Still only 11 kyu though.

Dammit. Forgot password. . Rockdoctor

2x2 board

[Anonymous Coward]

It would help to have more explanation of why a 2x2 board has more than 3^4 possible permutations.

Re: 2x2 board

[Teppy]

A 2x2 board has more than 3^4 possible games, not legal positions. The same legal position may occur in multiple games.

Re:2x2 board

[fph il quozientatore]

That number probably refers to legal games (=sequences of moves). The result on the 19x19 board enumerates the legal positions, instead. Confusing abstract.

Re: 2x2 board

[Anonymous Coward]

So knowing very little about go, I take it pieces can constantly flip back and forth between players or something happens that lets you remove a piece from the board?

Re: 2x2 board

[jofer]

You capture opponents pieces and remove them from the board. There's a good introduction here (the site is a great resource overall): http://senseis.xmp.net/?RulesO... In addition to playing a stone, passing is always a legal move (if both players pass the game ends). Because of this, "infinite loop" positions occur frequently and there's a rule called ko to address that. If your move would repeat the previous board position, you must play somewhere else. (Again, a good explanation is http://senseis.xmp.net/?Ko ) At any rate, for any given board state, there are a huge (but finite) number of different sequences of moves that might have led to that board state.

Re:2x2 board

[Chris Mattern]

The summary is crap from beginning to end. It confuses counting positions with enumerating them. It confuses the number of possible games with the number of possible positions. All in all, a typical timothy post.

Re:2x2 board

[Anonymous Coward]

Yes, I was wondering the same thing.

Re: 2x2 board

[Vermonter]

In addition, if the game is being played under any of the majority of rule sets, there is a "superko rule", which means you cannot repeat a previous board position, which the "billions of games for a 2x2 board" does not account for.

Re: 2x2 board

[Palinchron]

If your move would repeat the previous board position, you must play somewhere else.

Then I highly doubt they calculated all legal positions in the game. They probably calculated all legal positions of the board, but that's a different thing.

The number of possible positions of the board is upper-bounded by 3^(19^2), with 19^2 positions that each can hold a black stone, a white stone, or no stone at all. This exact number was probably computed by this research.

But the possible positions of the game include not just the current board position, but also the set of all previous board positions; after all, the same board position can admit different future games, and be won by different players, depending on the previously-seen board positions. Thus, the possible positions of the game is vastly huger than the number of possible positions of the board, upper bounded by 2^(3^(19^2)).

Re:2x2 board

[johntromp]

Author here.

A single 2x2 game can visit as many as 48 of the 57 legal 2x2 positions, with many dozens of passes in between moves, and obviously many captures.

This page

http://tromp.github.io/java/go...

on solving 2x2 go with various search methods may be helpful. I've lost track of my original 2x2 game counting code but suspect it was a close relative of this code.

Re: 2x2 board

[johntromp]

The 386356909593 games do account for superko.
That is exactly the number of simple (meaning not visiting the same point twice) paths starting
from the empty node in the graph in Figure 4 on page 5 of our paper http://tromp.github.io/go/gost...

Without superko, the number of 2x2 games would simply be infinite...

Re: 2x2 board

[johntromp]

Yes, I counted the number of possible board states, which I call positions.

You propose to instead use the word position to describe the complete game state including set of previously visited board positions.

I say that's really confusing.

Re: 2x2 board

[Golddess]

You capture opponents pieces and remove them from the board.

And that would explain my confusion. I was unaware that squares could ever revert to blank.

Re: 2x2 board

[sexconker]

That's a pointless measurement, though. A game of checkers has infinite possible games because you can repeat positions. For a player, or an AI trying to win a game, all that matters is the current game state and the possible game states, not how you arrived to that state.

Re:2x2 board

[angel'o'sphere]

What do you mean with 2x2 go?

A square with the 4 corners as legal positions?

The game is over after a few moves ... so the number of legal positions is rather small and far from billions.

Re: 2x2 board

[Anonymous Coward]

You capture opponents pieces and remove them from the board.

And that would explain my confusion. I was unaware that squares could ever revert to blank.

The squares are always blank. You go on the edges, not the squares. So a chessboard is a like 9x9 Go board.

Re:2x2 board

[johntromp]

2x2 is Go played on a 2x2 board.
where the 4 corners are the playable points.

A game can continue for dozens of moves.

Re: 2x2 board

[johntromp]

And the number of legal chess positions is in between the number of legal 9x9 Go positions and the number of legal 10x10 Go positions...

Re: 2x2 board

[DNS-and-BIND]

It's how the word is used in chess. Not really sure about Go, but I suppose it's the same. Here's the thing about words: you can't just make them up and then tell everyone they have to use your definition. That's crazy talk.

Re: 2x2 board

[Anonymous Coward]

Has anyone suggested application of the result to quantum mechanics? (Seriously - the states reminds me of it)

Re: 2x2 board

[Vermonter]

I stand corrected, and amazed.

Re: 2x2 board

[johntromp]

That's NOT how it's used in chess.
Even though the notion of chess position might include some game state information
  like side to move, castling rights, and en-passent capturability,
I've NEVER seen it include the set of all previous board states, as would be necessary
for applying the 3-fold repetition rule in the game's future.

Re:2x2 board

[angel'o'sphere]

It can't continue over dozen of moves.
The maximum is six moves. Depending on the move of the second party it wins after six moves or loses after two.

Re:2x2 board

[angel'o'sphere]

That was meant to read "loses after three".

If you count symmetries as different variations, you get of course a few more positions but not moves. You also could let the beginner make a mistake after the second had made a mistake, and instead of winning after move 3 he would then lose after move six. There is no way the game can continue in the first case beyond move three and in the other cases beyond move six.

Re:2x2 board

[johntromp]

You might want to learn how to play Go:-)

Re:2x2 board

[johntromp]

This 8 move game disproves your claim:

      . .
      . .
A2
      X .
      . .
B1
      X .
      . O
A1
      X .
      X O
B2
      . O
      . O
A1
      . O
      X O
A2
      O O
      . O
A1
      . .
      X .
B2
      . O
      X .
A2
      X O
      X .
pass
pass

Btw, we're counting all games, not just games without mistakes.

Re: 2x2 board

[RockDoctor]

More to the point, the 24 (IIRC, including symmetry operations) legal positions for a 2x2 game can occur multiple times in a game.

Re: 2x2 board

[RockDoctor]

you can't just make them up and then tell everyone they have to use your definition. That's crazy talk.

While you're not wrong, this might be a good moment to reflect that Go has a recorded history considerably longer than the history of the language you're writing in. (That's if you take your English back to Beowulf. "Hwat!" ; if you're talking about Shakespeare then the difference is greater.)

The mapping of chess game concepts thought English, into Japanese (or Chinese, or Korean) and onto Go game concepts is just slightly likely to lose something in the translation. Unless, of course, you're fluent in Go and in chess.

I stopped trying to keep up with the computational complexities in Go 20 years after I started to learn the game. That was before I got regular internet access.

Re: 2x2 board

[RockDoctor]

I was unaware that squares could ever revert to blank.

... which is why you count the board state in ternary.

Re: 2x2 board

[RockDoctor]

And as John says up-thread, he does include superko in his game definition.

*sigh* headline says positions, text says _games_

[Anonymous Coward]

slashdot is incompent as usual

386356909593 my ass

[Anonymous Coward]

Um, there are not billions of games on a 2x2 board. This site has the complete list of legal (and illegal) placements on a 2x2 board.
http://senseis.xmp.net/?PositionsAndGamesOn2x2

Re:386356909593 my ass

[Anonymous Coward]

You appear to be confusing "games" vs "board states". The number of valid games is vastly higher than the number of distinct board states.

Re:386356909593 my ass

[ledow]

You have failed to understand Go.

Board positions flip back and forth all the time as you capture territory, and then your opponent recaptures a portion, and so on.

Think more of Othello/Reversi - although there are only 8x8 board with each square either empty, black or white, the number of positions that flip back to earlier or similar positions is high throughout the game.

Re:386356909593 my ass

[Anonymous Coward]

In Othello/Reversi, since the number of pieces on the board increases after each move, positions can't repeat.

Re:386356909593 my ass

[beelsebob]

No, the summary is confusing "games" and "board states". It explicitly states positions, not games.

Re:386356909593 my ass

[angel'o'sphere]

It is extremely rare that territory gets recaptured.
Usually there is simply no places left to place stones in a meaningful way!

Re:386356909593 my ass

[RockDoctor]

As John said - you need to learn to play Go before commenting on how to play Go.

You were aware that you can pass in a game of Go? It's not the end of the game. So the number of initial plays on a 2x2 board is 5, not 4.

Re:386356909593 my ass

[angel'o'sphere]

I play go.
And you can not pass in a game of go. Unless you have weird self made up rules.

Re:386356909593 my ass

[angel'o'sphere]

I stand corrected, according to the english wiki you can pass.
Strange that I never experienced that, all games I played ended when one player suggested 'let's count' and the other agreed.
So we have a few more options ... to tired right now to count the logical max amount of moves if both parties can arbitrarily pass.

Re:386356909593 my ass

[RockDoctor]

The end of a game is, traditionally, when both players pass. SOME rule sets (not all - you have to check your local rules in each tournament you attend) require you to hand over a stone to the opponent's prisoner pile each time you pass. SOME don't. Obviously, this affects the counting. Which is why you need to check the rule set in use.

IF the prisoner isn't handed over, and you pass but the opponent does not, then either s/he has added a stone to a dead group which remains dead - this will go into your prisoner pile at end-game ; OR the opponent has played an unnecessary stone into their own territory and lost themselves a point of empty territory ; OR there was undecided territory on the board where YOU ought to have played instead of passing!

Go is a considerably more complex game than novices (people in the first couple of thousand games of their career) generally realise.

Re:386356909593 my ass

[angel'o'sphere]

I probably did a bit less then 1000 games ;D
That might explain my missing of passing. I only was about 11th kyu or something ... or about to acquire that level. Meanwhile I think I dropped down to 20 or something ;D

Re:386356909593 my ass

[RockDoctor]

People in the process of learning the game normally start in the mid 30s of kyu and will frequently strengthen by several kyu per game until they get to the low twenties. After that, you really need to start sitting down to formally learn set pieces (e.g. how 1-stone or 2-stone jumps can be cut - and therefore when to do a 1-stone extension instead of a 2-stone extension).

It took me about 8 months simultaneously learning and running a teaching club to get to 14 kyu. Then it took another year to make 11 kyu. And there I've stagnated for nearly 30 years, because I only get about 2 or 3 games a year. (I've tried playing online. I hate it.)

Error on line 12

[Anonymous Coward]

Spotted a mistake in the code on line 12... sorry, you have to start over, fellas.

Tic Tac Toe

[Anonymous Coward]

How about Tic Tac Toe?

Re:Tic Tac Toe

[shortscruffydave]

How about Tic Tac Toe?

No...let's play Global Thermonuclear War

Re:Tic Tac Toe

[RockDoctor]

It's about 30,000 possible games, IIRC.

error in title

[youngjeffrey]

Error in the title. They most certainly did not calculate all legal positions, only the exact *number* of legal positions. Which is a *very* different thing.

Re:error in title

[Imrik]

They calculated what they are, they just didn't save them.

Re:error in title

[youngjeffrey]

No, they certainly did not enumerate them in any way. They could not physically have done so (with today's technology). Look at the magnitude of the number again.

What's this good for?

[Anonymous Coward]

Since they published the s/w, he proposes one use it for a server benchmark.

Counting sheep is good for going to sleep, but I don't thing counting valid go board states is going to work for that because there is too much thinking involved.

Very interesting, nerdy work, but somehow
I don't see how the world is better because we know how many possible board positions there are in a size 19 Go board.

What am I missing?
Perhaps if he had done size 20 instead?

Re:What's this good for?

[PPH]

Counting sheep is good for going to sleep,

No its not

Pfft

[Anonymous Coward]

Way to solve a non-problem.

Bad description

[Chris Mattern]

They haven't calculated all the legal positions. They've counted all the legal positions.

This sounds like a job for Siri

[Overzeetop]

https://youtu.be/umDCQNTkSCk

you made Matt Ahrens cry

[Anonymous Coward]

wow. 10^48 huh?

that finally filled up my zpool.

what am I going to do with the other 999 quattuordecillion 999 tredecillion 999 duodecillion 659 undecillion 717 decillion 633 nonillion 79 octillion 61 septillion 536 sextillion 536 quintillion 625 quadrillion 392 trillion 568 billion 231 million 788 thousand and 544 bits now?

thanks alot, Tromp.

you big jerk.

A 2x2 board has an infinite amount of games...

[wertigon]

... But only 85 legal positions, with many being mirroring positions.

Placing two stones of the same color over the diagonal of this board leads to an absorbing state.

Any other state can be reset by either black or white to a single stone.

This is assuming the players are not playing with the rule of no repetition (but with the rule of no suicide).

For clarity, see the rulebook.

Re:A 2x2 board has an infinite amount of games...

[jfengel]

Where does 85 come from? There are 4 positions, each with 3 legal states (back, white, empty). I get 3^4=81. Is there some rule I'm missing that creates 4 more legal states?

Re:A 2x2 board has an infinite amount of games...

[Anonymous Coward]

... But only 85 legal positions

57

Re:A 2x2 board has an infinite amount of games...

[johncandale]

this. the mirrors really make it even less. and no suicide make it even less still. I highly doubt these numbers,

Re:A 2x2 board has an infinite amount of games...

[RockDoctor]

There are 4 positions, each with 3 legal states (back, white, empty).

But each player has 3 possible moves, for every position on the board : play on this point ; play on any other legal point ; pass.

Power Costs

[InterGuru]

I wonder how many megawatts such a calculation takes?

Re:Power Costs

[GuB-42]

I don't know if backtracking is used but if it is, that's 1.21 gigawatts.

Re:Power Costs

[InterGuru]

Actually, I should have asked megawatt-hours.

Can they figure out wins for each color?

[Anonymous Coward]

Black stones, white stones, and ties? Or did they take into account that Black moves first?

Universal Barcode

[Anonymous Coward]

2.081681994 * 10^170 = the number of legal positions.

Yet by some accounts, it is estimated that the there are between 10^78 to 10^82 atoms in the known, observable universe.

Makes for one heck of a tracking number.

Has anyone checked

[Hognoxious]

Has anyone checked the sky? I hope that overhead the stars aren't, without any fuss, going out.

Re:Has anyone checked

[Anonymous Coward]

It's cloudy here. On the other hand Unix appears to be self-destructing...
Maybe that's the true omen.

Re:Has anyone checked

[Hobart]

I understood that reference!

Re:Has anyone checked

[RockDoctor]

I too got the reference.

IF God existed, he'd play 3-d Go on 19x19x19, which would be on the order of L19^5^L19^L19, I think ( this result being "L19")

Re: Linear algebra permutation determinant functio

[Anonymous Coward]

Apk my dear chap, you look so much better without your rant hat on.

Are symmetries left our because of superko?

[GlobalEcho]

Looking into the paper, we see that with L(2,2)=81-16-8=57 various positions that are symmetric transforms of each other are considered distinct. For example, on sees this in the upper right and lower left corners of Figure 1. Now, it's true that superko will break some of that symmetry, but not all of it. How much complexity disappears with more accounting for symmetry?

Error: Go is 20 by 20, not 19 x 19

[nomentanus]

Go is a game played on a board with 20 x 20 = 400 intersections. That's where the pieces are placed, not in the center of the 361squares. I suppose I now know why most of my software is so crappy - nobody checks their assumptions. (There were 90 comments already when I wrote this!) Even when the evidence is staring them in the face, visible in every photo of a Go game, ever. What's gonna happen next, Republicans exhibiting climate denial or something crazy like that?

Re:Error: Go is 20 by 20, not 19 x 19

[RockDoctor]

If you're trying to be funny, it failed.

Since it's a matrix (& I'm "APK", lol)?

[Anonymous Coward]

See subject: Linear algebra permutation determinant functions are a likely best bet to calculate checkers or chess which are also matrices: Matrix math is what it does & it's even called that @ times...

I don't *think* that factorial permutations like 3x3 matrix = 9! = 9x8x7x6x5x4x3x2 (screw 1) = 362880 will cut it due to pieces movements in checkers/chess... & that's not right I wager. ...but MIGHT be close & on the 'right track' (might as well be a million miles away though, close doesn't cut it) to the answer, but not enough!

(2 'pieces'/players in tictactoe with single movements is simpler than checkers and certainly so for chess with movement variations galore, especially damn knights - so again, I wager it's on the right track, but not completely right either...) ... imo @ least, but not REAL strong in math here...

(KGIII a PhD in mathematics outta RIT & a /. registered users member here is, ask him - bet HE knows)

"No one can be TOLD what the matrix is - you have to see it for yourself..." - APK

(Does "to right & down 'salute'" which linear algebra folks WILL understand the meaning of... lol!)

APK

P.S.=> Of course, in checkers it's much simpler than chess for determining it - the movements are "set in stone" for pieces (except 'doubled up' ones) - in chess they vary widely by pieces abilities (especially the damn knights)...

Chess = my all-time favorite game - it's more-or-less classic battlefield & field general tactics "gamified" imo - that damn "GO" is more like vietnam tactics (I gauge folks' intelligence using it in fact quite often, assuming they know how to play fairly well @ least, first)... apk