Hintergrund

MENACE ( M achine E ducable N oughts A nd C rosses E ngine) ist ein rudimentärer flacher Algorithmus für maschinelles Lernen für das Spiel Noughts and Crosses, der in den 1960er Jahren vom britischen Informatiker Donald Michie entwickelt wurde. Es wurde ursprünglich mit 304 Streichholzschachteln implementiert, die jeweils mit einer Brettposition gekennzeichnet sind und farbige Perlen enthalten (wobei eine von neun Farben mögliche Bewegungen darstellt). Michie berechnete, dass diese 304 Streichholzschachteln für jede Kombination von Zügen auf dem Brett ausreichten.

Je mathematischer unter Ihnen, desto mehr können Sie feststellen, dass es tatsächlich 19.683 mögliche Kombinationen von Nullen, Kreuzen und Leerzeichen auf einer N & C-Tafel gibt. Er berechnete jedoch Möglichkeiten, um diese Zahl zu reduzieren (um den Algorithmus zu beschleunigen und wahrscheinlich Streichholzschachteln zu reduzieren!). Erstens entfernte er alle nicht möglichen Bewegungen, wie zum Beispiel:

-------
|X|0|X|
| |0| |
|X|X| |
-------

(zwei Nullen und vier Kreuze)

Als nächstes kompensierte er Rotationen. Wenn wir zum Beispiel auf der Streichholzschachtel sehen:

-------
| |0|0|
|X| |X|
| |0| |
-------

Wir können die gleiche Box für verwenden

-------
| |X| |
|0| |0|
| |X|0|
-------

Daher repräsentieren die oben genannten farbigen Perlen relative Positionen, nicht absolute. Wenn wir zum Beispiel sagen, dass eine rote Perle oben links bedeutet, schauen wir uns das Bild oben auf der Box an und sehen:

-------
| |0|0|
|X| |X|
| |0| |
-------

Wir würden also wissen, dass in dem Fall, dass dies das Brett ist, die rote Perle bedeuten würde:

-------
|R|0|0|
|X| |X|
| |0| |
-------

Aber wenn dies das Board ist:

-------
| |X| |
|0| |0|
| |X|0|
-------

die rote Perle würde bedeuten

-------
| |X|R|
|0| |0|
| |X|0|
-------

Diese Transformationen galten für Rotationen und Invertierungen (in alle Richtungen, einschließlich Diagonale). Auch hier müssen Sie jede Streichholzschachtel nur einmal auf diese Weise speichern: Erstellen Sie nicht für jede Transformation separate virtuelle Kisten!

Eine weitere Vereinfachung, die Michie vorgenommen hat, bestand darin, sicherzustellen, dass der Computer zuerst funktioniert. Auf diese Weise konnte er alle Bewegungen der ersten Ebene entfernen und etwa ein Fünftel der verbleibenden Kisten entfernen. Schließlich entfernte er alle Spielende-Boxen (da für diese Schritte keine weiteren "Inhalte" oder Züge erforderlich waren).

Nun zum Algorithmus selbst (es ist sehr einfach):

1. Entscheiden Sie zunächst, welche Farben die Perlen darstellen. Sie benötigen 9 Farben, um jedes der Felder auf der Tafel darzustellen.
2. Zu Beginn des Spiels enthält jede der 304 Streichholzschachteln Perlen. Während die Perlen eine zufällige Farbe haben (Duplikate sind also in Ordnung), sollten sie mögliche Bewegungen sein (wenn das Board-Statusbild in der Mitte rechts ein 'O' darstellt, können Sie die Perle, die die Mitte darstellt, nicht verwenden. richtig).
3. Suchen Sie jedes Mal, wenn MENACE (X) an der Reihe ist, die Streichholzschachtel mit der aktuellen Brettposition (oder einer Transformation davon).
4. Öffne die Streichholzschachtel und wähle zufällig eine beliebige Perle aus.
5. Finden Sie heraus, wie der Board-Status geändert wurde, um zum Bild auf der Streichholzschachtel zu gelangen (z. B. um 90 Grad gegen den Uhrzeigersinn gedreht). Wenden Sie dann diese Transformation auf die Perle an (z. B. wird oben links links links).
6. Platziere ein X in diesem Quadrat. Entfernen Sie die ausgewählte Perle aus der Streichholzschachtel. Wenn die Schachtel dadurch leer bleibt, legen Sie drei zufällige (mögliche) Perlen in die Schachtel und wählen Sie eine davon für den Zug aus.
7. Wiederholen Sie 3-6, bis das Spiel beendet ist.
8. Wenn MENACE das Spiel gewonnen hat, gehen Sie alle Streichholzschachteln durch, die MENACE genommen hat. Verfolgen Sie dann, welche Farbperle bei dieser Bewegung verwendet wurde. Legen Sie zwei dieser Perlenfarben in die Schachtel (so dass es die ursprüngliche Perle + eine weitere gibt, wodurch die Wahrscheinlichkeit erhöht wird, dass MENACE diese Bewegung beim nächsten Erreichen dieser Position ausführt).
9. Wenn MENACE das Spiel verloren hat, tun Sie nichts ( ersetzen Sie nicht die herausgenommenen Perlen).
10. Wenn MENACE das Spiel gezeichnet hat, ersetzen Sie die Perle, die es in jedem seiner Züge verwendet hat, aber fügen Sie keine zusätzliche hinzu, damit Sie das behalten, was Sie begonnen haben.

