Hallo, für ein Demo Projekt, was idealerweise später auch auf meinem Z80 mit nur 40kb RAM laufen sollte suche ich eine C Implementierung Spiels 4 Gewinnt. Im Netz ist nahezu alle Java oder C++ und für PC geschrieben. Dabei sind 64MB für Tabellen locker drin. Das Speil ist mathematisch vollständig beschrieben, erstmal von Victor Allis http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf Normalerweise hat man gegen den Computer keine Chance. Zumindest wenn der massig Speicher hat und eine sehr tiefe Analyse zulässt alle denkbaren Züge im Voraus zu bewerten. Gibt es vielleicht so etwas für einen uC? Sagen wir mal den STM323F1 mit 20KB RAM und einer halbwegs guten KI auf Basis des Alpha-Beta Algorithmus? Gruss, Christian
Für diese Problem langt ein AVR, Ein Arduino um 2€. Ein STM ist natürlich eine gute Wahl, günstig schnell und leicht zu bekommen.
Thomas W. schrieb: > Für diese Problem langt ein AVR, Ein Arduino um 2€. > > > Ein STM ist natürlich eine gute Wahl es war die frage nach einer kleinen c-implemntierung und nicht nach geeigneter hardware, oder?
Sven K. schrieb: > es war die frage nach einer kleinen c-implemntierung und nicht nach > geeigneter hardware, oder? Yupp... der Alpha-Beta Algorithmus in der Anpassung auf dieses Game. Habe schon viel gefunden aber eben nur alles für "moderne Sprachen". C scheint out zu sein.... >> Für diese Problem langt ein AVR, Ein Arduino um 2€ Aha... und wie lange soll der rechnen und wo legt er die Daten ab? Ein PC braucht schon 9s bei einer Tiefe von 7. Ich wage zu bezweifeln, dass 2k RAM ausreichen Hash Tabellen abzulegen und binäre Bäume.... wenn schon 300-400 Bytes allein für "Arduino Kram" verbraucht werden. Sonst schreibe ich das auf C um.... https://github.com/KeithGalli/Connect4-Python/blob/master/connect4_with_ai.py
Du hast recht … Einmal kurz gegoogelt … … Implementierungen gibt es ganz viele. Das Problem ist ja auch recht simpel, mit maximal 7 Möglichkeiten pro Zug.
Christian J. schrieb: > Aha... und wie lange soll der rechnen und wo legt er die Daten ab? Ein > PC braucht schon 9s bei einer Tiefe von 7. Ach komm, viel Speicher brauchst du da nicht. Und Geschwindigkeit? Wenn es auf einem Z80 laufen soll, dann ist der AVR allemal schneller. Ich denke wenn Schach am AVR geht, dann geht dieses Fuzzy Spiel spielend.
Ich hatte mich auch lange mit Vier Gewinnt beschäftigt gehabt und vor Urzeiten einen MiniMax Algorithmus in Turbo Pascal geschrieben gehabt (DOS-Zeiten). War auch ziemlich spielstark. Das ganze wollte ich auch auf einem Microcontroller portieren und hatte angefangen gehabt, meinen Algorithmus nach C umzuschreiben bis mir dann der ein Algorithmus von Keith Pomakis über den Weg gelaufen ist. Der hatte zwar meinen alten Pascalalgorithmus nicht geschlagen, aber in 8 von 10 Fällen mich. Auch wenn hier nicht nach Hardware gefragt wurde: Ich hatte versucht ein 4-Gewinnt auf einem ATMega328 zu implementieren. In Ermangelung genügenden RAM-Speichers hat das mit einem MiniMax Algorithmus nicht funktioniert (und ich habe das einfacher gestaltet). Das Ergebnis kann man hier sehen: Beitrag "VierGewinnt mit ATmega328p" Mit den 20kB RAM eines STM32F103 funktioniert der MiniMax Algorithmus von Keith Pomakis gut und das Ergebnis habe ich hier als libopencm3 Makefileprojekt angehängt. Einmal in einer Version, die die Ausgabe auf einem seriellen Terminal vornimmt, einmal mit 160x128 TFT SPI-Display. Anschluß des Displays hier: LCD_CLK = PA5 LCD_DIN = PA7 LCD_CE = PB6 LCD_DC = PA15 LCD_RST = PA8 Tastenbelegung rechts = PB4 hoch = PB5 links = PB1 runter = PB3 ------------------------------------------- Vielleicht nutzt es dir etwas.
Thomas W. schrieb: > Ich denke wenn Schach am AVR geht, dann geht dieses Fuzzy Spiel > spielend. Dann mach es doch einmal, wenn das so einfach geht. Allein aufgrund der Tatsache, dass das Spiel einfacher zu "durchschauen" ist als Schach, ist es auf einem einfachem System wie dem AVR (mit wenig RAM) schwierig ein spielstarkes System herzustellen. Das Schach, das auf den meisten AVR läuft, ist eine Portierung VON einem Z80 und gibt es schon ewig. Für jemanden, der etwas Schach kann, ist die Spielstärke des AVR nicht so wirklich gut. Aber wie gesagt, wenn das für die wirklich "spielend" ist, würde mich deine "spielend" einfache Implementation von Vier Gewinnt auf einem AVR sehr interessieren (keine Ironie). ------------------------------------------------- Im Moment werkel ich immer wieder mal an einer spielstarken Version von Reversi. Allerdings noch mit durchwachsenem Erfolg (meine alte Borland C Version war nicht so sonderlich spielstark).
Ralph S. schrieb: > Das Schach, das auf den meisten AVR läuft, ist eine Portierung VON einem > Z80 und gibt es schon ewig. https://de.wikipedia.org/wiki/Kathe_Spracklen
Ralph S. schrieb: > Aber wie gesagt, wenn das für die wirklich "spielend" ist, würde mich > deine "spielend" einfache Implementation von Vier Gewinnt auf einem AVR > sehr interessieren (keine Ironie). Wäre lustig einen kleinen Wettbewerb zu machen. Jeder gibt seinen Code ab bis zu einem Stichtag und dann lassen wir die KI gegeneinander spielen. Wir haben das in der Schule gemacht, mit programmierbaren Taschenrechner, die sind wirklich schwachbrüstig auch vom RAM her. Ralph S. schrieb: > Im Moment werkel ich immer wieder mal an einer spielstarken Version von > Reversi. Reversi ist deutlich komplexer. Schon von der Anzahl der Möglichkeiten und von der Berechnung der Möglichkeiten. ==== Auf einem PC geht man das natürlich ganz anders an als auf einem Spielzeug wie einem Arduino. Dem Mangel an RAM und Rechenleistung steht einem Überfluss an Flash Speicher entgegen. Also muss man halt zeitkritische Sachen möglichst kompakt und möglichst wenig Rechnerei abfackeln. Man schafft man sich zb. einen Vorteil, indem man einen Codegenerator baut, der die Feld Bewertung vor rechnet. Dann hat man halt eine menge Funktionen die spezielaisiert sein und spart sich viele IF und ganz viel RAM.
Ralph S. schrieb: > Dann mach es doch einmal, wenn das so einfach geht. Allein aufgrund der > Tatsache, dass das Spiel einfacher zu "durchschauen" ist als Schach, ist > es auf einem einfachem System wie dem AVR (mit wenig RAM) schwierig ein > spielstarkes System herzustellen. Ist es auch. Du kannst RAM gegen Rechenzeit tauschen, dafür werden beim idealen Alorithmus auf gamesolvers.org etliche Tabellen angelegt die einen Cache bilden bzw eine LUT. Da man das aber beim AVR nicht hat muss es eben gegen Rechenzeit getauscht werden. Habe da 15-20 mal gegen gespielt, das Ding ist unschlagbar und vor allem sehr schnell. @RalfS: Schaue ich mir an!
Ralph S. schrieb: > Der hatte zwar meinen alten Pascalalgorithmus nicht geschlagen, aber in > 8 von 10 Fällen mich. Habe das mal runter geladen. Ist der Ordner vg_version2 der Richtige? Ich arbeite mit der StdPeriphLib immer noch, das ganze Drumherum kann ich selbst machen. Wird entweder auf einem Grafikdisplay oder mit LED realisiert. Erstmal aber als ASCII Grafik auf VT100 Terminal. Da kann ich mit ncurses auch Sachen neu zeichnen ohne dass gescrollt werden muss. Ich brauche doch nur c4.c und c4.h als Kern des Ganzen? Da durchlblicken und den Input und Output, sowie die User Interaktion da drum herum bauen? Und dann gibt es noch den ordner orginal_ki, der ist deutlich größer als deiner was die Dateien angeht. 16kb mehr. Hast du mal einen ebay Link auf die Displays? Sehr nett, finde aber nur die oled 128.64
Christian J. schrieb: > Ich brauche doch nur c4.c und c4.h als Kern des Ganzen? Da durchlblicken > und den Input und Output, sowie die User Interaktion da drum herum > bauen? Richtig Christian J. schrieb: > Und dann gibt es noch den ordner orginal_ki, der ist deutlich größer als > deiner was die Dateien angeht. 16kb mehr. Was ich jetzt alles geändert hatte weiss ich nicht mehr (viel war es jedenfalls nicht). Christian J. schrieb: > Ich arbeite mit der StdPeriphLib immer noch, das ganze Drumherum kann > ich selbst machen. Denke ich schon, dass das gut an die StdPeriphLib anpassbar ist. Mir hat die libopencm3 besser gelegen, vor allem habe ich darauf hier fast alles aufgebaut. Wenn du unter Linux bist und den arm-none-eabi-gcc im System installiert hast, reicht ein Aufruf des Makefiles um das Programm zu übersetzen. Die Komplette libopencm3 findet sich im Verzeichnis lib. Alle zusätzlichen Sourcen in src und die dazugehörenden Header in include. Prinzipiell kannst du jedes SPI-TFT mit 160x128 Pixeln verwenden. Im Header tftdisplay.h kannst du den Controller des Displays sowie die Auflösung des Displays angeben. Weil ich gerade sehe, dass auch in Beitrag "VierGewinnt mit ATmega328p" geschrieben hast: Hier kommt ein 128x128 Display zum Einsatz, aber auch hier kannst du in dem entsprechenden Header tftdisplay.h Angaben zum Display machen. Chinalieferant für 160x128 und 128x128 Display: https://www.ebay.de/itm/1-44-1-8inch-TFT-Full-Color-128x128-128x160-SPI-LCD-Display-Module-for-Arduino/173530635627?hash=item28673b5d6b:m:mEKpRFG8-DAmKy7z_XfOnyQ Displays mit ST7789 OLED habe ich leider noch nicht am Funktionieren, bin ich aber dran !
Ralph S. schrieb: > Chinalieferant für 160x128 und 128x128 Display: > > Ebay-Artikel Nr. 173530635627 Ok, grad 3 bestellt. Hoffe mal dazu gibts ne Lib? Habe die für 320x240 mal vom Arduino auf STM portiert, da die SPI anders ist. Spielt mit 12 Mhz auf Lochraster prima für ca 5cm leitungen, drüber verliert sie dann aber Bits. Yupp, jibbet.... https://github.com/o-m-d/st7735_spi_stm32
Christian J. schrieb: > Ok, grad 3 bestellt. Hoffe mal dazu gibts ne Lib? Habe die für 320x240 > mal vom Arduino auf STM portiert, da die SPI anders ist. Spielt mit 12 > Mhz auf Lochraster prima für ca 5cm leitungen, drüber verliert sie dann > aber Bits. > > Yupp, jibbet.... > https://github.com/o-m-d/st7735_spi_stm32 Die frisst ja maximal Performance. Einen halben Tag Arbeit, und die Lib ist ein Vielfaches schneller!
Ralph S. schrieb: > Christian J. schrieb: >> Und dann gibt es noch den ordner orginal_ki, der ist deutlich größer als >> deiner was die Dateien angeht. 16kb mehr. > > Was ich jetzt alles geändert hatte weiss ich nicht mehr (viel war es > jedenfalls nicht). Hi, ich schieb das nochmal hoch, da ich genau das Thema jetzt wieder basteln möchte. Zunächst mal das Netz durchsucht, was ja voll ist. Die Hälfte aber leider unbrauchbar, weil wie so oft Codes veröffentlicht werden, die keinerlei Doku haben und alle Variablen maximal 2 Zeichen lang sind. Der von Keith Pomakis sieht aber gut aus. Wie das genau funktioniert lasse ich erstmal, das Prinzip ist bekannt aber es soll erstmal funktionieren. Zunächst werde ich mir daher ein Frontend schreiben, Displayausgabe, Touchscreen, Tasten, LEDs etc. Und dann die AI engine anbinden. Welche CPU? STM32Fxxx oft genug verwendet, mal ne andere. Muss nur eine UART haben und vllt.2 Tasten, mehr braucht das Game nicht. Mit einem Touch Display sind auch die Tasten zuviel und mit 2 Leitungen würde es auskommen. Hätte noch an 32 Bittern, die alle auf Arduino Basis laufen: Seeduino XIAO (super klein, M0 Cortex) 32kb RAM, 256 kb Flash ESP8266 D1 Mini (80 kb RAM, 1 MB Flash) ESP8266 Kit 8 (80kb RAM, 1MB Flash) ESP8266 NodeMCU Reichen 32 KB RAM? Vielleicht meldest Du dich ja mal, würde gern etwas von Dir da lernen, auch wenn ich andere Hardware nutze. Christian
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.