PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Damespiel entzaubert


Avalox/Gast
2007-07-20, 08:55:26
http://www.cs.ualberta.ca/~chinook/

Informatiker in den USA haben ein Dame Spielprogramm entwickelt, welches nicht mehr verlieren kann.
Der Gegenspieler schafft so maximal einen Patt.

Vor Jahren habe ich mich mal zum Thema Schach mit einem KI Entwickler gesprochen. Dieser war damals der Meinung, dass in nächster Zeit Schach entzaubert werden wird. Es wird sich herausstellen, dass entweder Weiss immer gewinnt, oder immer in einem remis endet, wenn sich nicht einer von beiden blöd anstellt.
Einfach ein komplexeres Tic/Tac/Toe.

Nun ist dieser Stand zwar im Schach noch nicht erreicht, aber nun im Damespiel. Auch dort wie bei Tic/Tac/Toe ein Patt als maximales Spielergebnis.

Cyphermaster
2007-07-20, 09:23:14
Jedes Spiel, daß absolut ausgewogen ist (= auch keine Zufalls-Elemente enthält), kann bei "quasi-unfehlbaren" Spielern nur Unentschieden ausgehen. Interessant ist eher, wie hoch der Komplexitätsgrad der Programmierung geworden ist, um immer komplexere Spielmodelle zu "knacken".

Monger
2007-07-20, 09:24:48
Die Spielzüge bei Dame sind natürlich viel homogener als bei Schach, was die möglichen Spielzüge doch drastisch reduziert...

Trotzdem ist das natürlich krass. Die Anzahl der Züge muss immer noch gigantisch groß sein.

Monger
2007-07-20, 09:37:54
Jedes Spiel, daß absolut ausgewogen ist (= auch keine Zufalls-Elemente enthält), kann bei "quasi-unfehlbaren" Spielern nur Unentschieden ausgehen. Interessant ist eher, wie hoch der Komplexitätsgrad der Programmierung geworden ist, um immer komplexere Spielmodelle zu "knacken".

Ich bin nicht sicher, ob das richtig ist. Ich denke, einen eindeutigen Lösungsweg gibt es nur dann, wenn es auch nur ein einziges Ziel gibt. Im Schach ist das nunmal das Schlagen des Königs, d.h. alle Strategie zentriert sich im Endeffekt um diese eine Figur. Bei Dame ist es schlicht die Anzahl aller Spielfiguren.

Sobald du aber ein Spiel hast, was alternative Lösungswege bietet (Skat z.B. kennt Mehrdeutigkeiten beim reizen, und iirc verliert man beim Grand, wenn der Gegner blank spielt, d.h. nicht einen einzigen Stich macht).

Mir fällt jetzt spontan kein klassisches Spiel ein, dass keinen Zufallsfaktor hat, aber mehrdeutige Lösungswege kennt, aber imho ist das durchaus denkbar.

Lyka
2007-07-20, 09:40:20
ein guter Artikel steht unter Heise

http://www.heise.de/newsticker/meldung/92996/from/rss09
|
V
Zugmöglichkeiten:

Nachdem die Zweisteiner-Datenbank vorliegt, kann man sich an die Dreisteiner machen, wobei die Gewinnkondition im Übergang in eine gewonnene Zweisteiner-Stellung besteht. Die Zehnsteiner-Datenbank enthält mehr als 39 Billionen Stellungen, Achtsteiner immerhin noch ca. 440 Milliarden. Auch andere Programmierer haben mittlerweile Zehnsteiner berechnet und verteilen sie gegen einen Unkostenbeitrag auf Festplatte; die Achtsteiner gibt es zum Herunterladen.

Cyphermaster
2007-07-20, 09:48:20
Gleichrangige alternative Lösungswege entsprechen einem Zufallsfaktor, da keine fakten-basierte Enscheidung für eine der Alternativen möglich ist.

BAGZZlash
2007-07-20, 10:38:47
Wer sich ein Wenig mit Spieltheorie (http://de.wikipedia.org/wiki/Spieltheorie) auskennt, kann theoretisch zeigen, daß es für Schach eine gewinnende Strategie (http://react.cs.uni-sb.de/publications/perspektiven.pdf) gibt.

Gast
2007-07-20, 10:49:48
Jedes Spiel, daß absolut ausgewogen ist (= auch keine Zufalls-Elemente enthält), kann bei "quasi-unfehlbaren" Spielern nur Unentschieden ausgehen. Interessant ist eher, wie hoch der Komplexitätsgrad der Programmierung geworden ist, um immer komplexere Spielmodelle zu "knacken".
So würde ich das auch sehen. Bei immer größerer Rechenleistung und verfügbaren Speicher sollte das Entzaubern derartiger Spiele eigentlich kein Hexenwerk mehr sein. Viel interessanter ist jedoch, den Code und die Algorithmen möglichst schlank und effizient zu proggen.
Daher finde ich auch die aktuellen Fritz! -Schachprogramme deutlich faszinierender als beispielsweise die Aktion mit Deep Blue (hieß das Ding so?). Zwar mag bei Fritz! vs. Deep Blue der Gewinner klar sein, aber dafür kommt Fritz afaik mit einem Bruchteil der Rechenleistung aus und kann selbst Profispieler zur Verzweifelung bringen.

Senior Sanchez
2007-07-20, 11:01:07
@Gast
Das sehe ich genauso.

Ich weiß man auch nicht, ich finde das immer nicht so toll, wenn KIs nur aufgrund ner fetten Datenbank gewinnen. Dass es ohne Datenbank aber sehr schwer ist, zeigt ja Go. Momentan ist kein Computerprogramm in der Lage Profispieler zu schlagen, da das Spiel eben so ungeheuer viele Kombinationen bietet und hauptsächlich auch durch Intuition bestritten wird.

DeX
2007-07-20, 11:06:39
War Dame nicht schon lange entzaubert? Zumindest das habe ich schon gehröt. Da das Spiel selber auch recht simpel ist hat mich das auch weniger gewundert.

Wobei Poker z.B unmöglich entzaubert werden kann. Nicht auf ein Match gesehen.

Senior Sanchez
2007-07-20, 11:13:45
War Dame nicht schon lange entzaubert? Zumindest das habe ich schon gehröt. Da das Spiel selber auch recht simpel ist hat mich das auch weniger gewundert.

Wobei Poker z.B unmöglich entzaubert werden kann. Nicht auf ein Match gesehen.

Nope, Mühle war entzaubert ;)

