From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Fri Jan 28 2005 - 08:46:09 MST
Russell Wallace wrote:
>
> Let I(P) = the best way to solve problem P given infinite computing power.
>
> Let L(P) = the best way to solve problem P given limited computing
> power; for the sake of definiteness, say a nanotech supercomputer,
> which is the most we can plausibly hope to get our hands on in the
> foreseeable future.
>
> Consider chess as an example.
>
> We know what I(chess) is: the minimax function.
Not so. Minimax is I(chess) only against another minimax I(chess)
opponent. Suppose chess is a win for black under minimax I(chess). A
*smart* and infinitely powerful player playing white might still win,
against a non-I-chess but superintelligent opponent, by predicting which
moves for white were likely to lead to mistakes for black (moves off the
sure-win game tree) given knowledge of black's algorithm, even if minimax
I(chess) would lose against that superintelligent opponent.
> What about L(chess)? We have good candidates in the form of a
> collection of very strong chess programs. What do they look like?
> Essentially tweaks (alpha-beta, iterative deepening, NegaScout etc) to
> the minimax function.
>
> Maybe there's some very clever algorithm that could beat Deep Blue
> while not relying much on minimax, but there's no evidence for such a
> thing thus far, and my guess for what it's worth is that there isn't
> any such.
Eh? Kasparov did beat Deep Blue in at least some games, if I recall
correctly. Kasparov's algorithm is not a mere tweak of minimax, even if it
distantly shares some structural features.
> So I'll conjecture that L(chess) ~= I(chess).
I strongly disagree! There's a tremendous amount of exploitable structure
in the game of chess that is not exploited by modern algorithms. Kasparov
nearly fought Deep Blue to a standstill, exploring fewer than 2 moves per
second to Deep Blue's 2 billion! That's a hell of an efficiency
improvement from searching Patterns in the Tree of Chess, versus searching
the mere Tree of Chess.
-- Eliezer S. Yudkowsky http://intelligence.org/ Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Tue Feb 21 2006 - 04:22:52 MST