Game complexity can only be crudely estimated. The number of legal positions (state-space complexity) for chess has been estimated at anywhere between 1043 to 1050; in 2016 the lower bound for Go was estimated by Tromp and Farneback at 2 x 10170. Alternately, a measure of all the alternatives to be considered at each stage of the game (game-tree complexity) can be estimated with bd, where b is the game's breadth (number of legal moves per position) and d is its depth (number of moves [plies] per game). For chess and Go the comparison is very roughly ≈3580 ≪ ≈250150, or ≈10123 ≪ ≈10360. (Allis 1994, стр. 158–161, 171, 174, §§6.2.4, 6.3.9, 6.3.12) Allis, Louis Victor (1994). Searching for solutions in Games and Artificial Intelligence(PDF). Maastricht: Proefschrift Rijksuniversiteit Limburg. ISBN978-90-9007488-7.
