Saitek Simultano - eine Rechenaufgabe
 

Hallo,

beim Bearbeiten des Wikis und Lesen im Forum stößt man ja zwangsweise auf lustige Informationen

Hier mal Angaben aus dem Wiki:

Saitek Simultano
Prozessor 65C02
ROM 64 KByte
RAM 8 KByte
Eröffnungsbibliothek 100.000 Halbzüge

Wer findet die Fehler?

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

64000 ByteRom und 100000 Eröffnungspositionen hört sich fantastsisch an... ;)

Beste Grüße
Jürgen

AW: Saitek Simultano - eine Rechenaufgabe
 

Ossi Weiner sprach hier vor vielen Jahren schon von der "Wundersamen Zugvermehrung"!

Und mir persönlich kamen die Angaben zur Bibliotheksgröße der Schachcomputer schon immer irgendwie zu groß vor denn in der Praxis spielten die Geräte einfach viel weniger Eröffnungen aktiv als angegeben und ich fragte mich wo stecken nur die Zigtausend Eröffnungszüge? Nur Beweisen konnte man als Laie schwerlich etwas, aber das ist jetzt dank Carsten vorbei!

Grüße
Otto

AW: Saitek Simultano - eine Rechenaufgabe
 

Hallo Carsten,

das Problem an der Sache, diese Angaben waren offizielle Herstellerangaben.

Wir hatten das Thema ja schon per PN besprochen. Wenn du gegenteilige, verifizierbare Fakten liefern kannst, z.B. deine ausgelesenen Bibliotheken, dann sollten aber genau diese offiziellen Werbeaussagen trotzdem im Wiki erhalten bleiben. Allerdings z.B. mit dem Zusatz "lt. Werbeprospekt" versehen, um die Diskrepanz zwischen Fiktion und Wahrheit aufzuzeigen.

Gruß
Micha

AW: Saitek Simultano - eine Rechenaufgabe
 

Ich habe mit den Hersteller-Angaben kein Problem. Denn in irgendeiner Weise (höhere Zahl durch Mehrfachzählung) muss es sich ja niederschlagen, ob ein Gerät innerhalb der Bibliothek Zugumstellungen erkennt oder nicht.

Gruß
Wolfgang

AW: Saitek Simultano - eine Rechenaufgabe
 

Kreative Zählweise, das war damals üblich.

Nehmen wir mal die folgenden Varianten her:
e2-e4 e7-e5 Sg1-f3 Sg8-f6
e2-e4 e7-e5 Sg1-f3 Sb8-c6

Nach meiner Zählweise liegen hier 5 Züge Umfang vor. Die Hersteller hätten seinerzeit aber behauptet, es seien 8. Wenn man nun Varianten hat, die sich erst bei deutlich tieferen Zügen unterscheiden, dann kann man mit der "kreativen" Zählweise nahezu jeden angeblichen Umfang erreichen.

AW: Saitek Simultano - eine Rechenaufgabe
 

Hallo Rasmus,

Ja, das ist schon klar und das hatten wir ja schon öfter mal diskutiert.

Da aber scheinbar niemand erkennt, worauf ich eigentlich mit dem Post hinaus wollte, werde ich mal zwei Fragen formulieren und bitte mal um möglichst viele Antworten :)

Der 65C02 hat einen Adressraum von 64 KByte (65536 Bytes). Das ROM ist lt. Angabe 64 KBytes groß.

1. Frage: wo liegt dann der 8 KByte RAM Bereich?

Ihr seit Programmierer und sollt eine Eröffungsbibliothek erstellen, die nur die beiden folgenden Varianten enthällt:

• Variante 1: e2-e4 Sg8-f6 (die Züge sollen aktiv gespielt werden)
• Variante 2: h2-h3 e7-e5 (h2-h3 soll nicht aktiv gespielt werden)

