Algorithmus für Primspiel verbessern

[Plexo]

Hallo,

wir haben in der Uni ein Java-Primspiel, für das man einen eigenen Spieler programmieren kann.

Kurze Erklärung des Spiels:
- Am Anfang hat man Zahlen von 1 bis n.
- Es spielen immer zwei Spieler gegeneinander.
- Es gibt zwei Runden. In der ersten Runde fängt der erste Spieler an, in der zweiten Runde fängt der zweite Spieler an.
- Jeder Spieler zieht eine Zahl. Der Gegenspieler bekommt daraufhin die vorhandenen Teiler. (Bsp: Spieler 1 zieht 6, der Gegenspieler bekommt 2 + 3)
- Man kann eine Zahl nur einmal ziehen. Eine gezogen bzw. erhaltene Zahl fällt aus der Liste.
- Wenn alle Zahlen gezogen wurden, dann ist das Spiel vorbei.
- Alle erhaltenen Zahlen werden summiert.
- Der Spieler mit der höheren Summe gewinnt.

Das sollte als Erklärung reichen. Das Spielprinzip ist eigentlich ziemlich simpel.

Ich hatte jetzt einen Spieler mit folgender Strategie entwickelt.
Ich ziehe immer die Zahl mit der größten Differenz zwischen der Zahl und den vorhandenen Teilern dieser Zahl.

Diese Strategie scheint auch ganz gut zu sein. Allerdings frage ich mich, ob man daran noch etwas verbessern kann. Falls jemand Verbesserungsvorschläge hatte, dann darf er / sie diese gerne posten.

Hier noch ein kleiner Ausschnitt:

Board is set up with numbers up to 200
Player "Joe Public 2" used 4 ms. for the move.
Player "Joe Public 2" made a move and took 199
Player "GreedyPlayer" gets 1
Player "GreedyPlayer" used 1 ms. for the move.
Player "GreedyPlayer" made a move and took 200
Player "Joe Public 2" gets 2, 4, 5, 8, 10, 20, 25, 40, 50, 100
Player "Joe Public 2" used 3 ms. for the move.
Player "Joe Public 2" made a move and took 197
Player "GreedyPlayer" gets nothing.
Player "GreedyPlayer" used 0 ms. for the move.
Player "GreedyPlayer" made a move and took 198
Player "Joe Public 2" gets 3, 6, 9, 11, 18, 22, 33, 66, 99
Player "Joe Public 2" used 3 ms. for the move.
Player "Joe Public 2" made a move and took 193
Player "GreedyPlayer" gets nothing.
Player "GreedyPlayer" used 0 ms. for the move.
Player "GreedyPlayer" made a move and took 196
Player "Joe Public 2" gets 7, 14, 28, 49, 98
Player "Joe Public 2" used 3 ms. for the move.
Player "Joe Public 2" made a move and took 191
Player "GreedyPlayer" gets nothing.
Player "GreedyPlayer" used 1 ms. for the move.
Player "GreedyPlayer" made a move and took 195
Player "Joe Public 2" gets 13, 15, 39, 65

Gruß

 

[~ihja]

Also wenn die Zahlen bis zur 8 gehen und dein Gegenspieler die 5 nimmt würde dein programmierter Spieler falsch handeln: Am besten wäre die 3, da du 3 Punkte bekämst und dein Gegner keine. Dein Bot zieht aber die 8, da die Differenz zur 4 anstatt 3 4 beträgt. So bekämst du zwar 8 Punkte dein Gegner aber 4+2=6, sodass du nur 2 Punkte gewinnen würdest.
Ich hoffe du blickst durch, die Zahlen sind etwas konfus...

Also neben einem vielleicht intelligentem und mathematischen Algorithmus, der mir in diesem Moment leider nicht einfällt, könntest du zumindest für eine bestimmte Größe von Zahlen alle durchprobieren um so die Beste zu finden.

 

[Scutus]

@~ihja die beste Wahl wäre eine 7 - du bekämst 7 und der andere 0...zudem würde Plexo's Algorithmus die 7 wählen...

Wie das Spiel schon heißt, würde ich das Ganze über Primzahlen lösen (ähnlich zu deinem): Ein modifiziertes Sieb des Eratosthenes.

