Author: Graham Laight
Date: 03:10:01 05/12/01
Go up one level in this thread
On May 11, 2001 at 15:02:28, Robert Hyatt wrote: >On May 10, 2001 at 07:16:32, Graham Laight wrote: >>I find myself siding with Jesper here. >> >>Given application of the 50 move rule and draws by repetition (which I think is >>sensible - if not strictly within the theoretical letter of the law), here is a >>simple reason why eventually chess search stops being exponential. Simply put: >> >>Beyond a certain depth of search, the number of extra nodes to be looked at with >>every additional search level will start to decrease, because an increasingly >>high proportion of the search tree branches will terminate in ended games. >> >>Having said that, with up to 49 moves between each pawn push or piece taken, the >>search tree is still going to be quite big - so while I agree with Jesper that >>the tree will eventually start to thin out, it's not actually offering us the >>prospect of solving chess by crunching out all possible games. >> >>-g > > >If you want to use that definition, fine. But then answer the following: > >Name one _real_ application that is not O(1) by your definition. IE by "real" >I mean a task that someone, some day, might want computed. It can't have >infinite input or it is impossible to compute, for example. If you think you >have one that has "unbounded but not infinite input" then post it. I'll bet I >can prove that it is not "unbounded" at all. > >waiting.... > >Bob The "impossible" constraint makes it quite difficult - my 1st thought was for computing Brownian motion! I think that the weather is finite and computable - the problem being that weather forecasters are very bad at guessing how quickly clouds will move - presumably because the input isn't good enough - you don't know the exact shape of the cloud - or how the cloud droplets are going to form to make these shapes. Fluid dynamics is an interesting area. Turbulence, flow, droplets etc - all very difficult. The problem here is that, in your simulation, you break the fluid into small chunks - but when you simulate movement, you must stretch these chunks, because you're not allowed to have holes in the fluid. This makes it difficult for even the most sophisticated simulators to properly emulate even relatively straightforward flows. The reason why IBM are building Deep Gene is because the simulation of emulating protein folding turns out to be harder that expected. Seems like almost every molecule in a folding protein can influence almost every other molecule during the process. Even Deep Gene may not be powerful enough. Anyway - I've just constructed a problem which meets most of your criteria - not 100% sure it's 0(1) though. I call it the "Chain Letter" problem. Letters in hyphens (-&-) are variables A group of -N- people form a social club. Every hour, on the hour, the members send each other chain letters by e-mail. Each member will send -B- new messages on the hour, where -N- > -B- > 0, and -B-is a random integer. For each message received, each member will forward it to -C- other members, where -N- > -C- > 0, and -C- is a random integer. The process continues for -A- hours. Your job, as club "facilitator", is to provide the computer power necessary to deliver all these messages. I think that you can clearly see that as -A- and -N- start to get large, whatever computers you provide are soon going to be very busy. For example, if there are 101 members, each could possibly receive 100 messages after the 1st hour, 10,100 after the second hour, over a million after the third hour, etc. If even a small number of people formed such a club, it would soon overwhelm the capacity of the entire internet. -g
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.