paul.muad.dib
2007-07-20, 11:18:41
Jedes Spiel, daß absolut ausgewogen ist (= auch keine Zufalls-Elemente enthält), kann bei "quasi-unfehlbaren" Spielern nur Unentschieden ausgehen. Interessant ist eher, wie hoch der Komplexitätsgrad der Programmierung geworden ist, um immer komplexere Spielmodelle zu "knacken".
Gleichrangige alternative Lösungswege entsprechen einem Zufallsfaktor, da keine fakten-basierte Enscheidung für eine der Alternativen möglich ist.

Beide Aussagen sind falsch. Wenn du Interesse daran hast, lies dich mal ein wenig in Spieltheorie ein. Schach ist prinzipiell ebenfalls lösbar, d.h. nach der Auslosung der Seiten steht eigentlich schon fest, wer gewonnen hat, man weiß allerdings noch nicht, ob das Schwarz oder weiß ist.

In der Spieltheorie geht es um die beste AW auf eine Strategie/Zug eines Gegners. Oft gibt es hier ein Gleichgewicht, d.h. es steht von vornherein fest, welche Alternative die beste ist. Ein bekanntest Beispiel ist das sog. Gefangenendilemma, wo es ein GG in dominanten Strategien gibt. Unabhängig von der Strategie der Mitspieler ist eine am besten.
Etwas komplizierter wird es, wenn das Spiel mehrere Stufen hat. Dies löst man meistens über Rückwärtsinduktion, man fängt also mit dem letzen Zug an.

Noch blöder wird es, wenn keine dominanten Strategien existieren. Dann gibt es aber häufig ein oder mehrere Nash-GG. Ein Nash-GG ist erreicht, wenn die Strategie des zweiten Spielers die beste Antwort auf eine Strategie des ersten Spielers ist und der ersten Spieler hierauf wiederum am besten mit seiner vorherigen Antwort reagiert.

Sollte kein Nash-GG in reinen Strategien existieren, kommt tatsächlich der Zufall ins Spiel. Beispiel für so ein Spiel ist z.B. Schere, Stein, Papier. Hier werden die Strategien dann zufällig, aber mit festgelegten Eintrittswahrscheinlichkeiten bestimmt. Trotzdem existiuert dann eine Lösung in Form eines Nash-GG in gemischten Strategien.

Simon Moon
2007-07-20, 11:26:21
Wobei Poker z.B unmöglich entzaubert werden kann. Nicht auf ein Match gesehen.

Geht garnicht - auch über längere Zeit hinweg nicht. Man kann durchaus über längere Zeit "vorwärts" machen bzw. damit Geld verdienen, wenn man es beherrscht, aber die Mathematik darin ist nur ein Teil des Spiels. Der andere Teil ist Menschenkenntnis und das lässt sich nun mal nicht zu 100% beherrschen.
Bei 5 Card Stud würd ich sogar sagen, hat Mathematik eine ziemlich untergeordnete Rolle, da man viel zu wenig Daten hat um die Chancen überhaupt sinnvoll zu berechnen.

Gast
2007-07-20, 11:31:11
Doch...Sensoren die die Gehirnströme des Gegenübers auswerten und dessen Blatt kennen;)

Gast
2007-07-20, 11:32:06
Naja, sobald eine Zufallskomponente wie Würfel o.ä. (z.B. bei Kartenspielen) mit ins Spiel kommen, sollte das Entzaubern auch unmöglich werden, da nur noch mit Wahrscheinlichkeiten gearbeitet werden kann.
Nebenbei finde ich Dame interessanter als Schach. Zwar ist Schach deutlich Komplexer aber Dame bietet trotz der Simplizität der Zugmöglichkeiten immernoch eine erstaunliche Komlexität. Muß mich mal über Go informieren, das könnte mir gefallen.

Cyphermaster
2007-07-20, 11:34:38
@paul.muad.dib:

Thx für den Hinweis - liest sich beim Drüberschauen interessant. Werd ich mir wohl bei Gelegenheit echt mal antun. Ist auch im zwischenmenschlichen Bereich gar nicht mal so uninteressant... :uponder:

Gast
2007-07-20, 11:37:21
@ Cyphermaster

Die Dinge sind bei Wiki ganz gut und verständlich beschrieben - nur so als Tip.

rotalever
2007-07-20, 11:45:18
Ich weiß man auch nicht, ich finde das immer nicht so toll, wenn KIs nur aufgrund ner fetten Datenbank gewinnen. Dass es ohne Datenbank aber sehr schwer ist, zeigt ja Go. Momentan ist kein Computerprogramm in der Lage Profispieler zu schlagen, da das Spiel eben so ungeheuer viele Kombinationen bietet und hauptsächlich auch durch Intuition bestritten wird.
Ein Menschlicher Spieler hat aber auch Erfahrung und besonders die Profis kennen sehr viele Dinge auswendig. Eine Datenbank würde ich deswegen keinesfalls als "unfair" ansehen.

Simon Moon
2007-07-20, 12:34:30
Naja, sobald eine Zufallskomponente wie Würfel o.ä. (z.B. bei Kartenspielen) mit ins Spiel kommen, sollte das Entzaubern auch unmöglich werden, da nur noch mit Wahrscheinlichkeiten gearbeitet werden kann.

Wie du schon sagtest, es ist eine Zufallskomponente. Als Bank, mit beinahe unendlichen Reserven, kannst du dich darauf verlassen, aber als Spieler mit endlichen Reserven nicht. Das liegt daran, dass es eben durchaus auch die möglichkeit gibt, dass eine ungünstige Zahlenreihenfolge länger dauern kann, als die Geldreserven gross sind - und wenn man mal pleite ist, ist man pleite.

