Schach auf ATmega32

[dcv]

Ist es möglich ein Schachprogramm auf einen ATmega32 zu implementieren? An Hardware dürfte es nicht mangeln, da eine Geschwindigkeit von 16MHz ausreichen dürfte (schon auf einen Schneider CPC gab es ein Schachspiel mit Computergegner, obwohl der nur 4MHz hatte, und auch neuere Schachcomputer dürften, wenn man den Preis betrachtet, nicht viel bessere Prozessoren enthalten. Nur der Speicherplatz dürfte etwas dürftig sein und ein ATmega64 bzw. ATmega128 sind im Vergleich sehr teuer (ATmega32 7€, ATmega64 24€) und ab Atmega64 gibt es sie nicht mehr in praktischen DIL Gehäuse (ich habe zumindest keine gefunden). Außen Geschwindigkeit und Flash brauch ein Schachprogremm nur Arbeitsspeicher und der ist genug vorhanden (ak Byte). Das Anzeigen kann auch ein weiterer Microcontroller mit Lcd übernehmen oder es kann z.B. auf einfachen Grafiktaschenrechnern, die kein Assembler unterstützen aber eine serielle Schnittstelle haben, implementiert werden. Auch nur die Ausgabe des Zuges ist möglich. Hat jemand schan irgendwelche Erfahrung? Ich bin für jede Antwort dankbar.

[RCO]

Also wenn ich das richtig sehe, kosten Atmega64 9,30€ bei reichelt, aber vermutlich wäre es eh sinnvoller einen externen speicher anzuschließen, vielleicht eine MMC-Card oder so, soll ja gehen. Ich weiß allerdings nicht wie aufwendig das ist. Allerdings hättest du dann speicher genug. Leider weiß ich auch garnicht genau, wie ein schachprogramm aufgebaut ist, hat es quasi jede Situation gespeichert und schaut nur nach, was als nächstes gemacht werden muss, oder ist es so intelligent zu reagieren. Vermutlich eine Mischung aus beidem.

MFG Moritz

[Gottfreak]

hat es quasi jede Situation gespeichert und schaut nur nach, was als nächstes gemacht werden muss, oder ist es so intelligent zu reagieren. Vermutlich eine Mischung aus beidem.

Ja, beides hat daran Anteil. Bei den Eröffnungen(zumindest 10-30 Varianten a ca. 4 Züge) greifen die meisten Programme auf Bibliotheken zurück. Später werden dann alle möglichen Züge "durchprobiert" und auch alle Reaktionen darauf usw(Stichwort "Minimax-Algorithmus"). Dabei werden die Ergebnisse nach gewissen Kriterien gewichtet(so sind die Figuren unterschiedlich viel Wert(nicht nur nach ihrem Typ, sondern auch nach ihrer Position auf dem Spielfeld).).
Der Rechenaufwand ist dabei in etwa eine Exponentialfunktion der Rechentiefe(der Anzahl an Zügen, die "vorrausgedacht" wird).
Zur Ausgabe: Ich find' die Variante mit einem "echten" Schachbrett am schönsten, wo Züge des Menschen über Reedkontakte erkannt werden und der Computer mit LEDs signalisiert, was er machen will(ist natürlich eine Menge Arbeit zu bauen.).

[Frank]

Irgendwo hab ich mal gelesen das es für einen Atmel schon ein Mini-Schachprogramm gibt. Es war aber glaub für den Mega128, mit dem Mega32 wird das nicht klappen. Man braucht einfach mehr schnellen RAM Speicher.
Leider hab ich die Seite mit dem Mini-Schachprogramm nicht mehr gefunden :-(

[dcv]

Wenn man eine MMC-Card benutz geht das aber doch dann sehr langsam, da das Programmteil erst in den RAM geladen werden muss, bevor es ausgefürht wird, oder gibt es eine Möglichkeit ein Programm direkt von einer MMC-Card laufen zu lassen? Gibt es eine Möglichkeit die I/O portrs als Adress- und Datenbus zu verwenden ohne das das die Geschwindigkeit reduzirt?

[RCO]

Mein Vorschlag resultierte ja auch nur aus dem nichtwissen, wie Schachprogramme aufgebaut sind, aber desto mehr langsamen Speicher man hat, desto mehr Züge könnte man vielleicht vorspeichern etc.

@ dcv: Der Anschluss von MMC-Karten ist möglich, aber ich hab grad keine Seite, noch einfacher ist es glaube ich bei SD-Karten.

Hier eine Seite, die zeigt, dass es möglich ist, wenn die hinkriegen, nen MP3-Player aus nem AVR zu bauen wo von ner KArte gelesen wird, sollte es wohl gehen ;-)

http://mme-berlin.de/mmeavr/mmeavr.htm#mp3

MFG Moritz

MFG Moritz

[RCO]

OK, bisschen gegooglet, und schlauer, hier ein Thread aus dem Mokrokontroller-NET-Forum, über die Software für dem AVR zum Anschluss der MMC/SD KArte.

http://www.mikrocontroller.net/forum/read-4-90147.html

UNd hier noch eine Homepage mit downloads...

http://www.mikrocontroller.net/forum/read-4-90147.html

http://www.ulrichradig.de/

MFG Moritz

[thkais]

Moin,

Leuts, ihr seit einfach zu verwöhnt. Ist ja ganz klar, heutzutage werden einem die GHz und MB nur so um die Ohren gehauen.
Es wurde vor Ewigkeiten mal ein Schach für den ZX-81 geschrieben. Dies ist einer der ersten Homecomputer überhaupt und er verfügt über den sagenhaften Speicher von einem ganzen Kilobyte.
Ich rede hier vom Gesamtspeicher, wohlgemerkt.
Inwiefern das damalige Programm auch das Basic-Rom angezapft hat, ist mir nicht bekannt - es dürfte sich bestenfalls um Berechnungsroutinen gehandelt haben.
Von einer "Spielstärke" kann man hier aber nicht reden ;-)

