Entwickler-Ecke
Algorithmen, Optimierung und Assembler - KI für Kartenspiel
Flamefire - Mo 08.02.10 14:54
Titel: KI für Kartenspiel
Ich habe folgende Version eines Kartenspiels:
2 Spieler bekommen je 9 Karten mit den Zahlen von 1-9
Jeder legt (verdeckt) eine Karte.
Wessen Karte höher ist, der bekommt einen Punkt.
Die gelegten Karten werden weggenommen (also nicht nochmal spielbar)
Das ganze geht demzufolge 9 Runden.
Jetzt habe ich überlegt, wie eine KI gegen einen Random-Gegner aussehen könnte.
Dazu ein einfaches Bsp: 3 Karten.
Ich lege 3 Gegner legt 2
Stand: 1:0
Ich: 1,2
Gegner: 1,3
Was wäre für mich die bessere Wahl? Ich habe 50% Chance, dass der Gegner die 1 legt.
Also: Lege ich die 1 zu erst:
50% Chance auf 1:2 Punktstand
und 50% auf 1:1 Punktstand
Bei der 2 sieht es genauso aus.
Ist es also egal, wie man vorgeht, oder ist das nur ein schlechtes Bsp?
Welche Strategie führt mit höchstmöglicher Wahrscheinlichkeit zum Sieg?
Hab schon gedacht, das zu brute-forcen indem alle Wahrscheinlichkeiten durchgerechnet werden. Das wären dann 9!*9! Varianten...
BenBE - Mo 08.02.10 15:22
Klassisch könnte man - da alle Karten abzählbar sind - das ganze mit MinMax lösen.
Zur Strategie: Spiel erst eine Reihe niedriger Karten und zieh dann von oben nach unten deine hohen Karten.
Tastaro - Mo 08.02.10 15:22
Ich würde sagen, dass das Spiel immer unentschieden ausgeht.
Um zu gewinnen wird jeder immer seiner höchste Karte legen.
Delphi-Quelltext
1:
2:
3:
4:
| Spieler 1 Spieler 2
9 9
8 8
... ... |
Etwas langweilig auf Dauer. Oder gibt es noch Zusatzregeln die das verhindern?
Edit: Oder weiß ich auch nicht, was ich lege?
Beste Grüße
BenBE - Mo 08.02.10 15:26
@Tastaro: Wenn Du immer die höchste Karte legst, dann würd ich dich mit meiner Strategie in Grund und Boden stampfen, weil ich durch das legen einer niedrigen Karte dir erstmal deine hohen Karten rausziehe (also 1 gegen 9 von dir) und dann von oben nach unten IMMER die höhere Karte haben werde ;-)
danielf - Mo 08.02.10 15:35
Ja, Tastaro ist einfach zu besiegen ;)
Aber Flamefire meinte ja gegen einen "Random-Gegner" der zufällig irgendwelche Karten legt (also unlogisch).
Ich denke auch, dass da wieder der MinMax siegt. Da generisch...
Alternativ könnte man es wie bei "23 - Dem Film" machen.. mit Karten zählen. Man definiert einen Durchschnitt wert, und wenn der Gegner drüber ist legt man eine hohe zahl.. sonsten eine niedrige um eine hohe von ihm "auszuweichen".
Versuche es am besten mal und berichte uns :D
Tastaro - Mo 08.02.10 15:48
 BenBE hat folgendes geschrieben  : |