Dies lässt uns einen Algorithmus übrig, der sehr einfach, aber schwer zu implementieren ist. Dies bildet die Grundlage Ihrer Herausforderung.

Wenn Sie immer noch verwirrt sind, lesen Sie http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ - das habe ich gelesen, als ich zum ersten Mal von diesem Algorithmus erfahren habe

Herausforderung

Spielen Sie eine Partie Tic-Tac-Toe mit dem Computer. Geben Sie bei jedem Schritt den Inhalt aller Streichholzschachteln aus.

Eingänge

• Zu Beginn des Programms eine Zahl, die angibt, wie viele Spiele Sie gegen MENACE spielen möchten
• Nach der ersten Runde von MENACE geben Sie Ihren Zug als zweistellige Zeichenfolge ein. Der erste Buchstabe ist "L", "R" oder "M" (links, rechts oder in der Mitte) und bezieht sich auf die Y-Achse. Dann geben Sie einen weiteren Buchstaben ein (wieder "L", "R" oder "M"), diesmal bezogen auf die X-Achse. Wiederholen Sie dies für alle Züge und Spiele.

Ausgänge

• Geben Sie zu Beginn jedes neuen Spiels "neues Spiel" aus.
• Geben Sie das Spielbrett nach jedem Zug des Spielers in einem angemessenen Format aus. Es muss nicht hübsch aussehen (z. B. ist ein Array von Arrays, die die Positionen der Platine darstellen, in Ordnung).
• Nach jedem Zug des Spielers sollte MENACE einen Zug machen. Gib das Board nach dem Umzug von MENACE aus
• Geben Sie nach jedem Spiel den Inhalt aller 304 Streichholzschachteln aus. Perlen können durch einen Buchstaben, einen Namen einer Farbe, ein Zeichen oder eine beliebige Zeichenfolge oder Ganzzahl dargestellt werden (keine Zeiger, anonyme Funktionen usw.).

Regeln

1. Dies ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
2. Ich muss in der Lage sein, Bewegungen einzugeben, nachdem ich die Antwort von MENACE gesehen habe. Nein, "Übergeben Sie alle Ihre Züge in diese Funktion und beobachten Sie, wie das Spiel abläuft".
3. Das Brett muss zwischen den Spielen geräumt werden.
4. Die Streichholzschachteln dürfen zwischen den Spielen nicht gelöscht werden (dies würde das maschinelle Lernen zurücksetzen).
5. Sie müssen 304 Streichholzschachteln haben. Jeder kann diesen Algorithmus mit allen 19.683 Streichholzschachteln implementieren, aber das Lernen ist langsam (da viele Spiele erforderlich sind , um alle mit nützlichen Inhalten zu versehen).
6. Die Ausgabe kann in jedem vernünftigen Format erfolgen, und die Eingabe kann gemäß den PPCG-Standards erfolgen (sofern dies der Regel 2 entspricht). Wenn Sie das Eingabeformat anpassen müssen (wie im Abschnitt ' Eingabe ' beschrieben), ist es in Ordnung, solange es sinnvoll ist.
7. Ein Spiel endet, wenn ein Spieler gewinnt (indem er drei in einer Reihe diagonal, horizontal oder vertikal erhält) oder wenn es ein Unentschieden gibt (das Brett ist voll und es gibt keinen Gewinner).
8. Während MENACE mögliche Bewegungen ausführen muss (und nur mögliche Perlen in jeder Streichholzschachtel haben muss), müssen Sie für die Herausforderung die Eingabe des Benutzers nicht validieren. Wenn sie etwas falsches eingeben, kann Ihr Programm alles tun (völlig verrückt werden, Fehler auslösen usw.) - Sie können davon ausgehen, dass die Eingabe korrekt ist.

R 839 Bytes

options(max.print=1e5)
s=colSums
r=rowSums
m=matrix
a=array
y=apply
S=sum
p=sample
b=m(rep(i<-1:(K=3^9),e=9)%/%(E=3^(8:0))%%3,c(9,K))
V=a(1:9,c(3,3,8))
V[,,2:4]=c(V[x<-3:1,,1],V[,x,1],V[x,x,1])
V[,,5:8]=y(V[,,1:4],3,t)
d=aperm(a(b[c(V),],c(9,8,K)),c(1,3,2))
v=m(V,9)
g=y(m(match(e<-y(d*E,2:3,S),i),,8),1,min)
g[K]=K
G=9-y(t(e==g)*8:1,2,max)
h=s(a(c(b,d[,,5],b[c(1,5,9,3,5,7,1:3),]),c(3,3,K,3))*3^(0:2))
k=r(s(h==13))>0
l=r(s(h==26))>0
o=s(b>0)
M=b
M[M==0]=-1
repeat{A=b[,t<-K]
z=j=c();B=1
repeat{if(S(pmax(-M[,t],0))<1)M[p(9,pmin(3,S(x)),,x<-M[,t]<1),t]=-1
z=c(z,u<-p(9,1,,pmax(-M[,t],0)))
j=c(j,t)
A[v[,G[B]][u]]=1
print(m(A,3))
if(k[B<-S(A*E)]||o[B]==9)break
A[ceiling((utf8ToInt(readline())-76)/5)%*%c(1,3)+1]=2
if(l[B<-S(A*E)])break
t=g[B]}
M[x]=M[x<-cbind(z,j)]-k[B]+l[B]
print(a(M[,g==seq(g)&!k&!l&s(b==1)==s(b==2)&o<8],c(3,3,304)))}

Probieren Sie es online aus!

Eine ziemlich lange Antwort, aber dies war keine einfache Herausforderung. Die TIO-Verbindung hier schlägt fehl, da sie interaktive Eingaben erwartet. Hier ist eine Version , die gegen einen zweiten, zufälligen Spieler spielt, der nur zufällig einen Punkt auswählt. Die Ausgabe für diese zweite Version ist nur der Gewinner (1, 2 oder 0 für ein Unentschieden). Streichholzschachteln werden für alle Brettpositionen initialisiert, aber nur für die 304 gemäß Spezifikation verwendet. Sie werden als Kopien der Tafel mit negativen Zahlen implementiert, um die Anzahl der Perlen an jeder Position anzugeben. Ich habe mit einer Liste von Vektoren gemäß der ursprünglichen Spezifikation experimentiert, aber sie war weniger intuitiv.

Dies ist eine weniger Golfversion mit Kommentaren (aber immer noch kurzen Variablennamen). Beachten Sie, dass die Streichholzschachteln nicht ausgedruckt werden, da sie sehr lang sind. Es kann einen interaktiven Spieler 2, einen zufälligen Spieler 2 oder dieselbe Matchbox-Strategie für Spieler 2 implementieren.

auto = 1 # 1 = Random player 2, 2 = Player 2 uses learning strategy
         # 0 for interactive
print_board <- function(board) {
  cat(apply(matrix(c(".", "X", "O")[board + 1], 3), 1, paste, collapse = ""), "", sep = "\n")
}
E = 3 ^ (8:0) # Number of possible arrangements of board
              # ignoring rotations etc.
