Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / Das kleinste Schachprogramm der Welt
- - By Joe Boden Date 2014-01-12 12:15
Was es nicht so alles gibt. Aus einem Wettbewerb entstanden ist das 1kb grosse Schachprogramm wie nachfolgend zu sehen.
Kannte das jemand? Normalerweise erfahren wir solche Sachen am Rande oft durch Michael Scheidl.

http://nanochess.110mb.com/chess4.html
Parent - - By Mythbuster Date 2014-01-12 12:43
Schon Anno 1984 gab es einen Schachcomputer, dessen Programm exakt 1 kB betrug, inkl. Tastatur- und Displayansteuerung ... und immerhin beherrschte er alle Regeln.
Parent - - By Chess Player Date 2014-01-15 11:50
http://en.wikipedia.org/wiki/1K_ZX_Chess

Code:
1K ZX Chess is a chess-playing computer program for the unexpanded Sinclair ZX81, created by programmer David Horne.[1] The game implements most chess rules (castling, queening, and en passant capture are missing), artificial intelligence, and a user interface. The code uses only 672 bytes of RAM, making this the smallest computer implementation of chess on any platform.
See also

    Microchess

References

    ^ Horne, David (February 1983). "Full ZX-81 Chess in 1K". Your Computer. pp. 100–102. Retrieved 17 October 2013.
Parent - By Benno Hartwig Date 2014-01-16 08:32
Faszinierend: 672 Byte (nein, ich habe hier kein 'k'  vergessen!) für ein komplettes Schachprogramm.
"castling, queening, and en passant capture are missing", aber wer wollte das dem Programmierer in diesem Fall schon vorwerfen.
Da war mein 'Collossus' mit seine 27kB (so meine Erinnerung) ja riesig gegen. Da diese aber immerhin 11 Minuten(?) brauchten, um sich von meiner Datasette zu spulen, kamen sie mir damals auch wirklich riesig vor.

Benno
Parent - - By Michael Scheidl Date 2014-01-12 14:57
Zitat:
Normalerweise erfahren wir solche Sachen am Rande oft durch Michael Scheidl.

Selbstverständlich wie z.B. im Jahre 2009:

http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=10947;hl=toledo

Das Thema gab es IIRC auch schon früher im Forum, aber ich finde nichts mehr.

Ich finde es höchst erstaunlich, daß durch diese paar Zeilen Code sozusagen eine vollständige Schachintelligenz entsteht. In Klartext haben ja schon alleine die Spielregeln größeren Umfang. Nicht gegen Toledo, aber gegen Micro-Max, dessen Source geringfügig größer ist, habe ich einige Partien gespielt und über die Qualität gestaunt. Erst nach mehreren Anläufen gelang mir ein Endspielsieg.

Bei Toledo und Micro-Max wurde versucht den Umfang des Quellcodes zu minimieren, während es bei Nano- und Pikoszachy darum geht das kleinstmögliche Executable zu realisieren.

http://www.nanochess.org/chess.html
http://home.hccnet.nl/h.g.muller/max-src2.html
http://www.kalisz.mm.pl/~pic/nanochess/

Für mich grenzt all das an Wunder.
Parent - - By Tom Paul Date 2014-01-12 15:59
Welche Spielstärke hast du denn?

Wie schneiden die Programme im Vergleich zu Stockfish ab?
Programme: Größe und Spielstärke im Vergleich zu Stockfish Größe und Spielstärke.

Kann man sagen die Programme sind für ihre Größe besser als Stockfish?

Könnte man Stockfish genauso viel Größe evtl. etwas mehr zumuten bei gleichbleibender Stockfish Spielstärke?
Parent - - By Benno Hartwig Date 2014-01-13 09:05

> Kann man sagen die Programme sind für ihre Größe besser als Stockfish?


