Algorithmus zum Spiel "PrimeGame"

scenix

Hallo,

ich versuche gerade ein Spiel in AutoIt zu Implementieren und überleg mir gerade verschiedene Spieler-typen und deren Strategien.

Zum Spiel:

Gegeben ist die Menge der natürlichen Zahlen zwischen 1 und einer beliebigen
Obergrenze. Zwei Spieler wählen abwechselnd eine Zahl aus dieser Menge, so
lange bis keine Zahlen mehr vorhanden sind. Bei jedem Zug erhält der
betreffende Spieler den Zahlenwert der ausgewählten Zahl gut geschrieben, sein
Gegner erhält die Zahlenwerte aller noch vorhandenen Teiler der ausgewählten
Zahl; danach werden die ausgewählte Zahl und alle ihre Teiler entfernt und der
andere Spieler ist am Zug.

Spieler 1: Zieht nur Primzahlen.

Spieler 2: Zieht Primzahlen wenn vorhanden oder kleinste Zahl.

Spieler 3: Zieht Random Zahlen

Spieler 4: Rechnet die besten 10 Züge im Vorraus aus.

Habt ihr eine Idee wie man einen Spieler entwickeln kann der immer gewinnt ?

Es geht mir nur um die Logik nicht um die Implementierung in AutoIt.

Vielen Danke im voraus und bedanke mich für jeden Beitrag

XovoxKingdom

Hi,
ich versuche mich mal grob an einer Lösung:

Spoiler anzeigen

Code

$zahlenMenge = erzeugeZahlenmenge(1,n)
Spieler1 :
wählePrimzahl($i = 0) := {
$zahl := max($zahlenMenge) - $i
wenn $zahl in $zahlenMenge UND $zahl.istPrimzahl()
DANN entferneZahlAusMenge($zahlenMenge,$zahl)) , return $zahl
SONST WENN $i >= anzahl($zahlenMenge) return *ERROR* // an dieser Stelle sind keine Primzahlen mehr möglich und Spieler 1 kann nichts mehr tun
ANSONSTEN return wählePrimzahl($i + 1)
}


Spieler 2:
wählePrimzahl_OderKleinste($i = 0) := {
$zahl := max($zahlenMenge) - $i
wenn $zahl in $zahlenMenge UND $zahl.istPrimzahl()
DANN entferneZahlAusMenge($zahlenMenge,$zahl)) , return $zahl
SONST WENN $i >= anzahl($zahlenMenge) return min($zahlenMenge)
ANSONSTEN return wählePrimzahl_OderKleinste($i + 1)
}


Spieler 3:
wähleZufallszahl := {
$k := maximalerIndex($zahlenMenge)
return $zahlenMenge[random(0, $k)]
}


Spieler 4:
/* Die 'besten' Züge kann man ohne die Züge der anderen zu kennen nicht bestimmen
Es ist ja möglich, dass der Folgezug bereits von einem anderen Spieler getätigt wird.
Weiterhin ist es denkbar den Zug so zu gestalten, dass man selbst nicht optimal, aber der Gegner dafür
umso schlechter wählt (siehe hierzu: Minimaxalgorithmus).
*/

Alles anzeigen

Vielleicht gibt dir der Pseudocode, sofern er überhaupt lesbar und nachvollziehbar ist, ein paar Anregungen

Yjuq

Spoiler anzeigen

Also...
Ich würde meine unbesiegbare KI einfach die größte Zahl aus der Zahlenmenge ziehen lassen welche keinen Teiler besitzt. So würde der Gegner nie Punkte bei einem Zug der KI bekommen. So ist es schon unmöglich zu gewinnen, weil die größten Zahlen einfach von der KI weggeschnappt werden. Und jede andere Zahl die dann der Spieler zieht bekommt dann meine KI.

Ich habe hier auch eine Spielrunde mit den Zahlen 1 bis 20 niedergeschrieben. Der Spieler zieht immer eine zufällige Zahl (habe ich mit Random in AutoIt gemacht) und die KI wie oben beschrieben:

Code

Runde 1:   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Sp: 1   (KI bekommt 0 Punkte) | 1
KI: 19 | 19


Runde 2:   2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20
Sp: 9   (KI bekommt 3 Punkte) | 1 + 9
KI: 17 | 19 + 3 + 17


Runde 3:   2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 20
Sp: 20   (KI bekommt 10 + 5 + 4 + 2 Punkte) | 1 + 9 + 20
KI: 15   (5 ist durch Sp weg) | 19 + 3 + 17 + 10 + 5 + 4 + 2 + 15


Runde 4:   6, 7, 9, 11, 12, 13, 14, 17, 18
Sp: 12   (KI bekommt 6 Punkte) | 1 + 9 + 20 + 12
KI: 18   (6 ist durch SP weg) | 19 + 3 + 17 + 10 + 5 + 4 + 2 + 15 + 6 + 18

Alles anzeigen

Ich glaube ich brauche das hier nicht weiter ausführen. Wie man sieht hat meine KI die meisten Punkte durch den Spieler erhalten und sich die höchst Mögliche Zahl geschnappt, ohne den Gegner auch nur einen Punkt zu überlassen.