Schaut mal hier - gaaanz unten auf der Seite ist ein Link. Allerdings dürfte der Atmel den Z80-Code leider nicht schlucken.
http://www.zx81.de/soft/_main_d.htm

[Frank]

Also in 8 KB bekommt man sicher schon ein Schachprogramm rein (gab´s schon beim PET - falls den noch jemand von Euch kennt - quasi Vorgänger vom VC64/20 wenn man so will). Allerdings von der Spielstärke wäre das recht schwach. Mindestens 16 KB oder 32 kb wären schon vorteilhafter.

Mit MMC/SD KArte und ähnlich langsamen Speichern kann man in der Schachprogrammierung so gut wie nix anfangen. Damit kann man bestenfalls eine Eröffnungsbibliothek verwalten, was aber nur wenige Züge beim Spielstart nutze (ca. 2 bis 4 Züge), danach muss das Programm richtig schnell rechnen und braucht einen schnellen RAM-Speicher. Je schneller, desto spielstärker wird das Programm sein. Dies liegt daran das diese Programme die sogenannte Brute Force Methode nutzen. Es werden also möglichst viele Züge vorausberechnet und ausprobiert.
Ich kenn mich mit dem Thema recht gut aus, mich vor vielen Jahren mal ernsthafter mit der Schachprogrammierung beschäftigt.

Gruß Frank

Hi

ich hätte nicht gedacht, das noch einmal jemand etwas schreibt.
Ich hab mich erst mal mit dem Aufbau eines Schachprogramms bis ins Detail eingearbeitet und in Delphi 6 ein Schachprogramm geschrieben (ist halt für den Anfang leichter) und schau, es läuft sogar schnell und spielstark (es gewinnt teilweise gegen mich) nur die Bedinung lässt noch zu wünschen übrig.
Es ist eine klassische Brute-Force - Alpha-Beta Variante.
Jetzt muss ich erst mal mit WinAVR klar kommen, da ich bisher nur in Assebler und Bascom programmiert habe, aber da stört mich die 2k Byte Begrenzung, außerdem kommt Basic meiner Meinug nicht an Pascal heran.