Wie willst du das denn messen?
ELO-Zahl / EXE-Laenge ?
Ja, dann wird der Winzling wohl jede Engine z.B. aus dem TCEC-Turnier oder auch aus Stefans Liste weit abhängen.
Aber macht solch ein Vergleich Sinn? Wohl eher nicht, oder?

Benno
Parent - - By Chess Player Date 2014-01-13 10:49
wenn sie so klein sind müssten sie doch rasend schnell sein? viel schneller als stockfish! oder sehe ich das völlig falsch?
Parent - By Tom Paul Date 2014-01-13 11:07
Und sprechen wir hier nicht von 1 KB vs 1000 KB ?
Bei ~500 ELO Unterschied?
Demnach wären 100 ELO mehr 200 KB.
Und 500 ELO mehr 1000 KB.
Parent - - By Benno Hartwig Date 2014-01-13 11:16
Knoten / Sekunde meinst du?
Nicht weil das Programm klein ist sondern weil ggf. die Bewertung sehr einfach ist, könnte das eventuell stimmen.
Wenn aber mit Blick auf kurze und nicht schnelle Implementierung gearbeitet wurde, dann würde es an verschiedenen Stellen ggf. wieder langsam.
(Bubblesort braucht nicht viel Code, dauert aber)

Tiefe erreichen meinst du?
Dann ist das kleine Dinge höchtwahrscheinlich deutlich 'langsamer', da ihm einfach so viel Logik fehlt für kreative Cuts und eine schlaue Suchtiefen-Verwaltung.

Benno
Parent - - By Michael Scheidl Date 2014-01-13 12:41 Upvotes 1
Die erwähnten Engines sind bei CCRL getestet worden. Wenn man zwecks größerer Partienzahl auf die 40/4-Liste schaut: Beispielsweise PikoSzachy, kleiner als 10 KB, ist dort nur unwesentlich hinter Mephisto Gideon Professional oder Tao gereiht, und vor bekannten Engines wie LambChop, Quark, Nejmet u.a.

Während es mich schon sehr wundert, daß überhaupt die Schachregeln komplett in weniger als eine A4-Seite Quellcode passen können, steckt ja noch viel mehr drin. Hier z.B. die Featureliste von MicroMax (< 2000 Zeichen Source):

Zitat:
On these pages various aspects of micro-Max are described:

Basic Data Representations
Piece Encoding
Board Representation
Move Generation
Basic Moves
En Passant Capture
Castling
Pawn Promotions
Search Algorithm
Alpha-Beta Minimax
Quiescence Search
Do and Undo Move
Iterative Deepening
Move Sorting
Transposition Table
Hashing
Replacement
Evaluation
Material
Piece-Square Table
Checkmate and Stalemate
Delay Penalty
The Interface
Move Legality Checking

Version 4
General & Hash Table
Futility Pruning
All-captures Quiescence Search
King Safety
Null-Move Pruning
Self-Deepening IID

Faszinierend
Parent - - By guest Date 2014-01-13 13:03
wenn ich das hier lese, dann ist für mich klar was die neuen programmiersprachen an ballast mit herumschleppen. dort liegt der schlüssel für effektives programmieren.
Parent - By Benno Hartwig Date 2014-01-13 16:38

>... dort liegt der schlüssel für effektives programmieren.


Effektives Programmieren macht sich heute wohl eher an einem
"In kurzer Zeit eine hohe Funktionalität erzeugen"
fest als ein einem
"mit wenig Code eine hohe Funktionalität erzeugen" oder einem "eine möglichst kleine EXE erzeugen".

Auf dem C64 wurde  sicher mit Bytes gegeizt, und auch unter DOS musste man den Platz ggf. sehr im Auge haben.
Heute sieht es aber meist anders aus. Wen interessiert denn wirklich, ob ein Programm 100 kB oder 1 MB oder 10MB MB groß ist.
Und wenn denn einer eine 100MB-Engine schreibt? Macht doch auch nicht wirklich was, wenn sie denn gut ist.

