Author: Sven Reichard
Date: 06:19:37 05/09/01
Go up one level in this thread
On May 09, 2001 at 03:39:42, Uri Blass wrote: >Algorithms to solve problem like chess,go or other games can be described as >O(1). > >Uri At the risk of repetition and adding to the confusion, here are my two bits: The complexity of an algorithm is usually given as a function of the input size n; moreover we usually consider its behavior as n goes to infinity. Since the complete information about a Chess position can be described by input that is bounded in size (just give the moves that lead to the position; I think we all agree that no game can last more than, let's be generous, 10,000 moves), it makes no real sense to consider the theoretical complexity of the Chess problem. What does make sense is to consider the complexity of an algorithm for any Chess-like game (2p0s, i.e., TicTacToe, Othello, Go, ...). And afaik, these problems are known to be worse than NP. It might be more relevant to consider the problem as it usually used by us programmers: Given a minimax tree with nominal depth n (there might be extensions and transpositions), determine its minimax value. If we leave out the transpositions, this is still worse than NP. If we factor in transpositions and the correlations between "similar positions", the complexity goes down, but the complexity analysis becomes a total mess. But my guess is that there is no algorithm for this that is P or even NP. Personally, I'd be happy with an algorithm that is O(n^3) as opposed to O(n^12) :) Sven.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.