8 ms·
Deep blue(and basically no chess engines since the mid 50s) wasn't really doing brute-force search. It was using alpha-beta conspiracy search, a version of alph
by mtlmtlmtlmtl 3y ago
Deep blue(and basically no chess engines since the mid 50s) wasn't really doing brute-force search. It was using alpha-beta conspiracy search, a version of alpha-beta which was a novel idea at the time. And even alpha-beta itself is only brute-force under the worst possible move-ordering, which due to iterative deepening is basically never the case. It does give the same result as a truly brute-force minimax search, but by looking at roughly the square root of the number of positions naïve minimax would(under optimal move-ordering).
As for Russell-Norvig, it has maybe 2 or 3 pages on alpha-beta, and nothing on the almost 70 years of developments that have actually made it fast, able to use multiple threads, etc.
- bunderbunder 3y agoAnd, for what it's worth, I started college a couple years after Deep Blue beat Kasparov, and at the time this family of search algorithms were still being taught (and consumed a significant amount of classroom time) in the Artificial Intelligence class, not the algorithms class.