2. Frage: wieviel Speicherplatz würdet ihr dafür benötigen?

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Das könnte man mit bank switching machen. Der Commodore 128 muß das ähnlich gelöst haben, um mit dem 6502 128k RAM adressieren zu können.

Eine denkbare Aufteilung wäre etwa, das RAM nach unten zu legen, dann den Code, und z.B. die letzten 8K des Adreßraumes switchbar über den ROM-Teil mit dem Eröffnungsbuch zu legen. Das wäre dann im Zugriff zwar langsam, wäre aber nur zum Lookup nötig und würde die eigentliche Suche nicht ausbremsen.

Wenn ich die Cache-Indices weglasse, 25 Bytes. 4 davon für die Länge des Eröffnungsbuches, was man beim 6502 aber auch mit einem uint16_t machen könnte, dann wären es noch 23 Bytes.

Allerdings ist mein Format nicht besonders speichersparend, weil beim Cortex-M4 mehr als genug ROM vorhanden ist. Für 22283 unterschiedliche Züge in 12563 unterschiedlichen Positionen mit 256 Cache-Indices werden 108425 Bytes benötigt. Die "rohe" Anzahl der Züge liegt übrigens bei 128258, also vor der Bereinigung um Zugumstellungen.

Bei der Skalierung ergeben sich damit 4.87 Bytes pro einzigartigem Zug, bzw. 0.86 Bytes pro Zug in "kreativer" Zählweise. Wenn ich die Positionen statt mit einer CRC-32 und einer CRC-8 nur mit CRC-16 und CRC-8 machen würde, wären das 2 Bytes pro Position weniger, was 25k sparen würde, und ohne Cache-Indices (1k weniger), dann wären es 3.7 bzw. 0.64 Bytes pro Zug.

Mit letzterem wäre man bei 100.000 Zügen vor Zugumstellung dann bei 64k, das ist die richtige Größenordnung. Nimmt man nun noch an, daß das Verhältnis aus Roh-Zählweise zu bereinigter Zählweise beim Simultano deutlich höher ist, weil das Buch auf Tiefe und nicht wie bei mir auf Breite zielt, dann wären auch 32k Buch durchaus machbar.

AW: Saitek Simultano - eine Rechenaufgabe
 

Hi Rasmus,

Die Frage war natürlich für 6502 Architektur gedacht. Da sind 25/23 Bytes aber sehr viel.

Wer kommt mit weniger aus?

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Ich denke, die Frage ist nicht sinnvoll gestellt, weil bei so einem kleinen Buch mit nur 1 aktivem Zug pro Position das Meiste für den strukturellen Overhead draufgeht, den man für die Ausweitung auf ein richtiges Eröffnungsbuch bräuchte. Meine Kalkulation mit 3.7 Bytes pro realem Zug käme hier auf 15 Bytes.

Noch weniger Speicher wäre natürlich 8 Bytes:
e2-e4 (2 Bytes) Sg8-f6 (2 Bytes)
h2-h3 (2 Bytes) e7-e5 (2 Bytes)

Da man 64 Felder hat, brauchen Start- und Zielfeld 6 bit, wodurch man eines der Bits reservieren kann, um anzuzeigen, ob der Zug aktiv gespielt werden soll oder nicht.

Dann sind aber keine Zugumstellungen mehr möglich, aber das war ja offenbar auch nicht in der Frage enthalten.

AW: Saitek Simultano - eine Rechenaufgabe
 

Hallo Rasmus,

Das sehe ich natürlich etwas anders ...

Demnach hätten Rechner wie der Mephisto MM V + HG550 kein "richtiges Eröffnungsbuch" ...

Das ist natürlich schon besser, ist aber noch erheblich mehr, als das was beispielsweise MM V und Konsorten benötigen.

Die wäre auch noch möglich, nur nicht mehr direkt und etwas umständlicher. Aber wenn es auf Speicherplatz ankommt ...

