Author: Dann Corbit
Date: 13:06:18 05/09/01
Go up one level in this thread
On May 09, 2001 at 15:49:59, Andrew Dados wrote: [snip] >Since n^5000>exp(n) for n<1000 then I estimate computational cost at >O(5000)<O(exp(n)). According to your argumentation we should not care for too >big n :). >Now you agree that O(5000) is better cost then O(exp(n)), then why we don't use >O(5000)? O(5000) is *identically* O(1) I think you mean O(n^5000) which would be in P. However, if you take a chess tree search and search ply n, then search ply n+1 you will not see this behavior. Why model an algorithm with a function you know beforehand to be wrong? >Here's another one: since there is less then 2^100 chess positions then solving >chess will require less or equal then 2^100 steps. Yes... this is O(1). Where >did you get that O(exp(n)) thingie at all?? :) The number of chess positions has not been determined. 2^100 is (by a landslide) the smallest estimate with any merit (made by an interesting study where GM's were asked binary questions). Be that as it may, that does not help us to model the search at all. It won't shed any light on how difficult it will be to go from ply 3 to ply 5 or ply 14 to ply 20. In short, it has no value as an estimate. We could plug the same data into our exponential calculation and get an estimate of time behavior. We can also use our exponential model to calculate behaviors for values which *are* computable. This makes the model actually _useful_ for predicting things (as a rough estimate of worst case behavior using the standard chess algorithms). The whole notion of algorithm analysis is to produce workable "back of the envelope" type estimates. The notion that finite input results in O(1) behavior produces estimates with no value whatsoever. That is why that sort of idea is not used. >Also, Big-O is defined as asymptotic behaviour, Dan; you can't arbitrary state >what are big or small numbers. For that matter alpha-beta + TT will never be >O(exp(n)). How long does it take your favorite program to go from ply 10 to ply 11? From ply 11 to ply 12? From ply 12 to ply 13? From ply 13 to ply 14? Do some calculations and plot a curve. >I think most of us know what Big-O is; we just differ in classifying chess >problem as finite or not. Finite or infinte makes no difference. Algorithms are NEVER applied to infinite sets. Those algorithms would never complete. We always apply algorithms to finite problems. Having big-O behavior analysis tells us how long it will take to compute a result for a given input problem size. That size will never be infinite. (Trivial calculations aside).
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.