Anmerkungen zum Algorithmus

Der ursprüngliche Algorithmus

basierte auf der generellen Idee, jeweils immer eine solche Kombination abzufragen, die den Suchraum, d.h. die Zahl der verbleibenden Möglichkeiten, maximal reduziert. Außerdem sollten nur solche Kombinationen abgefragt werden, die nach Lage der bisherigen Antworten noch möglich sind. Das ist eine diskutierbare Einschränkung, weil es zwar einerseits eine bessere Chance auf einen direkten Treffer bietet, anderseits aber evtl. Informationen verschenkt.

Das Verfahren beginnt mit einer zufälligen Frage und benutzt dann die Antworten, um aus dem Suchraum (anfangs 7^4==2401) die nicht mit diesen Antworten verträglichen Kombinationen herauszuwerfen.  Dann wird für jede der verbleibenden Kombination und jede mögliche Antwort errechnet, auf welche Größe der Suchraum damit reduziert würde und für jede Kombination das Maximum dieser Größen bestimmt. Schließlich wird dann diejenige Kombination als Frage ausgewählt, welche - unabhängig von der Antwort, den Suchraum in der nächsten Runde minimiert.

Auf meinem ersten Computer, einem selbst zusammengelöteten Nascom II  - ein aus Grossbritannien importierter Einplatinencomputer basierend auf einer 4Mhz-Z80-CPU, 32 KByte RAM, einem internen TV-Interface und einem Microsoft-Basic in einem 8KByte-ROM - habe ich das mit dem Assembler in etwa 3KByte implementiert und konnte damit ein 5*8-Spiel spielen. Nur für die erste Frage musste ein Zeitlimit eingeführt werden.

Wie bereits an anderer Stelle erwähnt, wäre dies mit einem 16F84 nicht realisierbar gewesen.

Ein minimaler Algorithmus für PIC-Prozessoren

Ein PIC16F84 hat 1024 Worte Programm-ROM, 68 Byte RAM und 64 Byte EEPROM. Letzterer kann zwar vom Programm aus gelesen und geschrieben werden, ist für unsere Zwecke aber viel zu langsam und zu empfindlich.  Ein Teil des RAM wird für Buchführung, Kommunikation usw. benötigt, so daß nicht einmal genügend Platz für das Abspeichern des Suchraums eines trivialen 4*3-Spieles verhanden ist.

Also wählte ich einen anderen Ansatz. Statt den möglicherweise recht großen Suchraum zu berechnen und dann zu reduzieren, speichere ich die Antworten und berechne die verbleibenden Möglichkeiten jedesmal aufs Neue. Ein lustiger Nebeneffekt ist, daß im Gegensatz zum obigen Verfahren, welches mit jeder Frage schneller wird, dieses hier immer langsamer wird.

Bei einem 4*7-Spiel (vier Stellen, sieben Farben resp. Ziffern) läßt sich eine Antwort in drei Bytes unterbringen und es werden etwa fünf Fragen benötigt. Das läßt also noch Spielraum. Auf der anderen Seite benötigt das Programm sowohl den Programmspeicher (Flash-ROM) als auch RAM fast vollständig, weil temporäre und weitere Variablen, z.B. für die Ansteuerung von Tasten und Display, ebenfalls Platz benötigen. In gewisser Weise hatte der 16F84 genau die richtige Größe für diese Art von Problemstellung.