So, jetzt noch einen Versuch und dann sind wir glaube ich am Ziel

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Die Bauernzüge könnte man auch mit einem Byte machen, indem man bei normalen Zieh-Zügen nur das Zielfeld angibt. Dafür wäre nebst dem "aktiver Zug"-Bit ja noch ein weiteres Bit verfügbar, mit dem man anzeigen kann, daß es sich um so einen Bauernzug handelt.

Das ergäbe 5 Byte:
e4 (1 Byte) Sg8-f6 (2 Bytes)
h3 (1 Byte) e5 (1 Byte)

Der Nachteil ist, daß man mit dem System erhebliche Teile des Buches durchparsen muß, um die Zugumstellungen zu erwischen.

AW: Saitek Simultano - eine Rechenaufgabe
 

Schon nah dran. MM V / HG 550 und Konsorten benötigen für obiges Buch genau 4 Bytes. Immerhin nochmal 20% weniger als 5 Bytes.

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Ok, bei Sg8-f6 kann man natürlich denselben Trick machen, weil es nur einen Springer gibt, der nach f6 gehen kann. Das spart dann das fünfte Byte.

AW: Saitek Simultano - eine Rechenaufgabe
 

Ok. Nächste Stufe:
Zwei Varianten
Erste: e2-e4,Sg8-f6,d2-d4,Sf6xe4,Lf1-c4 (soll aktiv gespielt werden)
Zweite: d2-d4,Sg8-f6,c2-c4,e7-e6,Sb1-c3 (soll nicht aktiv gespielt werden.

MMV bräuchte dafür 10 Bytes.

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Mindestens 512 Byte werden im Bereich 0x0000 bis 0x0200 liegen, eventuell auch alles RAM in den ersten 8 KByte. Das liegt an der Besonderheit der 6502, bei der Z80 wäre es anders, das RAM würde oben im Speicher liegen.

Das Rom hingegen dürfte teilweise parallel liegen. Dazu wird Bankswitching verwendet, d.h. der Speicher ist in einzelne Bänke unterteilt und diese werden wechselnd in den Adressraum der CPU eingeblendet. Bei der Eröffnungsbibliothek kann z.B. die Bewertungsfunktion ausgeblendet werden - es wird entweder der Zug aus dem Buch gespielt ODER mit der normalen Suche ermittelt.

Ich würde hier mit 8 Byte rechnen: Jeder Zug wird mit 2 Byte dargestellt, 12 Bits für von und nach und 4 Bits für Steueraufgaben wie Variantenende, nur passiv oder selten spielen usw.

Es gibt auch andere, kompaktere Möglichkeiten, aber die brauchen mehr RAM und das war meist knapper als ROM.

AW: Saitek Simultano - eine Rechenaufgabe
 

Mit 8 Bytes liegt die Lösung 100% über kompaktesten Lösung.

Stay tuned ...
Carsten

BTW: Das ein Bankswitching gemacht werden kann ist klar. Aber wird das beim Simultano auch gemacht? Ich habe da leichte Zweifel und hätte dazu gerne mehr gewusst.

AW: Saitek Simultano - eine Rechenaufgabe
 

Ich passe aus Faulheit, würde aber sagen, daß bei ehrlicher Zählweise zwischen 10% und 20% von den Marketing-Angaben des Zugumfanges real übrig bleiben, was dann auch in die 64k ROM paßt.

AW: Saitek Simultano - eine Rechenaufgabe
 

Was ist für Dich die kompakteste Lösung?
Ich kenne die Speicherung der Zugnummer durch einen Zuggenerator, der das Feld abscannt und deshalb immer dieselbe Reihenfolge liefert (bei Figurenlisten schon nicht mehr gegeben bzw. es braucht eine für das normale Spiel nicht hilfreiche Sortierung). Die Zugnummer kann aber 128 überschreiten, d.h. es sind keine Bits mehr übrig für die Markierung von Variantenenden oder aktiv/passiv bekannte Züge.

Wenn das mit dem Saitek nichts mehr zu tun hat, dann gerne in einem eigenen Strang. Ich finde das Thema nämlich interessant.

AW: Saitek Simultano - eine Rechenaufgabe
 

Das kann man vernachlässigen. Zwar existieren pathologische Stellungen mit deutlich über 200 möglichen Zügen, aber in realen Partien habe ich bei Messungen nie mehr als knapp über 90 gemessen, und das war schon selten.

Bei den 8-bittern wurde ja oft auch die Zahl der Halbzüge mit einem uint8_t dargestellt, obwohl Schachpartien durchaus mehr als 128 Züge haben können. Solche Näherungen waren für damalige Geräte aber akzeptabel.

AW: Saitek Simultano - eine Rechenaufgabe
 

Hallo Solwac,

Das ist schon die richtige Lösung. Figurenlisten beeinflussen das nicht. Auch ist eine Sortierung nicht störend. Das ist schon alles deterministisch.

Das hat Rasmus ja schon korrekt beantwortet. Wir reden hier über Eröffungsbibliotheken. Da kann ich mir Zuglisten mit mehr als 128 Zügen in einer Stellung nicht vorstellen. Oder hast du ein Beispiel?
Selbst wenn ... dann wäre die Stellung halt nicht aufgenommen worden

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Ich kenne da zwei Variablen: Eine für die letzten bis zu 256 Halbzüge (mehr kann dann nicht zurück genommen werden) und eine für die Zugnummer um die in einer Zugliste richtig anzuzeigen. Letzteres bedeutet natürlich, dass zwar bis zu 512 Halbzüge korrekt gezählt werden, dennoch aber (wegen des begrenzten Speichers) nur eingeschränkt Züge zurück genommen werden können.

Für Eröffnungsbliotheken siehe nächsten Beitrag.

AW: Saitek Simultano - eine Rechenaufgabe
 

Ne, bei Figurenlisten ist die Sortierung nötig, selbst wenn sie bei der normalen Suche aus Geschwindigkeitsgründen nicht verwendet wird. ;)

