Last active
April 24, 2024 16:51
-
-
Save denkspuren/0abca660e8c483e8b022dad6bdc54109 to your computer and use it in GitHub Desktop.
Implementation of Nim in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Den Code bespreche ich ausführlich im Podcast "Herzbergs Hörsaal" in der Episode | |
// https://anchor.fm/dominikusherzberg/episodes/PiS-Das-Nim-Spiel-in-Java-programmiert-edks2t | |
// | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Random; | |
import java.util.stream.IntStream; | |
class Move { | |
final int row, number; | |
static Move of(int row, int number) { | |
return new Move(row, number); | |
} | |
private Move(int row, int number) { | |
if (row < 0 || number < 1) throw new IllegalArgumentException(); | |
this.row = row; | |
this.number = number; | |
} | |
public String toString() { | |
return "(" + row + ", " + number + ")"; | |
} | |
} | |
interface NimGame { | |
static boolean isWinning(int... numbers) { | |
return Arrays.stream(numbers).reduce(0, (i,j) -> i ^ j) != 0; | |
// klassische Variante: | |
// int res = 0; | |
// for(int number : numbers) res ^= number; | |
// return res != 0; | |
} | |
NimGame play(Move... moves); | |
Move randomMove(); | |
Move bestMove(); | |
boolean isGameOver(); | |
String toString(); | |
} | |
class Nim implements NimGame { | |
private Random r = new Random(); | |
int[] rows; | |
public static Nim of(int... rows) { | |
return new Nim(rows); | |
} | |
private Nim(int... rows) { | |
assert rows.length >= 1; | |
assert Arrays.stream(rows).allMatch(n -> n >= 0); | |
this.rows = Arrays.copyOf(rows, rows.length); | |
} | |
private Nim play(Move m) { | |
assert !isGameOver(); | |
assert m.row < rows.length && m.number <= rows[m.row]; | |
Nim nim = Nim.of(rows); | |
nim.rows[m.row] -= m.number; | |
return nim; | |
} | |
public Nim play(Move... moves) { | |
Nim nim = this; | |
for(Move m : moves) nim = nim.play(m); | |
return nim; | |
} | |
public Move randomMove() { | |
assert !isGameOver(); | |
int row; | |
do { | |
row = r.nextInt(rows.length); | |
} while (rows[row] == 0); | |
int number = r.nextInt(rows[row]) + 1; | |
return Move.of(row, number); | |
} | |
public Move bestMove() { | |
assert !isGameOver(); | |
if (!NimGame.isWinning(rows)) return randomMove(); | |
Move m; | |
do { | |
m = randomMove(); | |
} while(NimGame.isWinning(play(m).rows)); | |
return m; | |
} | |
public boolean isGameOver() { | |
return Arrays.stream(rows).allMatch(n -> n == 0); | |
} | |
public String toString() { | |
String s = ""; | |
for(int n : rows) s += "\n" + "I ".repeat(n); | |
return s; | |
} | |
} | |
Nim nim = Nim.of(2,3,4); | |
assert nim != nim.play(Move.of(1,2)) : "Return a new Nim instance"; | |
int[] randomSetup(int... maxN) { | |
Random r = new Random(); | |
int[] rows = new int[maxN.length]; | |
for(int i = 0; i < maxN.length; i++) { | |
rows[i] = r.nextInt(maxN[i]) + 1; | |
} | |
return rows; | |
} | |
ArrayList<Move> autoplay(NimGame nim) { | |
ArrayList<Move> moves = new ArrayList<>(); | |
while (!nim.isGameOver()) { | |
Move m = nim.bestMove(); | |
moves.add(m); | |
nim = nim.play(m); | |
} | |
return moves; | |
} | |
boolean simulateGame(int... maxN) { | |
Nim nim = Nim.of(randomSetup(maxN)); | |
// System.out.println(nim); | |
// System.out.println((NimGame.isWinning(nim.rows) ? "first" : "second") + " to win"); | |
ArrayList<Move> moves = autoplay(nim); | |
// System.out.println(moves); | |
return (NimGame.isWinning(nim.rows) && (moves.size() % 2) == 1) || | |
(!NimGame.isWinning(nim.rows) && (moves.size() % 2) == 0); | |
} | |
assert IntStream.range(0,100).allMatch(i -> simulateGame(3,4,5)); | |
assert IntStream.range(0,100).allMatch(i -> simulateGame(3,4,6,8)); | |
/* // Beispielhaftes Spiel über JShell | |
jshell> Nim n = Nim.of(2,3,4) | |
n ==> | |
I I | |
I I I | |
I I I I | |
jshell> n = n.play(n.bestMove()) | |
n ==> | |
I I | |
I I I | |
I | |
jshell> n = n.play(Move.of(2,1)) | |
n ==> | |
I I | |
I I I | |
jshell> n = n.play(n.bestMove()) | |
n ==> | |
I I | |
I I | |
jshell> n = n.play(Move.of(1,1)) | |
n ==> | |
I I | |
I | |
jshell> n = n.play(n.bestMove()) | |
n ==> | |
I | |
I | |
jshell> n = n.play(Move.of(1,1)) | |
n ==> | |
I | |
jshell> n = n.play(n.bestMove()) | |
n ==> | |
jshell> n.isGameOver() | |
$25 ==> true | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
In der Methode
public Nim play(Move... moves)
hat es einen Fehler gegeben. So sah der Code aus, es wird nur der letzte der übergebenen Züge ausgeführt:Im Rumpf der
for
-Schleife muss es heißen:nim = nim.play(m)
, damit immer auf der zurückgegebenen Instanz der nächste Zug ausgeführt wird. Vielen Dank für den Fehlerhinweis und den Fix an Marc Thürmer (3. Apr. 2022)