Bsp. beim Roulette: (die Null ignorieren wir mal) Ich setze 1€ auf Rot. Gewinn ich, krieg ich 2€ retour, verlier ich hab ich -1€. Ich verlier nun aber, also setz ich 2€ auf Rot, gewinn ich, hätte ich insgesamt 1€ vorwärts gemacht, verlier ich hätte ich -3€. Ich geh wieder vom verlieren aus und setz nun 4€ auf Rot, wieder dasselbe, gewinn ich, hab ich 1€ vorwärts gemacht, verlier ich, hab ich -7€. Wenn ich also immer verdopple, halbiert sich die Wahrscheinlichkeit bei jedem Zug das ich verliere und irgendwann werd ich den einen € wieder raus haben. Sofern ich unendlich viel Geld habe, klappt das auch (aber nach 17 Zügen wären es schon 2€^16+1€ oder ~65k€ die ich verloren habe, wobei die Wahrscheinlichkeit 17x hintereinander zu verlieren 100/2^17 ist oder ~0.0008% - aber eben nicht unmöglich), aber bekanntlich hat das keiner.

Der Grund wieso man beim Roulette auf längere Sicht aber nicht gewinnen kann, ihr ahnt es schon, ist die Null. Da sie wieder Rot noch Schwarz ist, kippt sie die Gewinnchancen auf etwas weniger als 50% (48.6486%). Ok, bei unendlichem Geld immer noch kein Hindernis, dann wäre die Chance nach 17x Setzen zu verlieren auch noch ziemlich genau 0.0008% (ok, eine extrem winzige Abweichung ist vorhanden) - also ähnlich gut. Nun gibt es aber ein meist ein Limit, das 12'000x höher ist, als der Minimum betrag. Tönt nach viel, ist es aber nicht. Bereits nach 14 mal verdoppeln, hat man dieses Limit erreicht, die Chancen dabei immernoch verloren zu haben steigen somit auf etwa 0.00627%.

Diese 0.00627% entsprechen nun etwa gut jedem 15949sten Spieler, der insgesamt 1€+2€+4€+8€...+8192€ oder 2€^14-1€ oder 16383€ verliert, alle anderen gewinnen jedoch ihren einen 1€ Wieder. Bleibt netto für das Kasino 1x 16383€ - 15948x 1€ = 434€ fürs Kasino über.

Nun spielen aber nicht alle so diszipliniert und jede Abweichung von der Taktik vergrössert den Gewinn für das Kasino nur.

Ok, ich hoffe das war nicht zuviel :usad:


Btw. an den der Hirnströme messen will: Klar, aber das sehe ich als betrug an. Ebenso gut kann man auch direkt das Blatt miteinberechnen, kommt auf selbe raus. Ist dies für beide Seiten die Situation, im Poker versteht sich, würde es einfach immerhin und her schwanken (wegen der Blinds, Antes) wenn beide unendlich Chips hätten, ansonsten würde irgendwann der Fall eintreten, dass einer keine Chips mehr hätte.

PS: das ist das witzige am Poker, man spielt nicht gegen die Bank (die bekommt ihr Geld in Form von Eintrittsgebühren oder Rakes, periodische, kleinere Beträge, die jeweils von den Spielern bezahlt werden), welche allgemein immer einen Vorteil hat, sondern gegen andere Spieler mit exakt denselben Chancen - gewinnen tut der, welcher die Fehler der anderen erkennt. Gibt auch hier viel Theorie - aber das wichtigste ist Menschenkenntnis. (ok, bei wenig versierten Spielern reicht es schon, die Pot Odds zu beachten und so gewinnt man auf die länge)

Senior Sanchez
2007-07-20, 13:35:30
Ein Menschlicher Spieler hat aber auch Erfahrung und besonders die Profis kennen sehr viele Dinge auswendig. Eine Datenbank würde ich deswegen keinesfalls als "unfair" ansehen.

Das es unfair sei, habe ich nicht gesagt.

Natürlich hat ein menschlicher Spieler auch Erfahrung und kennt auch Züge auswendig. Allerdings und das ist der große Unterschied, zieht er auch Schlussfolgerungen und sieht Zusammenhänge sodass er auch ohne die Datenbank gut spielen könnte.

Die KIs können das zwar im Grunde fast auch, aber lange nicht so gut. Sie erschlagen lieber alles mit einer Datenbank, die sämtliche möglichen Stellungen und die nächstbesten Züge enthält.

Moorhuhn-Panzer-General
2007-07-20, 14:38:29
Das hier ist schon ein äußerst merkwürdiger Thread. Eigentlich ist jedes wirkliche Spiel "entzaubert", sobald an einem Ende des Tisches (oder gar an allen) ein Computer sitzt (Meine Meinung). Hier zeigt sich ein frappierender Mangel an Kultur und Intelligenz bei vielen Mathematikern und Informatikern, die ein Spiel und die zugehörigen Strategien allein unter dem Gesichtspunkt des Gewinnens sehen können. Mal ein Beispiel aus der Praxis: Das Hütchen-Spiel -> Sinn und Zweck des Hütchenspiels ist es in erster Linie sein Gegenüber durch schlechte Leistungen in Sicherheit zu wiegen, bevor man zum großen Rundumschlag ausholt. Das gleiche gilt für alle anderen Spiele (Schach, Poker, Fußball, Tennis, Billard, Karriere usw. usf.).

Überhaupt auf die Idee zu kommen, eine vom Computer berechnete Strategie einzusetzen, ist schon eine besondere Form von Nichtverstehen/Ignoranz. Wahrscheinlich kommt sowas durch die 'fachidiotische' Ausbildung vieler Informatiker/Mathematiker, die nur noch in 'Problemlösungen' denken und den Sinn eines Spiels (Erlernung sozialadäquater Verhaltensweisen bei Erzeugung zwischenmenschlicher Emotionen unter RealLife-Bedingungen) schon längst vergessen haben.

Es sei denn, man sieht das ganze unter therapeutischen Gesichtspunkten für sozial unterentwickelte Individuen, mit denen sich schon im Kindesalter niemand ernstlich befassen wollte (Akademikerkinder). Das sind die, die schon nach 5 Minuten ihre Spielsteine/Karten auf den Tisch knallen, in der zutreffenden Annahme, daß sie das Spiel nicht mehr gewinnen können. Ein Mathelehrer würde in so einem Fall sicher in schiere Begeisterung ausbrechen und die Note 'eins' geben, weil der Sohnemann seine Chancen korrekt ausgewertet hat. - Bei geistig noch gesunden Menschen gibts für diese Form von 'mathematischer Weitsicht' allerdings eine gepfefferte Backpfeiffe und/oder Stubenarrest (solange es noch was hilft). ;)

DeX
2007-07-20, 14:45:57
Da hast du irgendwie recht. Denn dieses Ganze "Rumgerechne" macht alles nur Kaputt und nichts anderes..