Die Engine mit mehr ELO wird gefeiert und nicht der Tabellenfünfte wegen seines ggf. nur ein Viertel so großen Platzanspruchs.

Benno
Parent - - By Benno Hartwig Date 2014-01-13 15:14
Bei dieser Gelegenheit habe ich in der Liste
http://www.computerchess.org.uk/ccrl/404/
auch mal nach ganz unten geschaut:
Engine:
Platz  Name         ELO     +    -  Score  Geg.ELO  Remis  Spiele
461 Ram 2.0         509   +537 −532 33.2%   +175.0  30.1%   435
462 LaMoSca 0.10    455   +590 −585 31.1%   +189.4  60.8%   286
463 CPP1            425   +621 −616 28.6%   +217.4  22.7%   255
464 ACE 0.1         309   +736 −731 14.2%   +493.3  22.0%   473
465 POS 1.20        279   +767 −762 18.6%   +378.1  22.5%   298

Hier sind die Error-Bars tatsächlich größer als der ermittelte ELO-Wert.
Kann das aber wirklich auch sein? Trotz immerhin mehr als 200 bis über 400 Spielen Errorbars zwischen 500 und 800.
OK, die Engines haben wenig Punkte geholt. Reicht das als Erklärung?

Benno
Parent - By Thomas Müller Date 2014-01-13 15:26
ist ja krass
vielleicht wird die errbar unterhalb einer ELO von ca. 1000 so berechnet.
Ich tippe mal wenn es engines gibt die noch näher an 1000 liegen dann wird die errbar immer kleiner ?!

gruß
thomas
Parent - - By ? Date 2014-01-13 17:18
Nein! Es ist mir unerklärlich, hat aber mit diesen Engines vielleicht nichts zu tun...
Was kann eigentlich eine Engine mit elo=0?guest
Parent - By Benno Hartwig Date 2014-01-16 08:36

> Was kann eigentlich eine Engine mit elo=0?guest


Im Ernst: Eine Engine, die die Regeln beherrscht, die aber nur rein zufällig irgendeinen legalen Zug ausführt, ungefähr welchen ELO-Wert würde sie eigentlich bekommen.
Sie könnte ja auch mal gegen Carlsen gewinnen. Es nur eher unwahrscheinlich.
Benno
Parent - - By Guest Date 2014-01-16 09:12
Das glaube ich nicht!
Und ich glaube auch nicht an die Zufälligkeit dieser Ergebnisse. Benno, wie kann so ein Ergebnis zustande kommen? als Statistiker müsstest Du doch irgendwelche Erklärungen parat haben.
Parent - By Benno Hartwig Date 2014-01-16 17:17

> als Statistiker müsstest Du doch irgendwelche Erklärungen parat haben.


Nee, kann ich nicht.
Ich weiß auch nicht, wie diese Errorbar-Grenzen berechnet werden.
Hängt sicher von der Spieleanzahl ab, aber sicher auch noch von diversem mehr (Quote, Gegner-Durchschnitts-ELO, Verteilung der ELO unter den Gegnern(?), Remisquote...)

Benno

PS:
Welcher ELO-Wert wäre für eine Engine vernünftig, wenn sie gerade 1000 Partien gegen Carlsen verloren und 1000 Partien gegen die hiesigen Kindergartenkinder gewonnen hat?
Parent - By Benno Hartwig Date 2014-01-13 14:50

> Für mich grenzt all das an Wunder.


Ja, wirklich faszinierend. Und deutlich(!) kleiner als das von mir vermutete Größenminimum!

Es könnte interessant sein, eigene Ratinglisten zu bauen, z.B. in den Spielklassen
- Source mit maximal 2000 Byte (Fliegengewicht-Weltmeister)
- Source mit maximal 5000 Byte (Federgewicht-Weltmeister)

Benno
Up Topic Hauptforen / CSS-Forum / Das kleinste Schachprogramm der Welt

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill