3

I'm wondering about the following issue. I obviously don't expect any practical solutions but I would appreciate any developer's thoughts on this:

Would it be theoretically possible to have a program that opens other programs (for the sake of argument let's say it opens .exe files), and determines whether or not a particular executable, when executed (with fixed input and machine state), plays a game of chess (amongst whatever other tasks it may perform).

With 'play chess' I mean having some representation of a chess board and pieces, applying subsequent moves for black and white originating from a built-in chess AI engine.

Such a theoretical 'chess detection program' may contain a Virtual Machine or PC emulator or whatever to actually simulate the scanned executable if necessary. We can assume it runs on an arbitrarily fast computer with ditto ram.

(Edit) Regarding the halting problem, I can solve that like this:

Load the program in a virtual machine, which has N bits (harddisk and memory space and CPU registers altogether). This virtual machine can assume at most 2^N different states.

Execute the program in the VM step by step. After each step, check if it halted. If yes: problem solved (result: yes, it halts). If no: take the current state of the virtual machine, and see if this state exists in a list of states we've already encountered before. If yes: problem solved (result: no it will run forever). If no: add this state to the list and continue.

Since there are at most 2^N different states that can occur, this algorithm will determine whether the program halts or not with certainty in finite time.

(Edit2) There seems to be some ambiguity about the (in)finiteness of the scanned executable or the (virtual) machine it runs on. Let's say the executables to be scanned may be at most 1 GB (which should be enough since most chess programs are considerably smaller) and they're supposed to run on a PC (or VM) with 10 GB of ram.

Our theoretical chess detector program can use an arbitrary amount of ram.

Sheldon Pinkman
  • 1,086
  • 4
  • 15
  • 21
  • Write a program that detects programs which can detect chess programs. Then create random .exe files on your arbitrarily fast computer and wait till it it detects the exe you are looking for. (and no, it's not possible) – Karoly Horvath Nov 29 '11 at 22:34
  • Why not? (regardless of the fact that a chess detector detector is most likely even more difficult than a chess detector) – Sheldon Pinkman Nov 29 '11 at 22:54
  • _IF_ what you are trying to do is catch cheaters, then why would you care about figuring out if "exe" executables can play chess. Instead, scan _currently running_ programs in memory which gives you a snapshot of each program and is much easier to deal with and doesn't reduce to the halting problem. – ldog Nov 29 '11 at 23:30
  • That's not what I had in mind, but it sounds interesting. How would you go about determining whether a currently running program is playing chess? (indeed regardless of whether it will ever halt or not) – Sheldon Pinkman Nov 29 '11 at 23:34
  • You can do stuff like look for a bit board representation in memory. http://en.wikipedia.org/wiki/Bitboard The plus side of this is that bitboards generally take up somewhat large chunks of contigous memory each piece being 64 bit (1 bit per square on the board) with some set of moves encoded in the 64 bit word. – ldog Nov 29 '11 at 23:55
  • With limited resources the halting problem is solvable in theory and hence such a chess program is possible. As long as you introduce any limit on executable size/input/states, all the paradoxes of the halting problem disappear (hint: Cantors diagonlization needs infinity). If you only look at n programs take a program that directly matches these and outputs true or false depending on which one it is. One of these will be your chess checking programs. Also look here: http://stackoverflow.com/questions/8264468/writing-a-program-that-writes-a-program/8267088#8267088 – LiKao Nov 30 '11 at 10:01

4 Answers4

7

No, there is no such algorithm that can detect whether an executable plays chess.

The proof of this rests in the fact that the following problem (called the halting problem) cannot be solved by any algorithm:

Given a computer program, does that program eventually terminate?

We can show that if there was a computer program that could determine whether or not another program plays a game of chess, we could solve the halting problem. To do so, we would write a computer program that does the following:

  1. Take as input some other computer program P.
  2. Run program P.
  3. If program P terminates, play a game of chess.

This program has the following interesting behavior: it plays a game of chess if and only if the program P terminates. In other words, if we could detect whether this program could play chess, we would be detecting whether or not the program P terminates. However, we know that this is provably impossible to do, so there must be not be a program that detects whether some computer program plays chess.

This general approach is called a reduction from the halting problem and can be used to show that a huge number of different problems are probably unsolvable.

Hope this helps, and sorry for the "no" answer!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    I don't think this line of reasoning works. Suppose our question is "can we determine whether the square root of 9 is 3". Now write a computer program with steps 1 and 2 above, replacing step 3 with "If program P terminates, divide 9 by 3 and test whether the result is equal to 3". In fact, your 3-step test of chess-playing ability does not even take as input a program PC that is a program to be tested for chess-playing ability. – phoog Nov 29 '11 at 22:48
  • 2
    @phoog: *"your 3-step test of chess-playing ability does not even take as input a program [..] to be tested for chess-playing ability."* - I think you misread. He is *describing* the program to input to our chess-detection-oracle. If such a chess-detection-oracle existed, it would have to solve the halting problem to determine if the above program ever plays chess. – BlueRaja - Danny Pflughoeft Nov 29 '11 at 23:00
  • @BlueRaja-DannyPflughoeft Aha, of course, thanks for setting me straight. – phoog Nov 29 '11 at 23:05
4

In regards to your edited question: yes, if we limit the size of the memory so we only have finitely-many possible programs, we could theoretically enumerate every possible program and manually divide them into "chess-playing" and "non-chess playing" by whatever set of criteria you wanted.

In this case, we'd no longer have a Turing machine, so the Halting Problem doesn't apply. Instead, we'd have a finite state machine (and yes, this means in the real world, all computers are actually finite-state approximations of a Turing machine).

However, you added this limitation because you wanted to be "practical, not theoretical," so here's another bit of practicality for you: to enumerate all of the 256-bit programs (with a billion PCs, each of which enumerate a billion programs a second) would take significantly longer than the age of the universe to complete. You can hardly imagine, then, how long it would take to enumerate all programs less than 1 GB (~1,000,000,000-bits).

Because of this, it is actually more practical to model real computers as Turing machines than as finite-state machines; and under this model, as @templatetypedef proved, it is impossible.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • Agreed about the impractical aspects of the ridiculous numbers we're dealing with. It was just theoretical, I just added the limit to ensure we're dealing with finite state machines (thanks for clarifying that term). But right now I'm wondering: can we actually determine objectively if a given program plays chess or not? I mean, it can be hidden in so many layers of abstraction that we wouldn't recognize it as chess at all. – Sheldon Pinkman Nov 30 '11 at 00:13
1

No. This is equivalent to the halting problem.

phoog
  • 42,068
  • 6
  • 79
  • 117
  • Note my edit above about the halting problem. I think the original halting problem is about detecting programs that can run on an *infinite* computer. That doesn't apply here. – Sheldon Pinkman Nov 29 '11 at 23:01
  • But there's an infinite number of ways to represent a chess game using a sequence of bits. – phoog Nov 29 '11 at 23:03
  • Does it help if we limit the executables to be checked? (see edit2 above) – Sheldon Pinkman Nov 29 '11 at 23:15
  • Even if you consider only bit sequences of finite length, you still have an infinite number of ways to interpret each sequence. For example, how do you know whether 1000001 represents the integer 65 or the ASCII character 'A' or perhaps the signed 7-bit integer -63 or perhaps the character 'k' in some unknown encoding scheme or perhaps two 6-bit indices into a 64-element array representing a chess board or perhaps a segment of a bitmap image or... – phoog Nov 30 '11 at 17:34
0

What does it mean that a program plays chess? I don't believe there exists a precise mathematical definition of the problem that couldn't be gamed and wouldn't be trivially equivalent to an untreatable problem.

For example, if you ask "Does there exist an encoding of moves under which this program plays chess?" then a bare Python interpreter plays chess - under the encoding that stipulates that you need to input:

  • a chess-playing Python program plus opponent's first move if you want it to play black
  • a chess-playing Python program if you want it to play white

If you fix the encoding, then the problem becomes boring. Chess games are finite (by the 50-move rule), so the only hard question is "does this program hang between moves on any of the finite set of chess games". If it doesn't and always respects the encoding (and makes valid move, all this is trivial to check) then it plays chess. Of course checking if it hangs is untreatable. Enumerating all chess games is treatable but of course also totally impossible given practical considerations.

Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90