Hier sind es Schachcomputer wo anders sind es irgendwelche Bots..
Das eine oder andere mal möchte man einem Entwickler für sowas die Rübe spalten ;)

Gast
2007-07-20, 14:55:55
Besonders beeindruckend finde ich, welche Rechenleistung selbst heutzutage im 21. Jahrhundert nötig ist, um ein Spiel zu gewinnen, das bereits Kinder erfolgreich beenden können.

Senior Sanchez
2007-07-20, 15:06:03
Man darf das glaube ich nicht so eng und nur aufs Spiel begrenzt sehen.

Gerade bei Spielen macht es doch extremen Spaß neue Lösungen auszuprobieren um zu sehen, wie sie sich schlagen. Und genau dazu dient sowas doch auch: zu sehen wie gut der Computer mittlerweile in der Lage ist, komplexe Situationen einzuschätzen und möglichst gut zu handeln.

Das das nicht nur auf Spiele begrenzt ist zeigt sich doch in unserer heutigen technischen Welt: Digitale Kameras, Fahrzeuge, Medizin - alles basiert zum Teil auf Entdeckungen die im Bereich der KI gemacht worden. Und diese KIs wurden eben auch häufig auf spielerische Weise entwickelt.

Viele Ideen aus diesem Gebiet stammen auch aus der Natur (evolutionäre Algorithmen, künstliche neuronale Netze, etc.), wie vieles eben auch in der realen Welt.

Und somit ergibt das schon Sinn.

Aber der Post von Moorhuhn-Panzer-General erinnert mich sehr an Herrn Prof. Weizenbaum, von dem ich vor etwa nem Monat nen Vortrag hören durfte. Er ist ja einer der größten Kritiker und aus meiner Sicht aber nen ziemlich großer Schwarzmaler der in allem nur das schlechte sieht.

Senior Sanchez
2007-07-20, 15:10:14
Besonders beeindruckend finde ich, welche Rechenleistung selbst heutzutage im 21. Jahrhundert nötig ist, um ein Spiel zu gewinnen, das bereits Kinder erfolgreich beenden können.

Vorsicht, starker Apfel-Birnen-Vergleich.

Auf meinem PDA läuft auch ein Dame-Programm und ich behaupte, dass es in 99% aller Fälle ein Kind locker im Dame-spielen schlagen würde. Da steckt keine große Rechenleistung hinter.

Man kann nicht einfach vergleichen zwischen etwas können und etwas perfekt können! Du kannst auch denke ich mal 100m laufen. Ist doch dann erstaunlich wieviel Arbeit ein professioneller Sprinter im 21. Jahrhundert investiert, der ja nur das gleiche macht. Merkst du wie dein Vergleich hinkt?

Zwischen etwas kennen und etwas perfekt zu beherrschen besteht ein himmelweiter Unterschied! Und ich kenne keinen Menschen, der Dame perfekt beherrscht.

Simon Moon
2007-07-20, 15:13:15
Das hier ist schon ein äußerst merkwürdiger Thread. Eigentlich ist jedes wirkliche Spiel "entzaubert", sobald an einem Ende des Tisches (oder gar an allen) ein Computer sitzt (Meine Meinung). Hier zeigt sich ein frappierender Mangel an Kultur und Intelligenz bei vielen Mathematikern und Informatikern, die ein Spiel und die zugehörigen Strategien allein unter dem Gesichtspunkt des Gewinnens sehen können. Mal ein Beispiel aus der Praxis: Das Hütchen-Spiel -> Sinn und Zweck des Hütchenspiels ist es in erster Linie sein Gegenüber durch schlechte Leistungen in Sicherheit zu wiegen, bevor man zum großen Rundumschlag ausholt. Das gleiche gilt für alle anderen Spiele (Schach, Poker, Fußball, Tennis, Billard, Karriere usw. usf.).


Es kommt imo durchaus auf das Wesen des Spiels an. Wenn ich eben gegen eine Bank spiele, die einen Mathematischen Vorteil hat, nützt mir auch der grösste Optimismus und die meiste Erfahrung nichts.

Aber es gibt durchaus auch andere Spiele, in denen der psychologische Aspekt wesentlich ausgeprägter ist (mein Liebling Poker) - da ist Menschenkenntnis wirklich wichtiger als Mathematik. Bsp. Im Poker hilft es mir nichts, wenn ich mit meinem Full House 99% Chance habe zu gewinne, aber zu blöd bin, dem anderen anzusehen dass er 4 Gleiche hat. Das ändert jedoch nichts daran, dass das Ganze ein Mix aus Wahrscheinlichkeit, Menschenkenntnis und Glück ist. Eine ausgewogene Mischung gewinnt eher, als jemand der sich nur auf einen Teilaspekt verlässt.

Was das mit gewinnen angeht: Wenn ich nicht gewinnen wollte, wieso sollte ich dann spielen? Ich mein jetzt nicht mit Lego oder so, aber Gesellschaftspiele/Sport sind bekanntlich immer auch Wettkämpfe.

Das Beispiel mit dem Roulette hab ich eigentlich nur aufgezeigt, dass trotz Schwankungen beim einzelnen, auf die Menge eigentlich nur ein Resultat herauskommt - und ich frag mich wirklich, wie man danach noch Roulette spielen kann. Das ist reines Glück, keine Menschenkenntnis oder Wahrscheinlichkeit hilft dir da, Erstere ist egal und Letztere ist gegen dich.

Ausserdem heisst es ja nicht, dass wenn man seine Chancen ausrechnen kann und zu einem schlechten Ergebnis kommt, dass man dann aufgeben muss - man kann in den meisten Spielen noch bluffen und auf sein Glück hoffen.

Gast
2007-07-20, 15:30:16
@ Moorhuhn Panzer General