Von der Übersicht und Bequemlichkeit ist Pascal sicher schöner, aber aber nicht unbedingt von der Geschwindigkeit. Zudem gibts keine "preiswerten" Compiler für die größeren AVR´s

[RCO]

@ 1. Gast:
Stark, wie bist du denn vorgegangen, könnte man da mal was von sehen? Wie entscheidest du, welcher Zug sinnvoller ist, wieviele Züge werden voraus gedacht?
Warum bleibst du nicht bei Assembler? Das ist doch eh schneller und wenn du es schon kannst.

MFG Moritz

[recycle]

Ich finde die Idee mit dem Schachbrett, das automatisch die Spielzüge des Menschen erkennt und z.B. über LEDs die Züge des Computers anzeigt ganz interessant.
Diese Brett könnte man auch über ein serielles Kabel oder vielleicht auch über Infrarot an den PC anschliessen und das eigentliche Schach-Programm auf dem PC laufen lassen.
Wenn dann in dem Microcontroller noch Speicher übrig ist, könnte man den ja für ein ganz simples Schachprogamm nutzen, so dass ohne PC eine Art Demo- oder Anfänger Mode möglich ist.

Oder man bringt dem µC autark das Dame-Spiel bei und für Schach muss man halt den PC anschliessen.
Eventuell reicht für das Schachprogramm ja auch ein PDA. Wenn man den nur daneben legen muss und die Datenübertragung über Infrarot abläuft, wäre das ja auch noch halbwegs elegant und sicher wesentlich komfortabler als direkt auf dem winzigen PDA-Display zu spielen.

Auf dem PC oder PDA hat man dann auch noch genug Speicher um gespielte Partien abzuspeichern, das sogar wenn man das Brett nutzt um Mensch gegen Mensch zu spielen.
Auf einem PDA-Display könnte man sich dann am nächsten Tag in der S-Bahn ohne Schachbrett nochmal in Ruhe ansehen, warum man die Partie am Vorabend verloren hat ;-)

[dcv]

Wer sich dafür interessiert, wie ein Schachprogramm aufgebaut ist, der kann mal die Seite
http://de.wikipedia.org/wiki/Minimax-Algorithmus
besuchen, nicht zu vergessen ist natürlich, das ein Schachprogramm über die Erweiterung des Minimax-Algorithmus durch ein Alpha-Beta-Suche verfügen muss und, um dadurch ca. 150 mal schneller zu sein, da ein Schachprogramm sonst selbst auf einem GHz Computer nicht realisierber ist.
Die Alpha-Beta-Suche ist auf
http://de.wikipedia.org/wiki/Alpha-Beta-Suche
sehr gut beschrieben.
Also einfach mal vorbeischauen.

PS: Ich hab kein PDA und das Schachspiel soll sehr transportabel bleiben, deshalb kommt der Computer erst mal nicht in Betracht.

[Kleiner]

Hallo,


[...] außerdem kommt Basic meiner Meinug nicht an Pascal heran.
vielleicht ist dieser Link ja etwas für Dich: http://avr-ada.sourceforge.net

Dieses Projekt beschäftigt sich damit den GNAT Ada-Compiler auf AVRs als Targetsystem zu portieren. (Basierend auf den AVR-GCC Port) Ich bin gerade dabei diesen Compiler ein wenig auszuprobieren und bin erstaunt, was schon alles funktioniert.

Jemand der schon mal mit Pascal gearbeitet hat dürfte sich schnell mit ADA zurechtfinden.

[John13]

Schaut Euch einfach mal diese Seite an:

http://www.schachcomputer.at/

Relativ leistungsstarke Schachcomputer sollten sich mit dem ATmega32 machen lassen, von der Rechenleistung liegt er über dem alten MC68000er von Motorola, wenngleich auch nicht 16bittig.

http://www.labcenter.co.uk/products/avr.htm