question: If both Chess and Go are played on a board, why does Chess have a finite number of possibilities (or states) but Go doesn’t?
comment: It is because of the variety of pieces that chess has that each has their own rules where go has only 1 type of piece that can be placed essentially anywhere on the board.
passages: As a result, superko variants (moves that repeat a previous board position are not allowed) of generalized chess and checkers are EXPSPACE-complete, since generalized chess and checkers are EXPTIME-complete. However, this result does not apply to Go.
  
  Section::::Computational complexity.:Complexity of certain Go configurations.
   Section::::Computational complexity.
  
  Generalized Go is played on "n x n" boards, and the computational complexity of determining the winner in a given position of generalized Go depends crucially on the ko rules.
  
  Go is “almost” in PSPACE, since in normal play, moves are not reversible, and it is only through capture that there is the possibility of the repeating patterns necessary for a harder complexity.
  
  Section::::Computational complexity.:Without Ko.
   The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.
   All known forced Go cycles are impossible with this rule. The nature of the rule itself suggests that forced cycles are either impossible or astronomically rarer than they are in Go when the superko rule is not used.
   A Go endgame begins when the board is divided into areas that are isolated from all other local areas by living stones, such that each local area has a polynomial size canonical game tree. In the language of combinatorial game theory, it happens when a Go game decomposes into a sum of subgames with polynomial size canonical game trees.
  
  With that definition, Go endgames are PSPACE-hard.
   An issue that all Go programs must tackle is how to represent the current state of the game. For programs that use extensive searching techniques, this representation needs to be copied and/or modified for each new hypothetical move considered. This need places the additional constraint that the representation should either be small enough to be copied quickly or flexible enough that a move can be made and undone easily.
   Go is another turn-based strategy game which is considered an even more difficult AI problem than Chess. The state space of is Go is around 10^170 possible board states compared to the 10^120 board states for Chess. Prior to recent deep learning models, AI Go agents were only able to play at the level of a human amateur.
  
  Section::::Deep learning agents.:Go.:AlphaGo.
   Robson showed that if the superko rule, that is, “no previous position may ever be recreated”, is added to certain two-player games that are EXPTIME-complete, then the new games would be EXPSPACE-complete. Intuitively, this is because an exponential amount of space is required even to determine the legal moves from a position, because the game history leading up to a position could be exponentially long.
   The superko rule (also called the positional superko rule) states that a repetition of any board position that has previously occurred is forbidden. This is the ko rule used in most Chinese and US rulesets.
  
  It is an open problem what the complexity class of Go is under superko rule. Though Go with Japanese ko rule is EXPTIME-complete, both the lower and the upper bounds of Robson’s EXPTIME-completeness proof break when the superko rule is added.
   Section::::Computational complexity.:Japanese ko rule.
  
  Japanese ko rules state that only the basic ko, that is, a move that reverts the board to the situation one move previously, is forbidden. Longer repetitive situations are allowed, thus potentially allowing a game to loop forever, such as the triple ko, where there are three kos at the same time, allowing a cycle of 12 moves.
  
  With Japanese ko rules, Go is EXPTIME-complete.
  
  Section::::Computational complexity.:Superko rule.
   BULLET::::- The number of spaces on the board is much larger (over five times the number of spaces on a chess board—361 vs. 64). On most turns there are many more possible moves in Go than in chess. Throughout most of the game, the number of legal moves stays at around 150–250 per turn, and rarely falls below 100 (in chess, the average number of moves is 37). Because an exhaustive computer program for Go must calculate and compare every possible legal move in each ply (player turn), its ability to calculate the best plays is sharply reduced when there are a large number of possible moves. Most computer game algorithms, such as those for chess, compute several moves in advance. Given an average of 200 available moves through most of the game, for a computer to calculate its next move by exhaustively anticipating the next four moves of each possible play (two of its own and two of its opponent's), it would have to consider more than 320 billion (3.2) possible combinations. To exhaustively calculate the next eight moves, would require computing 512 quintillion (5.12) possible combinations. , the most powerful supercomputer in the world, NUDT's "Tianhe-2", can sustain 33.86 petaflops. At this rate, even given an exceedingly low estimate of 10 operations required to assess the value of one play of a stone, Tianhe-2 would require 4 hours to assess all possible combinations of the next eight moves in order to make a single play.
   Section::::Obstacles to high-level performance.:Combinatorial problems.
  
  Sometimes it is mentioned in this context that various difficult combinatorial problems (in fact, any NP-hard problem) can be converted to Go-like problems on a sufficiently large board; however, the same is true for other abstract board games, including chess and minesweeper, when suitably generalized to a board of arbitrary size. NP-complete problems do not tend in their general case to be easier for unaided humans than for suitably programmed computers: it is doubtful that unaided humans would be able to compete successfully against computers in solving, for example, instances of the subset sum problem.
   Let the finite graph G be connected and loopless, with vertices "V" = {1, 2, . . . , "n"}. Let deg("v") be the degree of a vertex, and e("v,w") the number of edges between vertices "v" and "w". A configuration or state of the game is defined by assigning each vertex a nonnegative integer "s"("v"), representing the number of chips on this vertex. A move starts with selecting a vertex "w" which has at least as many chips as its degree: "s"("w") ≥ deg("w"). The vertex "w" is fired, moving one chip from w along each incident edge to a neighbouring vertex, producing a new configuration formula_1 defined by:formula_2and for "v ≠ w", formula_3A state in which no further firing is possible is a "stable state". Starting from an initial configuration, the game proceeds with the following results.
   Continuing the comparison to chess, Go moves are not as limited by the rules of the game. For the first move in chess, the player has twenty choices. Go players begin with a choice of 55 distinct legal moves, accounting for symmetry. This number rises quickly as symmetry is broken, and soon almost all of the 361 points of the board must be evaluated. Some moves are much more popular than others and some are almost never played, but all are possible.
  
  Section::::Obstacles to high-level performance.:Evaluation function.
   These types of positional evaluation rules cannot efficiently be applied to Go. The value of a Go position depends on a complex analysis to determine whether or not the group is alive, which stones can be connected to one another, and heuristics around the extent to which a strong position has influence, or the extent to which a weak position can be attacked.
   The total number of possible games can be estimated from the board size in a number of ways, some more rigorous than others. The simplest, a permutation of the board size, (N), fails to include illegal captures and positions. Taking N as the board size (19×19=361) and L as the longest game, N forms an upper limit. A more accurate limit is presented in the Tromp/Farnebäck paper.
   It is because there is so much territory left to be claimed that skilled players would not end the game in the previous position. The game might continue with White playing 1 in the next diagram. If the game ended in this new position, the marked intersections would become White's territory, since they would no longer be connected to an empty intersection adjacent to a black stone. 
   The next two measures use the idea of a "decision tree", which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.)
   A move in Alice Chess has two basic stipulations: the move must be legal on the board on which it is played, and the square transferred to on the opposite board must be vacant. (Consequently, capture is possible only on the board upon which a piece currently stands: pieces on board A can capture only pieces on board A; pieces on board B can capture only pieces on board B.) After capture, the capturing piece transfers to the opposite board the same as a non-capturing move.
   Other examples of EXPTIME-complete problems include the problem of evaluating a position in generalized chess, checkers, or Go (with Japanese ko rules). These games have a chance of being EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is sufficiently intractable to imply EXPTIME-completeness, but it is not known if the more tractable American or Chinese rules for the game are EXPTIME-complete.
   The standard basic checkmates (queen, rook, two bishops, or bishop and knight) can all be forced on the 16×16 board, but take a longer time to accomplish. For example, while 33 moves suffice from any winnable position to mate with bishop and knight on an 8×8 board, it can take up to 93 moves on a 16×16 board. For example, if White has a king on a1, a knight on b1, and a bishop on c1, while Black has only a king on c2, White can force mate in 92:
   However, this is not the case because if East had KQ, he could equally well have played the queen instead of the king. Thus some deals with original lie 32 and KQ would not reach this stage; they would instead reach the parallel stage with K alone missing, South having observed 32 and Q. In contrast, every deal with original lie Q32 and K would reach this stage, for East played the king perforce (without choice, or by "restricted choice").
   Section::::Computational complexity.
  
  Usually, in the endgame, the board is partitioned into separate "royal chambers", with queens inside each chamber. We define simple Amazons endgames to be endgames where each chamber has at most one queen. 
  
  Determining who wins in a simple Amazons endgame is NP-hard. This is proved by reducing it to finding the Hamiltonian path of a cubic subgraph of the square grid graph.
  
  Generalized Amazons (that is, determining the winner of a game of Amazons played on a n x n grid, started from an arbitrary configuration) is PSPACE-complete. This can be proved in two ways.
   The grey whale and killer whale can move any number of empty squares along a straight line, limited only by the edge of the board. The dolphin can, too, but only when on the back rank; it is a step mover elsewhere. If an opposing piece intervenes, it may be captured by moving to that square and removing it from the board. A ranging piece must stop where it captures, and cannot bypass a piece that is in its way. If a friendly piece intervenes, the moving piece is limited to a distance that stops short of the intervening piece; if the friendly piece is adjacent, it cannot move in that direction at all.
   Section::::Background.:Difficult challenge in artificial intelligence.
  
  Go is a complex board game that requires intuition, creative and strategic thinking. It has long been considered a difficult challenge in the field of artificial intelligence (AI) and is considerably more difficult to solve than chess. Many in the field of artificial intelligence consider Go to require more elements that mimic human thought than chess. Mathematician I. J. Good wrote in 1965:
  
presuppositions: Go should have a finite number of states since it is played on a board like chess.
corrections: Chess has a variety of pieces whereas go only has 1 type of piece that can be placed essentially anywhere on the board.
raw_presuppositions: Go should have a finite number of states since it is played on a board like chess. Go should have a finite number of states since it is played on a board like chess.
raw_corrections: Chess has a variety of pieces whereas go only has 1 type of piece that can be placed essentially anywhere on the board. Chess has a variety of pieces whereas go only has 1 type of piece that can be placed essentially anywhere on the board.