Ich sehe das völlig anders. Es geht hier im Prinzip nicht ums Gewinnen sondern einfach nur um eine möglichst elegante Lösung eines Komlexen Problems. Dabei ist mMn die Nutzung großer Datenbanken bestimmt nicht der Königsweg.
Das Zusammenstellen aller möglichen Spielzüge und Varianten, auf die zurückgegriffen werden kann, ist für mich in etwa so sinnvoll, als wenn für die Lichteffekte in einem Egoshooter nicht eine Textur vorliegt, die in Echtzeit berechnet wird, sondern für alle denkbaren Beleuchtungszustände eine extra Textur verwendet wird...
Natürlich wird man wohl nicht völlig auf Datenbanken verzichten können aber im Prinzip geht es doch darum, Komplexe Vorgänge besser verstehen zu lernen. In der Natur ist es doch ähnlich. Viele sehr intelligent wirkende Vorgänge (z.B. Pflanzenwachstum, Schwarmverhalten) lassen sich mit erstaunlich einfachen Algorithmen lösen. Das sollte der Ansatz für derartige Projekte sein: so einfach wie möglich, so komplex wie nötig.

Monger
2007-07-20, 15:53:06
Ich denke, dass Computer gerne an Spielbretter rangesetzt werden, hat den einfachen Grund, dass dies etwas ist was eigentlich dem Rechner extrem gut liegt.

Eine Menge natürliche Zahlen, relativ simple Berechnungen, viele Assoziationen - das sind die typischen Stärken eines Rechners. Viele andere Bereiche der Mathematik überfordern den Rechner einfach gnadenlos, oder lassen sich extrem schlecht formulieren. Spielrunde für Spielrunde auszuwerten, entspricht quasi dem PC Naturell.

Gast
2007-07-20, 16:24:58
Was das mit gewinnen angeht: Wenn ich nicht gewinnen wollte, wieso sollte ich dann spielen? Ich mein jetzt nicht mit Lego oder so, aber Gesellschaftspiele/Sport sind bekanntlich immer auch Wettkämpfe.
Es geht nicht nur um das Gewinnen, sondern darum sich friedlich mit seinen Mitmenschen zu beschäftigen (auch und gerade wenn sie andere Sprachen sprechen, andere Religionen besitzen, andere Mentalitäten besitzen). Was bietet sich da besser an, als sich mit anderen Menschen friedlich im Rahmen von Spielregeln zu vergleichen. In erster Linie steht immer das gesellschaftliche Ereignis. Der gemeinsame Weg ist das Ziel.
Im wirklichen Leben ist es häufig sogar so, daß man verlieren muß bzw. sich einordnen muß, um weiter zu kommen. Wer das nicht rafft hat zwar in Mathe eine "eins" auf dem Zeugnis, ist dafür aber gesellschaftlich isoliert (Streber). Und Leute die nur irgendwo mitmachen, wenn es für sie was zu gewinnen gibt, sind meist ganz schnell wieder da, wo sie hingehören: Allein vor ihrem PC.

Spasstiger
2007-07-20, 16:47:21
Es geht nicht nur um das Gewinnen, sondern darum sich friedlich mit seinen Mitmenschen zu beschäftigen (auch und gerade wenn sie andere Sprachen sprechen, andere Religionen besitzen, andere Mentalitäten besitzen). Was bietet sich da besser an, als sich mit anderen Menschen friedlich im Rahmen von Spielregeln zu vergleichen. In erster Linie steht immer das gesellschaftliche Ereignis. Der gemeinsame Weg ist das Ziel.
Ich denke, du spielst da auch auf Go an, bei welchem das Gewinnen tatsächlich nicht im Vordergrund steht. Auch vom Spielablauf her geht es nicht ums Auslöschen der Gegners, anders als z.B. bei Schach.
Aber das macht Go auch so unglaublich komplex, der Computer müsste das Spiel im Prinzip in allen Variationen durchrechnen (bis jeweils keine Steine mehr gesetzt werden können oder das Spiel durch Nichtplatzieren beendet wird), bevor ein möglicher Zug bewertet werden kann. Es gibt kein festes Ziel wie: "Schlage den König".
Außerdem weiß der Computer nicht, wann der Gegenspieler mal keinen Stein setzen will.
Die Anzahl an Platzierungsmöglichkeiten von bis zu 361 Steinen auf ebenso vielen Punkten ist einfach abartig groß.

Das dürfte wohl ein Problem sein, wo man mal Algorithmen auf Quantencomputern bemühen muss.

Simon Moon
2007-07-20, 17:11:02
Es geht nicht nur um das Gewinnen, sondern darum sich friedlich mit seinen Mitmenschen zu beschäftigen (auch und gerade wenn sie andere Sprachen sprechen, andere Religionen besitzen, andere Mentalitäten besitzen). Was bietet sich da besser an, als sich mit anderen Menschen friedlich im Rahmen von Spielregeln zu vergleichen. In erster Linie steht immer das gesellschaftliche Ereignis. Der gemeinsame Weg ist das Ziel.
Im wirklichen Leben ist es häufig sogar so, daß man verlieren muß bzw. sich einordnen muß, um weiter zu kommen. Wer das nicht rafft hat zwar in Mathe eine "eins" auf dem Zeugnis, ist dafür aber gesellschaftlich isoliert (Streber). Und Leute die nur irgendwo mitmachen, wenn es für sie was zu gewinnen gibt, sind meist ganz schnell wieder da, wo sie hingehören: Allein vor ihrem PC.

Ist ja schön und gut, ich kann mich durchaus friedlich mit meinen Mitmenschen beschäftigen. Aber das ist nicht Sinn und Zweck eines Wettbewerbs (seis nun Poker, Fussball, Mühle, Schach usw.). Darin geht es sicher um den Spass, aber damit man den hat, braucht es ehrgeiz. Stell dir mal ein Fussballspiel vor, der Stürmer sprintet nach vorne und findet "Ach ne, lieber Torwart, keine Angst, ich schiess nicht - hier hast den Ball" :ugly:

Für das miteinander gibts Dinge wie Musik machen, häcken (mit diesen winzigen, Styropor gefüllten Bällen), sich unterhalten, von mir aus Lego-Spielen, Gemeinsam etwas aufbauen, ein Problem lösen... es gibt etliche Dinge - aber ein Wettkampf ist dafür denkbar ungeeignet.

