Thursday, January 20, 2005

Does a Chess Program have Free Will?

A non-CS Chicago Alum asked me a question about free will and computation. I passed the question to David McAllester, an AI professor at TTI, and he gave the following interesting reply.
The idea that I could be simulated on a computer seems at odds with my subjective experience of free will and my intuition that my future actions are not yet determined — I am free to choose them. But consider a computer program that plays chess. In actual chess playing programs the program "considers" individual moves and "works out" the consequences of each move. This is a rather high level description of the calculation that is done, but it is fair to say that the program "considers options" and "evaluates consequences". When I say, as a human being, that I have to choose between two options, and that I have not decided yet, this seems no different to me from the situation of a chess playing computer before it has finished its calculation. The computer's move is determined — it is a deterministic process — and yet it still has "options". To say "the computer could move pawn to king four" is true provided that we interpret "could do x" as "it is a legal option for the computer to do x". To say that I am free is simply so say that I have options (and I should consider them and look before I leap). But having options, in the sense of the legal moves of chess, is compatible with selecting an option using a deterministic computation. A chess playing program shows that a determined system can have free will, i.e., can have options. So free will (having options) is compatible with determinism and there is no conflict.


  1. I think the question could be more defined: Can a submarine swim?

  2. I'd have to agree with Scott's comment. McAllester's definition of free will seems to imply that a thrown rock has 'free will'. The rock has the 'option' of going one direction or another. Due to the angle and velocity at which it was originally thrown, the rock 'chose' to go in a particular trajectory. The chess program similarly has the 'option' of making one choice or another, but due to its program 'chooses' a particular one. I tend to favor a defintion of free will that does not include determined behavior.

    - Homin

  3. What then about a chess-playing program that chooses its most highly-valued move but chooses randomly when more than one such move exists? This has both choice and unpredictability. Is that sufficient for free will?

  4. "Inability of other agents to predict a probability distribution over future actions" seems ill-defined to me. Being able to predict depends on what information you have about the agent in question. Probability is a function of the predictor's belief about the agent, not the agent herself.
    A qubit(or even a classical bit) whose state I do not know is unpredictable to me; a chess program whose parameters I do not know is unpredictable in the same way.
    Moreover the notion of probability when applied to a unique non-repeatable event has issues, to say the least. On the other hand, statistically humans are quite predictable as well.

    (On a lighter note, is this is a sign of the computer's "free will":
    Internal Server Error
    The server encountered an internal error or misconfiguration and was unable to complete your request.)

  5. IMHO we don't know brain function well enough to answer this in detail. Have Penrose's theories of quantum-level involvement been scientifically (dis)credited?

    As far as I know, chess programs choose their opening moves "randomly" but play deterministically once they are out of "book" lines. Their choices *may* depend on the time settings for the game. I own Fritz8, a leading commercial PC program, but cannot find anything about this in its documentation.

    McAllester and I had an interesting exchange in the mid-1980s. He asked me how many moves I (an International Master, the rank below Grandmaster) typically consider in a position. I answered "usually 2 or 3", and he couldn't believe so low an answer. But chess machines are now so fast that they often alpha-beta prune out most options in the first few milliseconds. Maybe my brain takes some instants to "apprehend" every legal move in a position, and in that sense I "consider" them---though I'm not conscious of this. (I happen to believe that we do much useful thought in parallel subconsciously, part reason I have students read thru all of an exam before I give the signal to write.) So that distinction between my own mental experience and what I observe in chess programs has lessened.

  6. I agree that the non-deterministic definition of free will is problematic, but it is the correct one (as that it is how the word is used). Whether or not free will exists is a valid question, though if one were to follow Howell's reasoning, it'd be hard to justify any moral judgments.

    Howell's discussion of consciousness reminds me of David Chalmer�s work. While Howell seems to have a similar solution to Chalmer (expanding our notion of consciousness to include rocks), he only addresses the functional aspects of consciousness while ignoring the experiential. If you're interested in other viewpoints, Chalmers includes a pretty fair summary of opposing view points here.

  7. Whoops. Forgot to sign that.

    - Homin

  8. There's an excellent discussion on
    the notion of free will, using chess
    playing programs (and also Conways's
    game of life) to illustrate some
    concepts and arguments, in Daniel
    Dennett's book "Freedom Evolves"
    (2003). I recommend that book to
    anyone interested in these topics.