Author: Dann Corbit
Date: 09:25:50 05/09/01
Go up one level in this thread
On May 09, 2001 at 09:19:37, Sven Reichard wrote:
>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.
This isn't too far from it. However, what we consider is what happens to the
algorithm as n "gets large." What "gets large" means is purely a function of:
1. Our available computer power
2. The type of algorithm
3. How desperately we want an answer.
For f(n) = a constant, n can be very, very large.
For f(n) = n, n can be in the billions or perhaps even trillions (consider the
RSA factoring efforts, or the GIMPS project or SETI, etc.)
For f(n) = n*log(n) we can process very large sets
For f(n) = n^3, we can process large sets (e.g. solve a one million by one
million matrix requires 10^18 time steps and so would be solvable on a petaflop
computer in unit time. Calculating nuclear explosions in core, etc. springs to
mind)
For f(n) = n! or exp(n) only very, very tiny problems are workable. Even
problems that are polynomial time can be extremely unweildy if the highest order
term has a large constant exponent.
Now that we are armed with data about how our algorith performs, we can decide
how large of a problem we can solve. That is the very reason to be behind
algorithm analysis. We want the answer to a single question:
"What problem size is workable?"
>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.
tic-tac-toe is probably not a good example. Though there are three states for
each box, there are only nine boxes. There are less than 3^9th final output
states since many are illegal like these are:
O | O | O
--+---+--
O | O | O
--+---+--
O | O | O
O | O | O
--+---+--
x | x | x
--+---+--
| |
Now, this is a microcosm of the whole chess argument, I think, so why don't we
take a moment to consider the terrificially easier game of tic-tac-toe.
I might write a tic-tac-toe algorithm that takes random moves and keeps trying
until it has proven a win. Such an algorithm could be so horrible that it
basically never completes, even with a microscopic problem set like this. That
algorithm is *not* O(1). If there were a reasonable time limit imposed, that
tic-tac-toe engine would lose every game on time.
I can do a minimax-search with alpha-beta. This will complete (for all intents
and purposes) instantaneously on a modern computer. That is an artifact of the
size of the tree, and does *NOT* effect the complexity of the search. It just
so happens that when the tree is tiny, it completes very rapidly. In other
words, we have a tiny input -- hence it is practical and even efficient. You
might argue that such an algorithm is pragmatically O(1) {and indeed, in this
case, I might be forced to agree} but such an algorithm is ALSO O(exp(n)) (and
O(f(n)) for any other function which grows faster than the constant function).
For tic-tac-toe you could completely calculate every move before-hand from the
bare board to every possible outcome with brute force and store the table. This
algorithm *is* Theta(1) in time at least [simple table lookup for every board
position that is legal].
>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) :)
Simple, come up with a branching factor that is almost identically 1. Do like
the chessplayer {I forget who} who said, "I only consider one move -- the best
one!"
;-)
You have to have a fully formed tree to start with. For deep searches, half the
pain is forming and storing the data.
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.