Gast
2007-07-20, 18:02:49
Das hier ist schon ein äußerst merkwürdiger Thread. Eigentlich ist jedes wirkliche Spiel "entzaubert", sobald an einem Ende des Tisches (oder gar an allen) ein Computer sitzt (Meine Meinung). Hier zeigt sich ein frappierender Mangel an Kultur und Intelligenz bei vielen Mathematikern und Informatikern, die ein Spiel und die zugehörigen Strategien allein unter dem Gesichtspunkt des Gewinnens sehen können. mir scheint, du verwechselst das Betrachten des Spiels unter dem Gesichtspunkt des Gewinnens mit der Unfähigkeit, es auch unter anderen Gesichtspunkten zu sehen.
Ich denke, Mathematiker und Informatiker sind durchaus in der Lage, auch andere Aspekte zu sehen, aber das hält sie eben nicht davon ab, sich mit der Thematik zu beschäftigen, wie das Spiel am effektivsten gewonnen werden kann. Schließlich ist das ein spannendes Gebiet, das gewiß nicht weniger unterhaltsam ist als das Spielen selbst.

Mal ein Beispiel aus der Praxis: Das Hütchen-Spiel -> Sinn und Zweck des Hütchenspiels ist es in erster Linie sein Gegenüber durch schlechte Leistungen in Sicherheit zu wiegen, bevor man zum großen Rundumschlag ausholt. Das gleiche gilt für alle anderen Spiele (Schach, Poker, Fußball, Tennis, Billard, Karriere usw. usf.).

Überhaupt auf die Idee zu kommen, eine vom Computer berechnete Strategie einzusetzen, ist schon eine besondere Form von Nichtverstehen/Ignoranz. nuja, zum einen schließt ja der Sachverhalt, daß man ein Spiel durch Täuschen des Gegners gewinnen kann, nicht aus, daß es auch durch ein rein auf Gewinnnen ausgelegte Strategie gewinnbar ist, und zum zweiten kann der Computer ja durchaus auch Täuschungstaktiken in die berechnete Strategie einfließen lassen, wenn das entsprechend programmiert wird.

und den Sinn eines Spiels (Erlernung sozialadäquater Verhaltensweisen bei Erzeugung zwischenmenschlicher Emotionen unter RealLife-Bedingungen) schon längst vergessen haben.also zum einen bezweifle ich stark, daß die von dir propagierte Idee, seinen Gegner zu täuschen um dann "zum Rundumschlag auszuholen" als sozialadäquate Verhaltensweise bezeichnet werden kann, und zum zweiten bezweifle ich noch viel mehr, daß dies der alleinige Sinn eines Spiels sein soll.

Es sei denn, man sieht das ganze unter therapeutischen Gesichtspunkten für sozial unterentwickelte Individuen, mit denen sich schon im Kindesalter niemand ernstlich befassen wollte (Akademikerkinder). Das sind die, die schon nach 5 Minuten ihre Spielsteine/Karten auf den Tisch knallen, in der zutreffenden Annahme, daß sie das Spiel nicht mehr gewinnen können. Ein Mathelehrer würde in so einem Fall sicher in schiere Begeisterung ausbrechen und die Note 'eins' geben, weil der Sohnemann seine Chancen korrekt ausgewertet hat.glaube ich nicht. Weil nach deinem eigenen Vorwurf sieht der Mathelehrer das Spiel ja nur unter dem Gesichtspunkt des Gewinnens. Und gewinnen tut man eben nicht dadurch, daß man aufgibt wenn die Chancen schlecht stehen, sondern dadurch, daß man lernt, wie man seine Chancen verbessert. ;)

Der_Donnervogel
2007-07-20, 18:36:56
Aber es gibt durchaus auch andere Spiele, in denen der psychologische Aspekt wesentlich ausgeprägter ist (mein Liebling Poker) - da ist Menschenkenntnis wirklich wichtiger als Mathematik.
Nun ja, ich gehe mal stark davon aus, daß man auch Menschenkenntnis mathematisch umsetzen kann. Auch der Mensch ist nichts anderes als eine biologische Maschine, dessen Vorgänge in seinem neuronalen Netz sich sicher auch mathematisch beschreiben lassen, bzw. simulieren lassen. Vermutlich wird aber zur Simulation eine andere Hardware/Software als heutzutage nötig sein, also vielleicht auch etwas in Richtung neuronales Netz.

Wenn das aber gegeben ist, sollte so ein Computer auch eine viel bessere Menschenkenntis haben, als jeder Mensch. Menschenkenntnis basiert letztlich auf Erfahrung. Dabei wird basierend auf ähnlichen früheren Situationen ein Vergleich mit der aktuellen Situation durchgeführt und dann die wahrscheinlichste Möglichkeit abgeschätzt. Je mehr Erfahrung, also je größer die Datenbasis, umso besser die Schätzung (Menschenkenntnis). Folglich müßte ein fiktiver Computer mit einer sehr großen Datenbasis die vielleicht einem Menschen mit jahrhundertelanger oder jahrtausendelanger Erfahrung entspricht sogar irgendwann jedem Menschen im Bereich Menschenkenntnis um Größenordnungen überlegen sein. :ugly:

paul.muad.dib
2007-07-20, 21:54:14
@Simon Moon: Roulette ist kein "Spiel", siehe unten.



Das Problem beim Poker ist, bestimmte Signale in Warscheinlichkeiten umzusetzen. Es ähnelt ein wenig dem Spiel "Treffen in New York".

Aufgabe bei diesem kooperativen Spiel ist es, dass zwei Spieler sich ohne Absprache in New York finden. Die Strategien bestehen darin, zu einer bestimmten Stelle zu gehen.

Zunächst erscheint jeder Ort gleichwertig und ein Treffen bei vom Computer festgelegten Strategien extrem unwahrscheinlich. Ein Mensch würde aber kaum zum Asia Schnellimbiss in der 23. Straße gehen, sondern zu wenigen wichtigen Punkten wie Freiheitsstatue oder Time Square. Da es nur weniger solcher Punkte gibt, ist ein Treffen für Menschen weitaus wahrscheinlicher.

Um also ein Computerprogramm für dieses Spiel zu optimieren, müsste man ihm nur beibringen, was diese Punkte sind.


Doch nun zu Poker: Prinzipiell sind die Entscheidungen hier weniger interdependent als beim Schach. Aus diesem Grund ist Roulette auch kein "Spiel" im Sinne der Spieltheorie, weil die Entscheidung, was man setzt nicht von den Einsätzen der anderen abhängt.
Auch bei Poker kann man prinzipiell immer eindeutig zwischen mitgehen und aussteigen entscheiden, wenn man die Gewinnwahrscheinlichkeit im Verhältnis zum Pott und zum Einsatz setzt. Hat man z.B. nur ein mittelmäßiges Blatt, aber es ist viel im Pott, lohnt es sich mitzugehen. Dieser Teil ist prinzipiell sehr leicht lösbar/programmierbar.