Ich möchte meine Idee jetzt nicht mathematisch belegen. Wäre mir zu viel Aufwand das ganze tatsächlich zu berechnen...

€dit:
Mir ist gerade ein noch viel besserer Algorithmus eingefallen. Man berechnet den tatsächlichen Punktetechnischen Vorteil den eine Zahl einbringt. Dafür subtrahiert man alle noch vorhandenen Teiler der Zahlenmenge durch die gewählte Zahl. Das Endergebnis liefert einen tatsächlichen Punktevorsprung. Die Zahl die den größten Punktevorsprung bringt, ist die Zahl welche der Algorithmus wählt.

Nehmen wir einmal an folgende Zahlen wären noch in der Zahlenmenge: 3, 5, 7, 12, 14

Nun wird zuerst der Punktevorsprung für die Zahl 14 gesucht. Der einzige Teiler wäre die Zahl 7. Also ist der Punktevorsprung 14 - 7 Punkte. Hier eine Liste für alle 5 Zahlen:

Code

Zahl 14:   14 - 7 = 7
Zahl 12:   12 - 3 = 9
Zahl 7:     7 - 0 = 7
Zahl 5:     5 - 0 = 5
Zahl 3:     3 - 0 = 3

Die Zahl 12 hat den größten Punktevorsprung. Also ist dies die Zahl welche am meisten Sinn macht zu wählen. Ich hoffe es ist so verständlich.

Ich hoffe ich konnte dir damit weiter helfen! LG. Make

**Andy**

Hi

Zitat

sein
Gegner erhält die Zahlenwerte aller noch vorhandenen Teiler der ausgewählten
Zahl; danach werden die ausgewählte Zahl und alle ihre Teiler entfernt und der
andere Spieler ist am Zug.

wenn ich das richtig verstehe, und Spieler1 eine 12 zieht, dann werden Spieler2 die Zahlen (Teiler) 1,2,3,4,6 also in Summe 16 gutgeschrieben....

**Mars**

Zitat von Andy

Hi

wenn ich das richtig verstehe, und Spieler1 eine 12 zieht, dann werden Spieler2 die Zahlen (Teiler) 1,2,3,4,6 also in Summe 16 gutgeschrieben....

Zitat

Spieler 1: Zieht nur Primzahlen.

Er kann keine 12 ziehen. Allerdings halten sich dann die Teiler in Grenzen

Yjuq

Zitat von "Andy"

[...] wenn ich das richtig verstehe, und Spieler1 eine 12 zieht, dann werden Spieler2 die Zahlen (Teiler) 1,2,3,4,6 also in Summe 16 gutgeschrieben....

Das hast du so richtig verstanden. Allerdings werden nur die Teiler gutgeschrieben, die sich noch in der Zahlenmenge befinden.

Ich war mal so frei und habe eine Simulation des Spieles programmiert. Über den Programmierstil lässt sich sicherlich streiten, aber es funktioniert soweit. Ich habe 4 Algorithmen eingebaut:
Spieler 2: Zieht Primzahlen wenn vorhanden oder kleinste Zahl.
Spieler 3: Zieht Random Zahlen
Mein erster KI Vorschlag
Mein zweiter KI Vorschlag

Spieler 1 habe ich nicht eingebaut, weil es nicht möglich ist immer NUR Primzahlen zu ziehen. Irgendwann sind alle Primzahlen weg. Und bei Spieler 4 wusste ich keinen Ansatz.

Ich habe folgende Funktionsnamen vergeben:
_PlayerOne (Spieler 2)
_PlayerTwo (Spieler 3)
_MyKIOne (erster KI Vorschlag)
_MyKITwo (zweiter KI Vorschlag)

Ich habe die Algo's gegeneinander antreten lassen. Ich habe _PlayerTwo ganz bewusst weggelassen damit kein Zufall den Spielfluss stören kann. Den Algo den ich zuerst immer nenne hat in dem Spiel begonnen. Hier die Ergebnisse bei einem Spiel von 1 bis 20 Zahlen:

Spoiler anzeigen

Code

_PlayerOne vs. _MyKIOne     _MyKIOne vs. _PlayerOne
39 Punkte < > 16 Punkte     20 Punkte < > 35 Punkte


_PlayerOne vs. _MyKITwo     _MyKITwo vs. _PlayerOne
34 Punkte < > 21 Punkte     21 Punkte < > 34 Punkte


 _MyKIOne vs. _MyKITwo       _MyKITwo vs. _MyKIOne
34 Punkte < > 21 Punkte     21 Punkte < > 34 Punkte






_PlayerOne >> 4 Siege
_MyKIOne   >> 2 Siege
_MyKITwo   >> 0 Siege

Alles anzeigen

Das verwundert mich gerade ein wenig... (Kann aber auch sein das ich iwo nen Fehler in den Algo's drin hab ^^)
Aber ich würde mal schätzen wenn man eine Kombination aus den Algo's bauen würde, dann wäre diese noch besser.
Ich selber habe noch keine weitere Idee...

Hier das Skript zum ausprobieren:

Spoiler anzeigen

[autoit]

#include <Array.au3>