Schachcomputer : AI oder Select Case
Übersicht
BlitzBasic Beginners-Corner
|
SmilyBetreff: Schachcomputer : AI oder Select Case |
 Mo, Feb 14, 2005 10:51Antworten mit Zitat 
|
|---|---|---|
|
Hallo, ich wollte mal ein kleinen Schachcomputer programmieren.
Jetzt wollte ich mal fragen, was ihr mir Empfehlen würdet: 1. Eine Künstliche Intiligenz, die den nächsten Zug berrechnet oder 2. Eine Select - Case abfrage, wo alle Möglichkeiten Stehen und der Computer sucht sich nur noch die aktuelle Stellung aus und hat auch schon sein Zug |
||
|
Hubsi |
Mo, Feb 14, 2005 11:30 Antworten mit Zitat
|
|---|---|---|
Ersteres. Zum einen gibts es beim Schach derart viele Kombis das die Select in etwa drei Lichtjahre lang werden würde und zum anderen wäre das System zu leicht zu durchschauen. 
|
||
| Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn... | ||
|
D2006Administrator |
Mo, Feb 14, 2005 11:42 Antworten mit Zitat
|
|---|---|---|
|
ein wenig Respekt wäre angebracht.
Ich programmiere seit ca. 7/8 Jahren und fühle mich alles andere als in der Lage, eine Schach KI zu programmieren. Da fließen derart viele Berechnungen ein... Und wenn man einen guten Computer haben will, bräuchte man auch eine Datenbank mit historischen Spielen. Alles andere bietet keine Konkurrenz zu bisherigen Schachspielen. Code lieber Doom4! MfG D2006 |
||
Klaas |
Mo, Feb 14, 2005 11:48 Antworten mit Zitat
|
|
|---|---|---|
ja, das Select möchte ich sehen 
man kann grob überschlagen ... Anzahl der Felder ^ Anzahl der Figuren das ist nicht ganz korrekt aber zeigt ungefähr die Dimensionen 64 ^ 32 = 6 * 10^57 also ein 6 gefolgt von 57 nullen wenn jeder Select nur aus 20 Zeichen bestehen würde dann bräuchte man noch 10 hoch 47 Terrabyte um den Quellcode zu speichern. 100.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 TerraByte Kompiliert wirds etwas kleiner ... 
|
||
|
|
SmilyBetreff: Oh |
Mo, Feb 14, 2005 12:12 Antworten mit Zitat
|
|---|---|---|
|
Angenommen es Existiert Folgende Stellung:
Computer - Turm auf H8 Spieler - Läufer auf E8 Computer - Bauer auf C6 Da kann der Computer doch diese Stellung abrufen: Computer - Turm auf A8 Spieler - Läufer auf D8 Computer - Bauer auf F6 Als kann man das Schachbrett an der Y-Achse Spiegeln. So halbiert man die möglichkeiten. Also Sind das dann nur(!!!) noch 10^47 / 2 TB (500.000.000.000.000.000.000.000 TB). Durch weitere solchen kleinen Tricks, kann das Vielleicht mal auf eine Erträgliche Größe Schreiben. Ich arbeite noch mit Intgerzahlen, da wird für eine Zahl mit 7 Ziffern nur 4 Byte verbraucht. PS: Die, die bei der NASA (Haben die Leistungsfähigsten Rechner Weltweit) arbeiten, wollen auch mal ein Schönes Spiel haben.
|
||
Klaas |
Mo, Feb 14, 2005 12:23 Antworten mit Zitat
|
|
|---|---|---|
|
Also damit würdest du ja nur ein Schachspiel mit 2 Figuren haben !!!
Du mußt aber immer alle Figuren die auf dem Feld sind betrachten. Das Feld zu spiegeln ist unsinn .. was hat das denn noch mit Schach zu tun ? ... zudem 10^47 /2 ist immer noch 5*10^46 also 50.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 TerraByte ... du brauchst ne Menge guter Tricks um das zu reduzieren !!
Ich glaub die Zahl sagt dir nicht viel oder ? Stell dir mal vor du hast 10 Milliarden Freunde ... jeder von denen müßte dir Festplatten mit 5*10^36 Terrabyte Speicherplatz schenken damit du dein Programm speichern könntest ... und dann kommen bestimmt noch einige Trilliarden Tastaturen die du verbrauchen wirst ... bzw. nicht du sondern deine Groß-Groß-Enkel die dann immernoch an dem Case-Select tippen werden.
|
||
|
|
SmilyBetreff: Und die KI? |
Mo, Feb 14, 2005 12:37 Antworten mit Zitat
|
|---|---|---|
|
Ob die KI besser ist?
Zitat von D2006: Da fließen derart viele Berechnungen ein. Naja, ich versuch mich doch Vielleicht ersteinmal an einem Tic-Tac-Toe Das wäre etwas kleiner. |
||
|
Spikespine |
Mo, Feb 14, 2005 12:55 Antworten mit Zitat
|
|---|---|---|
|
tic-tac-toe ist da wohl wesentlich unanspruchsvoller. ich denke, man könnte sogar jede stellung einzeln abspeichern...
|
||
Hot-BitSieger des B2D Retro Wettbewerb / Aug 04 |
Mo, Feb 14, 2005 13:51 Antworten mit Zitat
|
|
|---|---|---|
|
Hoi.
Ich kekse mich ab ! Bevor du nur annähernd mit dem Gedanken spielst, eine Schach-KI zu programmieren, mach erst mal dein TIC-TAC-TOE ! Denn schon hier wirst du leichte Probleme haben. Und dann steig um auf VIER GEWINNT ! Hier wirst du schon anstehen, wie ein Ochse vorm Scheunentor 
Außer du spiegelst, re-spiegelst und extrahierst das gespiegelte, bis nur mehr 2 Felder und ein Spielstein übrig bleibt 
Mann, von Selbst-Überschätzung schon mal was gehört ? Fang klein an. Mach klein weiter. Dann wird vielleicht was. Toni |
||
|
... ..... .i.. ...
*** Sieger des BB-Gameboy-Contest 2004 Sieger des Blitzbaster 2D-Minigolf-Contest 2005 *** |
||
|
Rakete |
Mo, Feb 14, 2005 14:13 Antworten mit Zitat
|
|---|---|---|
|
@hot-bit
Warum lässt du nach jedem Satz eine Zeile frei? 
Rakete |
||
Hot-BitSieger des B2D Retro Wettbewerb / Aug 04 |
Mo, Feb 14, 2005 14:39 Antworten mit Zitat
|
|
|---|---|---|
|
Hoi.
Damit es auch für die Analphabeten unter euch, zu lesen ist ? Hast es nun verstanden ? Ok, dann passt es
Toni |
||
|
... ..... .i.. ...
*** Sieger des BB-Gameboy-Contest 2004 Sieger des Blitzbaster 2D-Minigolf-Contest 2005 *** |
||
|
adba |
Mo, Feb 14, 2005 15:08 Antworten mit Zitat
|
|---|---|---|
|
Ich würde eine Art bewertungssystem programmieren. Zum Beispiel ist ein zug umso besser je mehr eigene figuren gedekt sind und auch umso besser je mehr gegnerische angegriffen werden. zudem muss man schauen das alle figuren die angegriffen werden auch gedekt sind. Dann müssen die wichtigen spielfiguren (dame, turm, ...) mehr punkte geben (also wichtiger sein) als zb die bauern.
Jetzt kannst du bei jedem zug berechnen welche figuren gedenkt werden müssen, welche möglichst wertvollen des gegners man angreifen könnte und und und... natürlich darf de könig nie im schach stehenbleiben. Mit all diesen Regeln bekommt jeder mögliche zug eine Zahl zugeordnet und je höher diese zahl ist desto besser. am schluss der berechnung führst du einfach den zug aus der die höchste zahl hat. Wenn du weitere schritte im voraus berechnen möchteste wird es ein bisschen komplizierter. ich würde dann auch jeden möglichen zug berechnen und dazu noch jede mögliche reaktion des gegner und darauf wieder jeder mögliche zug von dir usw... das kann man natürlich nicht sehr weit machen weil sonst der rechnaufwand zu gross wird. Wenn zwei züge die gleich hohe bewertung erlangt haben entscheidest du per zufall. das macht das spiel ein bisschen abwechslungsreicher. man könnte sowieso noch ein bisschen den zufall walten lassen so das du bei jeder bewertung eine zufalszahl addierst. so wird das spiel nicht immer gleich auch wenn dadurch nicht immer der optimalste zug genommen wird. ich hoffe ich konnte dir helfen. ich habe das überigens noch nie programmiert aber so würde ich es angehen. hat jemand noch andere ideen? Mfg AdbA ___________ www.adba.biz |
||
Timo |
Mo, Feb 14, 2005 17:48 Antworten mit Zitat
|
|
|---|---|---|
|
richtige Berwertungen von Schachfiguren:
Bauer = 1 Läufer = 3 Pferd = 3 Turm = 5 Dame = 9 damit lässt sich doch was anfangen
Das beste was du machen könntest, währe dir ein Schachbuch oder ein gutes Schachspiel zu besorgen. Es gibt einige Taktiken, die die KI dann draufhaben sollte. Diese muss man deshalb erstmal seleber verstehen (z.b. Outposting, immer möglichst viele Felder gedeckt halten, etc.) |
||
|
|
Spikespine |
Mo, Feb 14, 2005 18:34 Antworten mit Zitat
|
|---|---|---|
|
Um ein Schachspiel zu programmieren reicht es nicht aus zu wissen, wie wertvoll die einzelnen Figuren sind und ein Schachbuch zu besitzen.
Ich schätz mal man müsste schon entweder selbst Schachprofi sein oder einen einstellen, der die KI ausarbeitet... ich hab mal ne 4-gewinnt KI versucht zu proggen. Ich hab mich wochenlang mit dem Spiel auseinandergesetzt bis ich jeden Gegner schlagen konnte. Die KI war natürlich mit if-abfragen, die sortiert nach priorität waren: zuerst wurde geprüft, ob gefahr besteht, zu verlieren. Dann wurde die eigene Taktik in angriff genommen. leider war es damals zu schwierig für mich und ich bin gescheitert... 
|
||
NetPad |
Mo, Feb 14, 2005 20:01 Antworten mit Zitat
|
|
|---|---|---|
|
hmmm...bei brettspielen wird eigentlich immer das minimax prinzip verwendet. da wird wirklich JEDER schachzug berechnet und bewertet. um den computer nicht ins unendliche rechnen zu lassen gibt es möglichkeiten spielzüge ausfallen zu lassen.
über google wird man sicherlich fündig. grs NP |
||
- Zuletzt bearbeitet von NetPad am Mo, Feb 14, 2005 20:17, insgesamt einmal bearbeitet
|
PSY |
Mo, Feb 14, 2005 20:15 Antworten mit Zitat
|
|---|---|---|
|
Hoi,
die Anzahl aller möglichen vorstellbaren Züge in einem Schachspiel (nicht die Anzahl aller möglichen Stellungen) ist wahrscheinlich grösser als die Anzahl der Atome im Universum, deshalb kommt ne Vorausberechnung aller möglichen Züge schonmal nicht in Frage
Um dies zu umgehen, arbeiten Schachprogramme quasi nach einer "intelligenten" BruteForce Methode. Die bekannstesten Algorithmen sind minimax, alpha-beta und nullmove bzw. eine Kombination davon. Grob: Die momentane Position hat einen bestimmten Stellungswert. Züge werden in Bäume mit verschiedenen Knoten bzw. Blättern zerlegt, denen jeweils bestimmte Werte zugeordnet werden. Verspricht ein Ast eine geringeren Erfolg nach wenigen Zügen, wird er ganz ausser acht gelassen und nicht bis zur Maximaltiefe untersucht. Somit werden jede Menge Berechnungen gespart. Der A-B Algorithmus baut nur die Teile eines Baumes auf, in denen die Möglichkeit besteht einen besseren Zug zu finden, als den Besten der zur Zeit bekannt ist. Das Prinzip welches dahinter steckt lautet: Wenn Du feststellst, dass ein Zug schlecht ist, schaue nicht nach, wie schlecht er wirklich ist. Durch Figurenwerte und bestimmte Stellungssituatinen kann festgestellt werden, wie gut eine Stellung ist, z.B. wird kann ein weisser Doppelbauer die Gesamtbewertung um 0.5 Punkte senken, uswusw. Je mehr dieser speziellen Möglichkeiten abgefragt werden, umso besser arbeitet das Programm. Die Werte für die Figuren sollten nicht zu klein gewählt werden, z.b. anstatt Bauer 1, Springer 3.5, König 20 sollte lieber mit Bauer 100, Springer 350, König 9999 gerechnet werden. Das lässt mehr Spielraum, vor allem wenn bestimmte Stellungssituationen (Doppelbauer, Läuferpaar, isolierter Bauer, Rochade usw.) noch mit berücksichtigt werden. Zitat: 100.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 TerraByte
Das reicht bei WEITEM nicht aus
Es müssen nicht nur alle Stellungen, sondern auch alle Folgezüge der Stellung bis zum Matt gespeichert werden, d.h. alle möglichen Zugkombies in Bäumen speichern. Wie gesagt, die Anzahl der Atome im Universum ist Dreck dagegen
Allein bei TicTacToe (9 Felder und quasi nur 2 "Figuren") gibts 362880 -wenn ich mich nicht aufm Rechner vertippt hab- Äste. Allerdings frühzeitiger Abbruch wegen Partiegewinn nicht berücksichtigt. Probier lieber erstmal was leichteres, z.B. 4 gewinnt wie viele hier schon gesagt haben. P.S. Um ein gutes Schachprgramm zu schreiben muss man nicht zwangsläufig gut Schach spielen können. PSY |
||
Klaas |
Mo, Feb 14, 2005 20:35 Antworten mit Zitat
|
|
|---|---|---|
|
@PSY:
Ich wüßte nicht warum man alle Folgezüge speichern sollte (abgesehen davon das die Methode sowieso schwachsinn ist). Ein Rechner würde bei der Situationsanalyse immer auf die gleiche Reaktion kommen, deshalb müßte man nur die eine Reaktion speichern. Außer natürlich er arbeitet mit gewissen Strategien die die Situation vorher betrachten. also mag es für ein TicTacToe evtl. 362880 verscheidene Spielverläufe geben aber nur weniger als 81 Situationen. |
||
Timo |
Mo, Feb 14, 2005 22:24 Antworten mit Zitat
|
|
|---|---|---|
|
nur mal so, eigentlich gibt es beim Schach unendlich viele möglichkeiten, oder? Man kann Züge ja auch wieder rückggängig machen, zählen aber als weitere möglichkeit. Spätestens erledigt hat es sich, wenn nur noch die beiden könige übrig sind
|
||
NetPad |
Mo, Feb 14, 2005 22:48 Antworten mit Zitat
|
|
|---|---|---|
|
Zitat: nur mal so, eigentlich gibt es beim Schach unendlich viele möglichkeiten, oder? Man kann Züge ja auch wieder rückggängig machen, zählen aber als weitere möglichkeit. Spätestens erledigt hat es sich, wenn nur noch die beiden könige übrig sind
eben nicht! es werden ja durch verschiedene analysen einzelne spielverläufe abgebrochen! Zitat: Ich wüßte nicht warum man alle Folgezüge speichern sollte (abgesehen davon das die Methode sowieso schwachsinn ist). Ein Rechner würde bei der Situationsanalyse immer auf die gleiche Reaktion kommen, deshalb müßte man nur die eine Reaktion speichern. Außer natürlich er arbeitet mit gewissen Strategien die die Situation vorher betrachten. also mag es für ein TicTacToe evtl. 362880 verscheidene Spielverläufe geben aber nur weniger als 81 Situationen. 1. WENN diese methode schwachsinn ist, sind die entwickler des schachcomputers, der den schachweltmeister geschlagen hat, alles schwachköpfe... 2. aus welchem grund sollte der computer bei einer situationsanalyse immer auf die gleiche reaktion kommen???? grs NP |
||
Hot-BitSieger des B2D Retro Wettbewerb / Aug 04 |
Mo, Feb 14, 2005 23:52 Antworten mit Zitat
|
|
|---|---|---|
|
Hoi.
Ich gebe PSY in allem Recht ! Da ich sehr viel Schach spielte, und mich das drumherum schon immer interessiert hat, habe ich die gleichen Informationen wie PSY. Ich habe irgendwo noch ein klitzekleines Schach-Programm, von Richard Lang, dem mehrmaligen Weltmeister der Schach-Computer-Programmierer. Dieses kleine Programm, hat ca. 80 KB, schlägt die meisten, aufgeblasenen anderen Programme, daß es nur so eine Freude ist. Ich habe nicht mal den Funken einer Chance. Und dieser Richard Lang kann nicht mal ausgezeichnet Schach spielen ! Toni |
||
|
... ..... .i.. ...
*** Sieger des BB-Gameboy-Contest 2004 Sieger des Blitzbaster 2D-Minigolf-Contest 2005 *** |
||
Übersicht
BlitzBasic Beginners-Corner
Powered by phpBB © 2001 - 2006, phpBB Group