| @Tastaro: Wenn Du immer die höchste Karte legst, dann würd ich dich mit meiner Strategie in Grund und Boden stampfen, weil ich durch das legen einer niedrigen Karte dir erstmal deine hohen Karten rausziehe (also 1 gegen 9 von dir) und dann von oben nach unten IMMER die höhere Karte haben werde ;-) |
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| BenBE Tastaro
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
9 1 |
=> Unentschieden
Oder was geht jetzt an mir vorbei?
danielf - Mo 08.02.10 16:08
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| BenBE/Daniel Tastaro
1 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
2 1
================
8 1 |
;)
Tastaro - Mo 08.02.10 16:11
Ok, nun habe auch ich es verstanden.
Danke für eure Geduld. Ist heute eh ein blöder Tag. :(
Beste Grüße
danielf - Mo 08.02.10 16:27
Okay.. mein Tag ist sehr gut :) (sorry).
Ich hab mal einen "RandomPlayer" und einen "UpDownPlaye" implementiert und bin zu folgendem Resultat gekommen:
Ein zufälliger Spieler gewinnt durchschnittlich 30-35% der Spiele gegen einen UpDownPlayer (er legt 3,2,1).
Gruß Daniel
Program.cs:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
| static void Main(string[] args)
{
List<Card> cards = new List<Card> { new Card(1), new Card(2), new Card(3) };
int loops = 1000000;
List<Result> results = new List<Result>();
for (int i = 0; i < loops; i++)
{
results.Add(PlayRound(cards, new RandomPlayer(), new UpDownPlayer()));
}
int winsP1 = results.Count(delegate (Result r)
{
return r.Winner.Equals("Player1");
});
int winsP2 = results.Count(delegate (Result r)
{
return r.Winner.Equals("Player2");
});
Console.WriteLine("Player1 won {0}% ({1}/{2})", (100f / loops) * winsP1, winsP1, winsP2);
}
private static Result PlayRound(List<Card> cards, Player player1, Player player2)
{
Result result = new Result();
player1.SetCards(new List<Card>(cards));
player2.SetCards(new List<Card>(cards));
for (int i = 0; i < cards.Count; i++)
{
Card card_p1 = player1.PutCard();
Card card_p2 = player2.PutCard();
if (card_p1 > card_p2)
{
result.Wins++;
}
else if (card_p2 > card_p1)
{
result.Looses++;
}
else
{
result.Draws++;
}
}
return result;
} |
RandomPlayer:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| public override Card PutCard()
{
int index = _random.Next(0, _cards.Count);
Card c = _cards[index];
this._cards.RemoveAt(index);
return c;
} |
UpDown:
C#-Quelltext
1:
2:
3:
4:
5:
6:
| public override Card PutCard()
{
Card c = this._cards.Max<Card>();
this._cards.Remove(c);
return c;
} |
guinnes - Mo 08.02.10 16:29
Da ich mich ja wohl auf deine Strategie einstellen kann : :wink:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
| BenBE/Daniel Guinnes
1 9
9 1
8 8
7 7
6 6
5 5
4 4
3 3
2 2
================
1 1
Und wenn du dich auch auf meine Strategie einstellst :
BenBE/Daniel Guinnes
1 9
9 1
2 8
7 2
3 6
5 3
4 4
8 8
6 6
================
3 3 |
BenBE - Mo 08.02.10 16:51
| guinnes hat folgendes geschrieben : |
Da ich mich ja wohl auf deine Strategie einstellen kann : :wink:
Quelltext 1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| Und wenn du dich auch auf meine Strategie einstellst :
BenBE/Daniel Guinnes
1 9
9 1
2 8
7 2
3 6
5 3
4 4
8 8 <-- CHEATER!!!
6 6 <-- CHEATER!!!
================
3 3 | |
Wollte es nur erwähnt haben :P
guinnes - Mo 08.02.10 17:02
:oops: :oops: Dann eben so :
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| BenBE/Daniel Guinnes
1 9
9 1
2 8
7 2
3 6
5 3
4 4
8 5
6 7
================
4 4 |
danielf - Mo 08.02.10 17:07
Hehe.. der olle Cheater ^^
Ich hab noch einen "intelligenten" Spieler implementiert. Dieser überprüft was der Gegner für Karten gespielt hat. Wirft der Gegner hohe Karten "antwortet" er mit hohen Karten und versucht somit die Karten zu egalisieren. Auf jeden Fall ist das Ergebnis bei 3 Karten uninteressant. Alle Teilnehmer können mit einer Gewinnquote von ca. 16% rechnen (16% zu 16% bei 78% draws). Interessant wird es erst, bei mehr Karten.. beispielshalber habe ich 6 genommen.
Bei 6 Karten wendet sich das Blatt. Während Random vs. Intelligent und Random vs. UpDown immer noch Ausgeglichen ist (30%zu 30%) gewinnt beim Intelligent vs. UpDown der Intelligenz 100% der Spiele :D - Intelligenz siegt doch ;)
Gruß Daniel
IntelligentPlayer
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
| public override Card PutCard()
{
if (_opponentPlayed.Count == 0)
{
Card c = this._cards[this._cards.Count / 2];
this._cards.Remove(c);
return c;
}
else
{
int sum = 0;
foreach (var card in _opponentPlayed)
{
sum += card.Value;
}
float avager = sum / _opponentPlayed.Count;
Card c = this._cards[(int) Math.Min(Math.Round(avager,0), this._cards.Count - 1)];
this._cards.Remove(c);
return c;
}
} |
jasocul - Mo 08.02.10 17:11
Macht doch einen Wettbewerb.
Jeder Teilnehmer baut ein kleines Programm mit eigener Intelligenz und lässt es gegen Andere antreten. Dann kann jeder seine eigene KI basteln und mal sehen, wer die beste Variante hat.
Flamefire - Mo 08.02.10 18:56
Das wäre mal was. Ich könnte ein Programm machen, dass z.b. 10000 Spiele spielt, die Spieler sind in einer DLL
Funktionen:
Start(x) //Neues Spiel mit x Karten
GetCard() //wähle Karte
TurnResult(y,state) //Ergebnis des Zuges: Gegnerkarte: y ; state=(win,loss,draw)
Fertig.
Dann kann jeder seine KI gegen jede andere antreten lassen.
Hab dazu gerade mal Lust.
Ergebnis kommt dann ;-)
guinnes - Mo 08.02.10 19:42
| Flamefire hat folgendes geschrieben : |
Das wäre mal was. Ich könnte ein Programm machen, dass z.b. 10000 Spiele spielt, die Spieler sind in einer DLL
Funktionen:
Start(x) //Neues Spiel mit x Karten
GetCard() //wähle Karte
TurnResult(y,state) //Ergebnis des Zuges: Gegnerkarte: y ; state=(win,loss,draw)
Fertig.
Dann kann jeder seine KI gegen jede andere antreten lassen.
Hab dazu gerade mal Lust.
Ergebnis kommt dann ;-) |
Mir würde da noch fehlen, wer anfängt, weil das die Strategie ändern könnte
Flamefire - Mo 08.02.10 20:32
Es gibt keinen, der anfängt. Das ganze läuft ja gleichzeitig.
FinnO - Mo 08.02.10 23:09
Man sieht die Karte des Gegners also nicht. Das macht das ganze ja schon fast spannend. Also eine möglichst genaue DLL-Doku und eine "Server"anwendung ist gefragt.
Flamefire - Mo 08.02.10 23:14
Hab eine Basis-Anwendung mit KI fertig.
Ist lokal (hab keinen Bock auf Server und zum Testen muss man die KIs eh 10000x spielen lassen um Zufälle auszuschließen)
Das ganze gibts
hier [
http://www.delphi-forum.de/viewtopic.php?p=594884]
KI-Doku ist dabei.
Bisher nur Mensch vs KI als Demo.
Rest hab ich heute noch nicht geschafft.
Flamefire - Mi 10.02.10 00:15
So...
Das ganze gibts jetzt auch im Test-Modus. (s. thread)
Also können jetzt verschiedene KIs ausprobiert werden.
Martok - Mi 10.02.10 01:28
Dieses Forum hat ein ganz schön kurzes Gedächtnis.
Das Thema hatten wir schon mal mit den Karten von 1-11, aus der ersten oder zweiten Schlag den Raab. Auch damals waren wir soweit, dass Computer meistens unentschieden spielen, und das erst dann interessant wird, wenn man auf den Gegner reagiert.
Irgendwo hab ich auch noch den Code vom Test-Tool liegen. Plaintext-TCP, konnte man auch per Telnet spielen ;)
Damals wollte aber keiner weiter machen, nachdem das fertig war...
Flamefire - Mi 10.02.10 12:42
Habs grade gefunden.
Nja bei meiner Variante gibts ne Visualisierung und ein schnelles KI-System (damit man auch mal 1Mio Durchläufe testen kann, über Telnet würde das etwas länger dauern)
Außerdem kann die Anzahl der Karten variiert werden.
Frage ist: Kommt jemand dauerhaft gegen eine Random-"KI" an?
In dem thread: Wenn man 2 gleiche KIs gegeneinander antreten lässt, die auch bei der ersten Karte die gleiche Entscheidung fällen, dann legen die immer das gleiche -->Unentschieden.
Also wenn jemand Lust hat: Das Programm ist fertig.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!