Game complexity: Difference between revisions

Revision as of 13:39, 29 May 2025

Latest revision as of 00:34, 31 May 2025

(5 intermediate revisions by 4 users not shown)

Line 40:

=== Computational complexity ===

The [[Computational complexity theory|''computational complexity'']] of a game describes the [[Asymptotic analysis|asymptotic]] difficulty of a game as it grows arbitrarily large, expressed in [[big O notation|bigو notation]] or as membership in a [[complexity class]]. This concept doesn't apply to particular games, but rather to games that have been [[generalized game|generalized]] so they can be made arbitrarily large, typically by playing them on an ''n''-by-''n'' board. (From the point of view of computational complexity, a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)

The asymptotic complexity is defined by the most efficient algorithm for solving the game (in terms of whatever [[computational resource]] one is considering). The most common complexity measure, [[computation time]], is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of [[DSPACE|space]] or [[computer memory]] used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be [[PSPACE-hard]], and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).