OK, letzteres wäre eine Idee. Dann hätte man zumindest ein Bit für ein Flag (Variantenende). Eine solche Bibliothek hätte dann zwar keine Unterscheidung zwischen aktiv und passiven Zügen, wäre aber ultrakompakt.

Etwas mehr Information könnte man mit einem Byte pro Zug und einem Byte pro Variante unterbringen. Bei Varianten mit einem Zug Länge braucht es dann zwei Byte, bei einer Variante von fünf Zügen dann aber nur sechs Byte, d.h. 1,2 Byte pro Zug.

Je mehr ich drüber nachdenke, desto mehr Ideen kommen mir. Ich habe aber zu wenige Schachcomputer um die realisierte Umsetzung abzuschätzen.

AW: Saitek Simultano - eine Rechenaufgabe
 

Hallo Solwac,

Das mag sein, es spielt nur für eine kompakte Eröffungsbibliothek keine Rolle. Auch mit Sortierung und Figurenlisten würde man nicht mehr als 1 Byte pro Zug brauchen (inklusive Variantenende und NAS (nicht aktiv spielbar) Kennung).

Stay tuned ...
Carsten

AW: Saitek Simultano - eine Rechenaufgabe
 

Praktisch gesehen kann man auch nur 6 bits für den Zugindex nehmen, denn meiner Erfahrung nach kommt man zu Anfang ohnehin nicht auf 64 Züge in einer Position. Zudem könnte man notfalls auch mit der Zugsortierung frickeln, so daß die relevanten Züge innerhalb der ersten 64 Einträge landen. Dann hat man zwei Bits für Variantenende und NAS.

Im äußersten Notfall, wenn gar nichts mehr geht, könnte man dann beide Bits auf einmal setzen, was offensichtlich regulär nicht vorkommt (dann würde man den Zug ja einfach weglassen) und damit als Escape-Sequenz ein Sonderformat fürs nächste Byte einleiten.