# Make all possible boards
b = matrix(rep(1:3 ^ 9, e = 9) %/% E %% 3, c(9, 3 ^ 9))
# Define the eight possible rotation/inversion matrices
V = array(1:9, c(3, 3, 8))
V[, , 2:4] = c(V[x <- 3:1, , 1], V[, x, 1], V[x, x, 1])
V[, , 5:8] = apply(V[, , 1:4], 3, t)
# Create eight copies of the 19683 boards with each transformation
d = aperm(array(b[c(V), ], c(9, 8, 3 ^ 9)), c(1, 3, 2))
v = matrix(V, 9)
# Create reverse transformations (which are the same except for rotation)
w = v[, c(1:5, 7, 6, 8)]
# Find the sums of each transformation using base 3
e = apply(d * E, 2:3, sum)
# Find the lowest possible sum for each board's transformed versions
# This will be the one used for the matchboxes
f = matrix(match(e, 1:3 ^ 9), , 8)
g = apply(f, 1, min)
# Store which transformation was necessary to convert the lowest board
# into this one
G = 9 - apply(t(e == g) * 8:1, 2, max)
# Work out which boards have 3-in-a-row
h = colSums(array(c(b, d[, , 5], b[c(1, 5, 9, 3, 5, 7, 1:3), ]), c(3, 3, 3 ^ 9, 3)) * 3 ^ (0:2))
k = rowSums(colSums(h == 13)) > 0 # player 1 wins
l = rowSums(colSums(h == 26)) > 0 # player 2 wins
# Store how many cells are filled
o = colSums(b > 0)
# Create matchboxes. These contain the actual board configuration, but
# instead of zeroes for blanks have a minus number. This is initially -1,
# but will ultimately represent the number of beads for that spot on the
# board.
M = b
M[M == 0] = -1
repeat {
  # Initialise board and storage of moves and intermediate board positions
  A = b[, t <- 3 ^ 9]
  z = j = c()
  C = 1
  # If we're automating player 2 also, initialise its storage
  if (auto) {
    Z = J = c()
  }
  repeat {
    # If the current board's matchbox is empty, put up to three more beads
    # back in
    if (sum(pmax(-M[, t], 0)) == 0) {
      M[sample(9, pmin(3, sum(x)), , x <- M[, t] == 0), t] = -1
    }
    # Take out a bead from the matchbox
    u = sample(9, 1, , pmax(-M[, t], 0))
    # Mark the bead as taken out
    M[u, t] = M[u, t] + 1
    # Store the bead and board position in the chain for this game
    z = c(z, u)
    j = c(j, t)
    # Mark the spot on the board
    A[v[, C][u]] = 1
    # Print the board
    if (!auto) print_board(matrix(A, 3))
    # Check if  player 1 has won or board is full
    if (k[B <- sum(A * E)] || o[B] == 9) break
    if (auto) {
      # Repeat for player 2 if we're automating its moves
      # Note if auto == 1 then we pick at random
      # If auto == 2 we use the same algorithm as player 1
      D = g[B]
      if (sum(pmax(-M[, D], 0)) == 0) {
        M[sample(9, pmin(3, sum(x)), , x <- M[, D] == 0), D] = -1
      }
      U = sample(9, 1, , if (auto == 1) M[, D] <= 0 else pmax(-M[, D], 0))
      Z = c(Z, U)
      J = c(J, D)
      A[v[, G[B]][U]] = 2
    } else {
      cat(
        "Please enter move (LMR for top/middle/bottom row and\nLMR for left/middle/right column, e.g. MR:"
      )
      repeat {
        # Convert LMR into numbers
        q = ceiling((utf8ToInt(readline()) - 76) / 5)
        if (length(q) != 2)
          stop("Finished")
        if (all(q %in% 0:2) && A[q %*% c(1, 3) + 1] == 0) {
          break
        } else {
          message("Invalid input, please try again")
        }
      }
      A[q %*% c(1, 3) + 1] = 2
    }
    if (l[B <- sum(A * E)])
      break
    # Player 2 has won
    t = g[B]
    C = G[B]
  }
  if (auto) {
    cat(c("D", 1:2)[1 + k[B] + 2 * l[B]])
  } else {
    cat("Outcome:", c("Draw", sprintf("Player %d wins", 1:2))[1 + k[B] + 2 * l[B]], "\n")
  }
  # Add beads back to matchbox
  M[x] = M[x <- cbind(z, j)] - k[B] - 1 + l[B]
  if (auto)
    M[x] = M[x <- cbind(Z, J)] - l[B] - 1 + k[B]
}