Nun kommen aber noch die Erwartungen und das Bluffen hinzu. Es kann sinnvoll sein, von der oben geschilderten Optimalstrategie abzuweichen, wenn man glaubt, dass ein Mitspieler blufft oder man selber bluffen möchte und glaubt, dass die Mitspieler den Bluff kaufen.

Die Einschätzung der Mitspieler disbezüglich ähnelt dem Treffen in New York. Auf Grund von Hintergrundwissen (Wenn es früh ist, sind die Spieler weniger risikobereit), Erfahrungen (der Mitspieler spielt sturr nach Wahrscheinlichkeiten) und Signalen (er wirkt nervös), sind bestimmte Strategien (Freiheitsstatue) wahrscheinlicher.



Der Trick wäre es daher, einem Computer genau diese Hintergrundinformationen zu geben und ihm aus dem Verhalten der Mitspieler ein Profil erstellen zu lassen. Das halte ich für lösbar, wenn die Spieler keinen direkten Kontakt miteinander haben, also etwa beim Internet-Poker.

paul.muad.dib
2007-07-20, 22:03:12
Das hier ist schon ein äußerst merkwürdiger Thread. Eigentlich ist jedes wirkliche Spiel "entzaubert", sobald an einem Ende des Tisches (oder gar an allen) ein Computer sitzt (Meine Meinung). Hier zeigt sich ein frappierender Mangel an Kultur und Intelligenz bei vielen Mathematikern und Informatikern, die ein Spiel und die zugehörigen Strategien allein unter dem Gesichtspunkt des Gewinnens sehen können. Mal ein Beispiel aus der Praxis: Das Hütchen-Spiel -> Sinn und Zweck des Hütchenspiels ist es in erster Linie sein Gegenüber durch schlechte Leistungen in Sicherheit zu wiegen, bevor man zum großen Rundumschlag ausholt. Das gleiche gilt für alle anderen Spiele (Schach, Poker, Fußball, Tennis, Billard, Karriere usw. usf.).


Es geht beim Lösen von Spielen nicht darum, zu gewinnen oder das Spiel zu entzaubern. Spieltheorie hat viele praktische Anwendungen immer dann, wenn es interdependente Entscheidungsprobleme gibt.

Ein gutes Beispiel ist die Gestaltung der UMTS-Auktion, wo spieltheoretische Kenntnisse verwendet wurden, um die "Spielregeln" zu gestalten. Und immerhin sind dabei 100 Mrd. für den Bund bei rausgesprungen.

Spiele eignen sich deshalb zum Üben, weil sie sehr klare und schnell ersichtliche Regeln haben und sehr weit verbreitet sind. Aber die Erkennnisse daraus lassen sich dann z.B. auf Verhandlungen in der Welthandelsorganisation WTO übertragen wo es um die Regeln für das "Spiel" internationalen Handel geht.

Gast
2007-07-21, 05:30:42
:| sogar für 3dc verhältnisse sehr viel nonsense in diesem thread :|

aths
2007-07-21, 13:27:24
:| sogar für 3dc verhältnisse sehr viel nonsense in diesem thread :|Dann trag doch mal was sinnvolles bei.

aths
2007-07-21, 13:29:03
:| sogar für 3dc verhältnisse sehr viel nonsense in diesem thread :|Dann trag doch mal was sinnvolles bei.


Nun ist dieser Stand zwar im Schach noch nicht erreicht, aber nun im Damespiel. Auch dort wie bei Tic/Tac/Toe ein Patt als maximales Spielergebnis.Sonst wäre das Spiel unfair. Bei Tic Tac Toe auf 3x3 hat aber der, der anfängt, einen recht großen Vorteil. Ich bevorzuge Tic Tac Toe auf 4x4 oder 4x4x4 (in 3D.) Während 3-er Tic Tac Toe in 3D nicht funktioniert (der Mittelpunkt ist zu stark) geht es bei 4-er soweit ich weiß auch in 4D noch (also 4x4x4x4.)

Gast
2007-07-21, 14:39:24
Überhaupt auf die Idee zu kommen, eine vom Computer berechnete Strategie einzusetzen, ist schon eine besondere Form von Nichtverstehen/Ignoranz. Wahrscheinlich kommt sowas durch die 'fachidiotische' Ausbildung vieler Informatiker/Mathematiker, die nur noch in 'Problemlösungen' denken und den Sinn eines Spiels (Erlernung sozialadäquater Verhaltensweisen bei Erzeugung zwischenmenschlicher Emotionen unter RealLife-Bedingungen) schon längst vergessen haben.Gut, daß du allen erklärst worin der einzige Sinn eines Spieles liegt. Jede andere Beschäftigung mit einem Spiel als die von dir propagierte hat da natürlich keinen Platz mehr.
Was hattest du nochmal über Ignoranz geschrieben?

Simon Moon
2007-07-21, 16:32:39
Der Trick wäre es daher, einem Computer genau diese Hintergrundinformationen zu geben und ihm aus dem Verhalten der Mitspieler ein Profil erstellen zu lassen. Das halte ich für lösbar, wenn die Spieler keinen direkten Kontakt miteinander haben, also etwa beim Internet-Poker.

Ok, aber eben: Online Poker. Hier fällt ein ganzer Aspekt des Spiels ins Wasser und übrig bleibt noch die mathematische / Glück Komponente. Da ist es wirklich keine Kunst mehr, einen Algorythmus zu schreiben, der gut spielt. Im Prinzip rechne ich schon selber aus, ob das Verhältnis von Pot zu meinem Einsatz, auch in etwa mit dem Verhältnis meiner Karten zum besten Blatt stimmt. Also wenn ich Gewinnchancen von 1:3 habe (also in 4 Spielen, gewinn ich einmal) und der Pot wäre 1:5, dann setz ich natürlich - ausser ich hab schon gesehen, dass der Spieler, der wettet bisher noch nie aktiv war - dann werd ich allenfalls stutzig und lass es.

Es wäre also lediglich nötig, zum einen jeweils das Verhältnis zu berechnen und zum anderen, die Spieleigenschaften der Mitspieler zu erfassen. Das kann man auch recht leicht machen.

