Infinite and limited computing power

From: Eliezer S. Yudkowsky (
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                
Research Fellow, Singularity Institute for Artificial Intelligence

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:50 MDT