Grundgedanke ist:

erstelle eine Liste von 2...n
für jede zahl i: 2...n führe aus:
   für jede zahl k: 2...n führe aus:
      falls i oder k noch nicht gezogen:
         streiche i*k von der Liste

nun nimm das Maximum von der Liste. Somit müsstest du immer lokal die optimale Entscheidung treffen, was global wohl auch zu einer optimalen Entscheidung führen dürfte (sprich eine Art Greedy-Algorithmus).

Ich kann dir gerade nicht beweisen, dass das stimmt, aber vom Gefühl her müsste es richtig sein.

Grüße,

Scutus

 

[Darkslide]

Die optimale Entscheidung ist fast immer, wie Scutus schon sagte, die größte noch vorhandene Primzahl zu ziehen. Da eine Primzahl keine Teiler hat (1 und sich selbst wird ja ausgeschlossen) bekommt der Gegenspieler 0 Puntke. Das heißt ich bekomme die Punkte, die der Primzahl entsprechen. Die Wahl eine Primzahl ist dann, und nur dann, nicht optimal, wenn die Differenz zwischen Zahl und deren Teiler größer ist, als die größte vorhandene Primzahl.

Die (meiner Meinung nach) beste Strategie:

Suche nach irgendeinem Algorithmus die größte Primzahl im Intervall [1, n].
Für jede Zahl im Intervall [primzahl, n] suche alle Teiler der Zahl und summiere diese auf. Ist die Differenz zwischen Zahl und Teiler > der größten Primzahl, so nehme die Zahl. Erfüllt keine Zahl die obige Bedingungen, so wähle die gefundene, größte Primzahl.

//edit:
Sagen wir die größte gefundene Primzahl in [1, 100000] WÄRE 8437, dann brauchst du nur die Zahlen größer als 8437 testen. Denn egal, ob die Zahl defizient, vollkommen oder abundant ist, so ist die Differenz zwischen Zahl und Teiler sowieso kleiner als die Primzahl. Alle abundanten Zahlen, größer 8437 und kleiner als 10000 sind auch uninteresant, denn dann ist die Summe der Teiler größer als die Zahl selbst.

Interesant sind eigentlich nur die defizienten Zahlen, welche im Intervall [primzahl, n] liegen.

 

[~ihja]

@~ihja die beste Wahl wäre eine 7 - du bekämst 7 und der andere 0...zudem würde Plexo's Algorithmus die 7 wählen...

Stimmt natürlich -.-'
Aber wenn er anfängt und die 7 zieht und der Gegner die 5 würde er fälschlicherweise die 8 anstatt der besseren 3 ziehen.

 

[Scutus]

Ich ziehe immer die Zahl mit der größten Differenz zwischen der Zahl und den vorhandenen Teilern dieser Zahl.

Sprich er erhält bei 8 eine Differenz von 2 und bei 3 eine Differenz von 3 -> er würde die 3 nehmen Sein Algorithmus nimmt schon die optimale lokale Entscheidung...die Frage ist nur, ob man sie wesentlich beschleunigen kann

@darkslide ich arbeite nicht nur mit Primzahlen! Bei meinem Algorithmus wird eine Zahl in der Liste zu einer Pseudo-Primzahl, falls es in der Liste keinen Teiler dafür gibt (1 und die Zahl an sich natürlich ausgeschlossen).

Wenden wir wieder das Bsp. an:

n=8

Spieler zieht die 6 => 1, 2, 3 fallen raus. Dadurch wird auch 4 zu einer "Primzahl", da es keine Zahlen mehr gibt, wodurch du sie darstellen kannst...

Das Ganze ist dann eher als Feintuning zu sehen, weswegen mich mal die Implementierung in Java interessiert - wäre super, wenn du sie hochladen würdest, oder sie mir schicken (also so, dass ich nur noch den Bot programmieren muss)

Grüße

 

[Darkslide]

Oh ich habe in meiner Betrachtung nicht bedacht, dass auch die Teiler der Zahl aus dem Spiel genommen werden.... die Vorgehensweise bleibt aber die gleiche, nur dass man dann die Pseudoprimzahlen einbeziehen muss.