Wie hat ein Schachprogramm in 4kB Speicher Platz?

... komplette Frage anzeigen

3 Antworten

Bei so etwas muss man natürlich immer Kompromisse eingehen. Von daher denke ich, dass die 64 Felder als Nibbles abgespeichert werden, die einen 4 Bit Index für die darauf stehende Figur enthalten. Darin finden alle 6 Figuren, "leeres Feld" und sogar noch ein zusätzlicher Zustand platz. Demnach reichen 32 Byte um das gesamte Spielfeld abzubilden.

Wenn man hingegen die Spielfiguren als Index verwendet, kommen wir auf 32 Figuren mit einem von 8x8=64 möglichen Positionen, der sich in 6 Bit darstellen lässt. Wenn man es jetzt drauf anlegt und sich für Bitschubserei nicht zu schade ist, benötigt man noch 24 Byte plus 4 Byte als Flags, ob die Figur sich auf dem Brett befindet, oder nicht. Insgesamt landen wir also bei 28 Byte, allerdings dürfte der Bit-Schubs-Code den Vorteil gegenüber ersterer Methode auffressen.

Auch wenn man heute noch Mikrocontroller programmiert, stehen ja oft nicht mehr als 512 Byte ROM oder 32 Byte RAM zur Verfügung. Und selbst damit kann man erstaunliche Dinge bauen!

Außerdem vergessen viele, dass man auch am Computer Assembler-Software in weit unter einem KB schreiben kann, z. B. einen ganzen Webserver (hab ich mal in unter 500 Byte geschafft). Oder schau dir mal die ganzen Demo-Szene Intros an.

Für mich klingen 4KB ROM und 256 Byte RAM jetzt nicht sooo katastrophal wenig, aber ich komme auch aus dem embedded Bereich. Trotzdem, interessant und bemerkenswert ist deine neue Errungenschaft schon! Da hast du dir ein schickes Teil geangelt! :)

Die Eröffnungsbibliothek ist eher klein - die Software ist auch nicht besonders spielstark.

Ansonsten kann man sagen: die Software für den Z80 (A) wurde überwiegend in Maschinensprache programmiert. In Maschinensprache bekommt man mit extrem wenig Platz ziemlich viel hin - besonders wenn man auf sehr spezialisierter Hardware ablaufen lässt.

Mehr info gibt es hier: http://chessprogramming.wikispaces.com/

Es gab noch kleinere Rechner damals. Zum Beispiel der LC80 mit 2kb ROM und 1kn RAM.

Und 64 Felder mit 32 Figuren in nur 256 Bytes RAM zu speichern?

Wenn ich die 32 Figuren jeweils einem Byte zuordne, dann reichen 6 Bit aus für die Positionsbestimmung. D.H. es reichen 32 Byte vollkommen aus für 64 Felder und 32 Figuren. Ich hätte es aber andersherum programmiert (so wurde es vermutlich auch gemacht): 64 Byte für jedes Feld und darin die Information was da drauf steht (reichen 5Bit)

Wie war/ ist es möglich, ein doch einigermassen komplexes Schachprogramm in nur 4kB ROM zu programmieren?

Sowas muss nicht unbedingt komplex sein. Für Spiele kann man Beispielsweise auch nach Belobigungen gehen. Man muss das System nur anlernen. Das wurde wahrscheinlich vorher gemacht und dann auf ein ROM geschmissen.

Was möchtest Du wissen?