(frei von Wiki die Begriffe, aber passt)
aggressiv: ein Spieler, der öfter und höhere Beträge setzt und erhöht als der Durchschnitt
passiv: ein Spieler, der seltener und niedrigere Beträge setzt und öfter nur mitgeht, checked oder passt als der Durchschnitt
loose: ein Spieler, der viele Hände spielt
tight: ein zurückhaltender Spieler, der nur wenige Hände spiel

Entweder er spielt wenige, aggressive oder viele, aggressive Hände. Alternativ spielt er wenige, passive oder viele, passive Hände. In diese vier Typen kann man eigentlich die meisten Spieler stecken und so jeweils darauf reagieren. Logischerweise hast du die aggressiven, tighten Spieler gerne vor dir und die passiven, immer mitgehenden Spieler lieber hinter dir. Usw. etc.

Achja und zu Roulette: Das Gefällt mir einfach, weil die Chancen so simple auszurechnen sind. Wollte damit nur verdeutlichen, dass das, was über ein paar Züge Zufall sein kann, auf die Dauer eben auch berechenbar wird und man als Spieler immer einen Nachteil hat.

@Donnervogel: Klar, aber wenn ich mir anschaue, wie langsam das diese Entwicklung noch vor sich geht, reden wir darüber wohl eher in zehn Jahren wieder.

Coda
2007-07-21, 16:55:30
Algorithmus mit i bitte. Hat nichts mit Rhytmus zu tun.

paul.muad.dib
2007-07-23, 12:18:46
Ok, aber eben: Online Poker. Hier fällt ein ganzer Aspekt des Spiels ins Wasser und übrig bleibt noch die mathematische / Glück Komponente. Da ist es wirklich keine Kunst mehr, einen Algorythmus zu schreiben, der gut spielt.
Es wäre also lediglich nötig, zum einen jeweils das Verhältnis zu berechnen und zum anderen, die Spieleigenschaften der Mitspieler zu erfassen. Das kann man auch recht leicht machen.

Achja und zu Roulette: Das Gefällt mir einfach, weil die Chancen so simple auszurechnen sind. Wollte damit nur verdeutlichen, dass das, was über ein paar Züge Zufall sein kann, auf die Dauer eben auch berechenbar wird und man als Spieler immer einen Nachteil hat.


Klar fehlt beim online-Poker ein Aspekt des Spiels. Theoretisch könnte man auch ein Programm für reales Poker schreiben, wenn die Forschung zum Anylysieren von Mimik und Gestik weiter vorrangeschritten ist. Oder man schließt die Mitspieler einfach an einen Lügendetektor an.


Nebenbei: Ich hoffe, du hast dich bei "simple" nur vertippt. Ich hasse diese ganzen Rechtschreibe und Grammatikfehler die aus dem dem Englischen resultieren. Wenn ich sowas lese wie "in 2003" oder "in Deutsch" sträuben sich mir immer die Haare.

drmaniac
2007-07-23, 13:56:30
Bsp. beim Roulette:...

Wenn ich also immer verdopple, halbiert sich die Wahrscheinlichkeit bei jedem Zug das ich verliere und ...


also es ist so: nach jedem verdoppeln und verlieren des Einsatzes ist es wieder nur 50/50 das deine Farbe doch mal kommt. Und wenn 10 x schwarz kommt und die schon 9 x verdoppelt hast und dann setzt ist es trotzdem wieder nur 50/50 für dich ;)

Das schoss mir wie der Blitz durch den Kopf als ich mit 10 Euro angefangen habe und schon das fünfte mal verdoppelt hatte (es lagen also 160 auf dem Tisch und wenn wieder nicht rot gekommen wäre, hätte ich 310 euro verloren :) kam aber dann doch ;) puhhhh

dann hab ich hier mal nachgelesen ( das hier hast du schon gut beschrieben aaaber http://de.wikipedia.org/wiki/Martingalespiel)

http://de.wikipedia.org/wiki/Spielerfehlschluss

nach dem durchlesen des Spielerfehlschlusses ...uiuiui

Nehmen wir an, wir hätten soeben viermal hintereinander Kopf geworfen. Ein Spieler könnte sich sagen "...wenn der nächste Münzwurf wieder Kopf ergibt, wäre das schon fünfmal Kopf hintereinander. Die Wahrscheinlichkeit für eine solche Reihe ist 0.55 = 0.03125; also ist die Chance, dass die Münze das nächste Mal Kopf zeigt, 1:32."

Hier liegt der Fehler. Wenn die Münze fehlerfrei ist, muss die Wahrscheinlichkeit für "Zahl" immer 0,5 betragen, nie mehr oder weniger, und die Wahrscheinlichkeit für "Kopf" muss immer 0,5 sein, nie mehr oder weniger


Ich habs dann gelassen :D

Gast
2007-07-23, 14:32:14
also es ist so: nach jedem verdoppeln und verlieren des Einsatzes ist es wieder nur 50/50 das deine Farbe doch mal kommt. Und wenn 10 x schwarz kommt und die schon 9 x verdoppelt hast und dann setzt ist es trotzdem wieder nur 50/50 für dich ;)

dass ist schon richtig, trotzdem wirst du irgendwann richtig raten.

es ist bei dieser strategie natürlich egal ob man auf rot oder schwarz setzt, oder auch abwechselnd, da bei jedem durchgang die wahrscheinlichkeit für rot und schwarz gleich hoch ist.

Simon Moon
2007-07-23, 14:47:37
dass ist schon richtig, trotzdem wirst du irgendwann richtig raten.

es ist bei dieser strategie natürlich egal ob man auf rot oder schwarz setzt, oder auch abwechselnd, da bei jedem durchgang die wahrscheinlichkeit für rot und schwarz gleich hoch ist.

Jupp, ist im Prinzip egal. Man könnte auch sagen deine chancen, 5x hintereinander zu verlieren, wären 1:32 - unabhängig wie man setzt.

Lyka
2007-07-23, 14:52:00
wie war der Spruch? "Zufall hat kein Gedächtnis". Lotto ist doch dasselbe.

übrigens: Für Dame/Schach-Spiele lohnt es sich bei PC-Software eh "nur" 2-5 Züge vorauszudenken, oder?

(bin gerade dabei, wieder Schach zu üben, bin ganz schlecht drin :D )