It's more the fact that Deep Blue showed significant insight and long-term planning. It's not immediately obvious to most people that human-like behaviours can arise directly from a game tree.
The problem with looking at just algorithm similarities is that every modern chess bot uses some variant of the same algorithm so the executable code will superficially look similar (negamax.) Computers aren't powerful enough to search the entire game tree, so you have to stop after a certain number of levels (15, for instance) and use a heuristic to evaluate the strength of that position.
The main differences between chess bots are found in that heuristic.
According to the actual report the heuristic is obviously based on Fruit's, which is what they're really angry about.
Humans haven't been able to compete against computers for quite a few years. Even a cheap netbook can plow through more levels of the game tree than Deep Blue could, and Deep Blue was even using custom hardware specifically designed for chess. It's not a simple case of a sore loser.
On the basis that he lost. Really. Kasparov thought Deep Blue was making moves that were too 'human-like,' and therefore it must have been fed moves from human players.
You see similar reactions from poker players. Humans don't want to believe that computers are capable of bluffing convincingly, but even simplistic alpha-beta poker bots are perfectly able to do it.
Big-Oh notation comes from real analysis, which is why the definition is given over functions with a real domain. Having potentially-real 'n' is also needed for certain important results in CS, such as the Smoothness Rule and the Master Theorem.
It's easy to see that the discrete case does not contradict the general definition: if the relation in the definition is true for some fractional x0, it must also be true for the natural number ceil(x0).
With respect to your oath, you shouldn't say that list insertion is linear in time, because it's untrue.:P "List insertion is O(n)" does not mean the same thing as "List insertion is linear in time." It roughly means "List insertion is not slower than linear in time." You need to use Big-Theta notation if you want to be precise when you're talking about algorithms.
You shouldn't feel bad about not understanding what Big-Oh means. Most people misuse it on the internet, so it may be difficult to learn correctly. You should be aware, though, that not knowing the differences between Big-Oh, Big-Theta and Big-Omega is a sign of an extremely weak background in theory. If you're interested in learning, at this level I usually recommend 'Introduction to The Design & Analysis of Algorithms' by Anany Levitin.
YES! O(1) is a subset of O(n), and I will give you a formal proof of this fact.
Recall, by definition, a function f(x) is in O(g(x)) iff there exists c positive real number and x0 real such that for all x>x0 |f(x)|<=c|g(x)|.
PROOF: Let f(x) be any function in O(1). By construction, and the above definition, there exists satisfactory c,x0 such that for all x>x0 |f(x)|<=c|1|=c. Let x1 = max{x0, 1}. n.b. x1>=x0 and x1>=1. It follows that for all x>x1 |f(x)|<=c<=c|x|. Therefore, there exists c positive real number and x1 real such that for all x>x1 |f(x)|<=c|x|. Therefore, by definition, f(x) is also in O(n).
f(x) in O(1) implies f(x) in O(n). This is the definition of a subset! O(1) is a subset of O(n).
Big Oh only says anything about the upper bound. It doesn't say anything about the lower bound. Any constant-time algorithm is in O(1), O(n), O(n^2), O(2^n), etc.
This mistake is the easiest way to figure out if someone doesn't really understand algorithms or complexity classes.
[1] The ptmalloc2, by the way, *urkel snort*, DOES use linked lists for everything. Like I said. The tree structure thing you mentioned? Complete bullshit, just like your remark about the origin of the term 'heap.'
No, ptmalloc2 stores all free chunks in (doubly-) linked lists. It sorts them into bins by size to improve speed and reduce fragmentation.
Your comment about 'vaguely correct semantics' is complete nonsense. Implementing malloc using linked lists is a good exercise for first year undergraduates; it's clear that such an idea works.
weak_ptr can't be used naively either. Keep in mind that a cycle of any size will prevent shared_ptr from functioning, and it may not be immediately obvious that this is a problem.
Do you remember college? Do you remember how many people in your cohort deliberately learned nothing, spent the whole time just drinking and playing video games on their daddy's money? Do you remember how many people were just plain stupid and couldn't understand no matter how hard they worked? Do you remember how many people were smelly, unshaven, socially lazy awkward people?
IIRC it was a lot more than 4.5%.
Is it really a surprise that they can't find work?
A lot of people don't like hearing this, especially here where the computer janitor types completely outnumber the software types, but people aren't all made equal. There will always be a demand for people who are genuinely skilled, qualified, motivated, and social.
w.r.t. finding free memory faster: A modern garbage collector pre-allocates memory in several large pages and condenses the free space to one end of these pages. Locating free space is worst-case Theta(n) in the number of pages - which is a small number, usually in the tens, and is stable and predictable. Malloc is worst-case Theta(n) in the number of free blocks, which is determined by a combination of malloc implementation details and usage (this is potentially all memory which is ever freed by the program.) Heap allocation in managed languages is indeed much faster than allocation in C or C++.
I didn't compare it to alternatives because that isn't the point of my post. The point is that C and C++ programs must* also "search through lists regularly" during memory management, which obviates whatever complaint against garbage collection you were trying to make. No offense, but you really don't come off as understanding this problem as well as you want to.
(*or trade it for, I think, Theta(2^k) extra memory, where k is the number of bits in the largest block that can be allocated. If that sounds wise.)
I've never taken a "programming course." It sounds ghastly.
That's why people focus on memory management when they talk about C++: it's filled with 'gotchas' that will completely fuck you up if you don't completely understand everything you are doing. That's why so many C++ 'fans' hate automatic memory management. It's not because they're attached to the idea of manual memory management, it's because C++ forces you into a culture of paranoia and it's difficult to adjust to a world where the standard library isn't out to kill you.
What do you think malloc does? The C heap is a linked list. Libc has to do a worst-case Theta(n) search on a linked list for free space on allocation. Depending on your implementation, it may even wait until an allocation fails before it compacts the heap - causing a several second or minute pause in the middle of a malloc call.
If you haven't written software big enough to see the disadvantages of malloc, you haven't written software big enough that you should care about the cost of a GC.
Don't worry. There are lots of places on the internet for 24 year old basement dwellers to talk about childrens' toys and Japanese childrens' television.
The main vector of attack in WebGL is through shaders. Silverlight doesn't support shaders (it only supports the Reach profile,) which - for better or for worse - means it really is more secure.
XNA doesn't have a particularly good OpenGL implementation? As someone with years of experience with XNA, Direct3D, OpenGL, and even some experience with WebGL, I feel ethically responsible for saying that you have absolutely no idea what you're talking about at all.
Slashdot Mirror
It's more the fact that Deep Blue showed significant insight and long-term planning. It's not immediately obvious to most people that human-like behaviours can arise directly from a game tree.
The problem with looking at just algorithm similarities is that every modern chess bot uses some variant of the same algorithm so the executable code will superficially look similar (negamax.) Computers aren't powerful enough to search the entire game tree, so you have to stop after a certain number of levels (15, for instance) and use a heuristic to evaluate the strength of that position.
The main differences between chess bots are found in that heuristic.
According to the actual report the heuristic is obviously based on Fruit's, which is what they're really angry about.
Humans haven't been able to compete against computers for quite a few years. Even a cheap netbook can plow through more levels of the game tree than Deep Blue could, and Deep Blue was even using custom hardware specifically designed for chess. It's not a simple case of a sore loser.
On the basis that he lost. Really. Kasparov thought Deep Blue was making moves that were too 'human-like,' and therefore it must have been fed moves from human players.
You see similar reactions from poker players. Humans don't want to believe that computers are capable of bluffing convincingly, but even simplistic alpha-beta poker bots are perfectly able to do it.
Big-Oh notation comes from real analysis, which is why the definition is given over functions with a real domain. Having potentially-real 'n' is also needed for certain important results in CS, such as the Smoothness Rule and the Master Theorem.
It's easy to see that the discrete case does not contradict the general definition: if the relation in the definition is true for some fractional x0, it must also be true for the natural number ceil(x0).
With respect to your oath, you shouldn't say that list insertion is linear in time, because it's untrue. :P "List insertion is O(n)" does not mean the same thing as "List insertion is linear in time." It roughly means "List insertion is not slower than linear in time." You need to use Big-Theta notation if you want to be precise when you're talking about algorithms.
You shouldn't feel bad about not understanding what Big-Oh means. Most people misuse it on the internet, so it may be difficult to learn correctly. You should be aware, though, that not knowing the differences between Big-Oh, Big-Theta and Big-Omega is a sign of an extremely weak background in theory. If you're interested in learning, at this level I usually recommend 'Introduction to The Design & Analysis of Algorithms' by Anany Levitin.
YES! O(1) is a subset of O(n), and I will give you a formal proof of this fact.
Recall, by definition, a function f(x) is in O(g(x)) iff there exists c positive real number and x0 real such that for all x>x0 |f(x)|<=c|g(x)|.
PROOF: Let f(x) be any function in O(1). By construction, and the above definition, there exists satisfactory c,x0 such that for all x>x0 |f(x)|<=c|1|=c.
Let x1 = max{x0, 1}. n.b. x1>=x0 and x1>=1. It follows that for all x>x1 |f(x)|<=c<=c|x|. Therefore, there exists c positive real number and x1 real such that for all x>x1 |f(x)|<=c|x|. Therefore, by definition, f(x) is also in O(n).
f(x) in O(1) implies f(x) in O(n). This is the definition of a subset! O(1) is a subset of O(n).
Q.E.D.
Indeed, any algorithm in O(1) is also in O(n).
Have you really never needed, for example, a linked data structure that could form a cyclic graph?
O(1) is a subset of O(n).
Big Oh only says anything about the upper bound. It doesn't say anything about the lower bound. Any constant-time algorithm is in O(1), O(n), O(n^2), O(2^n), etc.
This mistake is the easiest way to figure out if someone doesn't really understand algorithms or complexity classes.
[1] The ptmalloc2, by the way, *urkel snort*, DOES use linked lists for everything. Like I said. The tree structure thing you mentioned? Complete bullshit, just like your remark about the origin of the term 'heap.'
Nobody is stupid enough to write an O(n) malloc?
You realize that any algorithm in O(1) is also in O(n), right?
Don't lecture people about complexity theory until you understand it. Or anything else, for that matter.
The bins ARE linked lists.
Stop embarrassing yourself: read Knuth, read the source code, stop making up shit.
No, ptmalloc2 stores all free chunks in (doubly-) linked lists. It sorts them into bins by size to improve speed and reduce fragmentation.
Your comment about 'vaguely correct semantics' is complete nonsense. Implementing malloc using linked lists is a good exercise for first year undergraduates; it's clear that such an idea works.
Donald Knuth disagrees with you. He knows his history better than either of us.
Actually many shipping malloc implementations use linked lists, such as dlmalloc and ptmalloc2, upon which the glibc implementation is based.
weak_ptr can't be used naively either. Keep in mind that a cycle of any size will prevent shared_ptr from functioning, and it may not be immediately obvious that this is a problem.
Yes, 4.5% of US engineers are unemployable.
Do you remember college? Do you remember how many people in your cohort deliberately learned nothing, spent the whole time just drinking and playing video games on their daddy's money? Do you remember how many people were just plain stupid and couldn't understand no matter how hard they worked? Do you remember how many people were smelly, unshaven, socially lazy awkward people?
IIRC it was a lot more than 4.5%.
Is it really a surprise that they can't find work?
A lot of people don't like hearing this, especially here where the computer janitor types completely outnumber the software types, but people aren't all made equal. There will always be a demand for people who are genuinely skilled, qualified, motivated, and social.
It's called a heap because it's a messy pile of junk. The heap data structure has nothing to do with it.
I've already explained twice.
w.r.t. finding free memory faster: A modern garbage collector pre-allocates memory in several large pages and condenses the free space to one end of these pages. Locating free space is worst-case Theta(n) in the number of pages - which is a small number, usually in the tens, and is stable and predictable. Malloc is worst-case Theta(n) in the number of free blocks, which is determined by a combination of malloc implementation details and usage (this is potentially all memory which is ever freed by the program.) Heap allocation in managed languages is indeed much faster than allocation in C or C++.
I didn't compare it to alternatives because that isn't the point of my post. The point is that C and C++ programs must* also "search through lists regularly" during memory management, which obviates whatever complaint against garbage collection you were trying to make. No offense, but you really don't come off as understanding this problem as well as you want to.
(*or trade it for, I think, Theta(2^k) extra memory, where k is the number of bits in the largest block that can be allocated. If that sounds wise.)
I've never taken a "programming course." It sounds ghastly.
Boost/0x shared_ptr can't handle circular references.
That's why people focus on memory management when they talk about C++: it's filled with 'gotchas' that will completely fuck you up if you don't completely understand everything you are doing. That's why so many C++ 'fans' hate automatic memory management. It's not because they're attached to the idea of manual memory management, it's because C++ forces you into a culture of paranoia and it's difficult to adjust to a world where the standard library isn't out to kill you.
What do you think malloc does? The C heap is a linked list. Libc has to do a worst-case Theta(n) search on a linked list for free space on allocation. Depending on your implementation, it may even wait until an allocation fails before it compacts the heap - causing a several second or minute pause in the middle of a malloc call.
If you haven't written software big enough to see the disadvantages of malloc, you haven't written software big enough that you should care about the cost of a GC.
Don't worry. There are lots of places on the internet for 24 year old basement dwellers to talk about childrens' toys and Japanese childrens' television.
Or those Americans who arrest the foreign owners of legal gambling sites.
Right, my mistake. I was thinking of WP7.
The main vector of attack in WebGL is through shaders. Silverlight doesn't support shaders (it only supports the Reach profile,) which - for better or for worse - means it really is more secure.
XNA doesn't have a particularly good OpenGL implementation? As someone with years of experience with XNA, Direct3D, OpenGL, and even some experience with WebGL, I feel ethically responsible for saying that you have absolutely no idea what you're talking about at all.