tło

Widmo ( M achine e ducable N oughts ND C Rosses e ngine) jest prymitywny algorytmiczne płytkie maszyna do zera gier i przecięcie, utworzonych przez brytyjskiego komputer naukowca Donald MICHIE w 1960 roku. Pierwotnie został zaimplementowany z 304 pudełkami zapałek, każdy oznaczony pozycją planszy i zawierający kolorowe koraliki (jeden z dziewięciu kolorów, reprezentujący możliwe ruchy). Michie obliczyła, że ​​te 304 pudełka zapałek wystarczały na każdą kombinację ruchów na planszy.

Bardziej matematyczni mogą zdawać sobie sprawę z tego, że na planszy N&C istnieje 19 683 możliwych kombinacji kółko, krzyżyk i puste miejsce; Jednak obliczył sposoby na zmniejszenie tej liczby (aby przyspieszyć algorytm i prawdopodobnie obniżyć pudełka zapałek!). Po pierwsze, usunął wszystkie niemożliwe ruchy, takie jak:

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

(dwa kółko i cztery krzyże)

Następnie skompensował obroty. Na przykład, jeśli na pudełku zapałek widzimy:

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

możemy użyć tego samego pudełka dla

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

Dlatego wyżej wspomniane kolorowe koraliki reprezentują pozycje względne, a nie absolutne. Na przykład, jeśli powiedzieliśmy, że czerwony koralik oznacza lewy górny róg, wtedy spojrzymy na obraz na górze pudełka i zobaczymy:

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

wiedzielibyśmy, że w przypadku, gdy jest to tablica, czerwony koralik oznaczałby:

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

Ale jeśli to jest plansza:

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

znaczyłby czerwony koralik

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

Transformacje te zastosowano do obrotu i odwracania (we wszystkich kierunkach, w tym po przekątnej). Ponownie musisz zapisać każde pudełko zapałek tylko w ten sposób: nie twórz osobnych pudełek wirtualnych dla każdej transformacji!

Kolejnym uproszczeniem dokonanym przez Michie było upewnienie się, że komputer jest pierwszy. W ten sposób mógł usunąć wszystkie ruchy pierwszego poziomu, usuwając około jednej piątej pozostałych skrzynek. W końcu usunął wszystkie pola kończące grę (ponieważ na tych krokach nie była wymagana żadna „zawartość” ani ruchy).

Właśnie, teraz na samym algorytmie (to bardzo proste):

1. Najpierw zdecyduj, co reprezentują kolory koralików. Będziesz potrzebował 9 kolorów, aby przedstawić każde z miejsc na planszy.
2. Na początku gry każde z 304 pudełek zapałek zawiera koraliki. Chociaż koraliki mają losowy kolor (więc duplikaty są w porządku), powinny być możliwe ruchy (więc jeśli obraz stanu planszy przedstawia „O” w środkowym prawym rogu, nie możesz użyć koralika reprezentującego środek- dobrze).
3. Za każdym razem, gdy nadchodzi kolej MENACE (X), znajdź pudełko zapałek z wydrukowaną na nim bieżącą pozycją planszy (lub jej transformacją).
4. Otwórz pudełko zapałek i wybierz dowolny koralik tam losowo.
5. Dowiedz się, w jaki sposób status tablicy został przekształcony, aby dostać się do obrazu na pudełku zapałek (np. Obrócony o 90 stopni w lewo). Następnie zastosuj tę transformację do koralika (np. Lewy górny staje się lewy lewy).
6. Umieść X w tym kwadracie. Usuń wybrany koralik z pudełka zapałek. Jeśli w rezultacie pudełko pozostanie puste, umieść w nim trzy losowe (możliwe) koraliki i wybierz jeden z nich do ruchu.
7. Powtarzaj 3-6, aż gra się zakończy.
8. Jeśli MENACE wygrał grę, przejrzyj wszystkie pudełka zapałek, które zabrał MENACE. Następnie prześledzić, jakiego koloru koralik użył w tym ruchu. Umieść dwa tego koloru koralika w pudełku (tak, aby był oryginalny koralik + jeszcze jeden, zwiększając tym samym prawdopodobieństwo, że MENACE wykona ten ruch następnym razem, gdy osiągnie tę pozycję)
9. Jeśli MENACE przegrał grę, nie rób nic ( nie wymieniaj wyjętych koralików).
10. Jeśli MENACE narysowało grę, wymień koralik użyty w każdym z jego ruchów, ale nie dodawaj dodatkowego, aby pozostało ci to, co zacząłeś.

To pozostawia nam algorytm, który jest bardzo prosty, ale trudny do wdrożenia. To stanowi podstawę twojego wyzwania.

Jeśli nadal jesteś zdezorientowany, zobacz http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ - to właśnie przeczytałem, kiedy po raz pierwszy dowiedziałem się o tym algorytmie

Wyzwanie

Zagraj w kółko i krzyżyk na komputerze. Na każdym kroku wypisz zawartość wszystkich pudełek zapałek.

Wejścia

• Na początku programu liczba podająca liczbę gier, w które chcesz zagrać przeciwko MENACE
• Następnie, po pierwszej turze MENACE, wpisujesz swój ruch jako ciąg dwóch znaków, pierwszą literą jest „L”, „R” lub „M” (lewa, prawa lub środkowa) odnoszące się do osi Y. Następnie wprowadź inną literę (ponownie „L”, „R” lub „M”), tym razem odnoszącą się do osi X. Powtórz dla wszystkich ruchów i gier.

Wyjścia

• Na początku każdej nowej gry wpisz „nowa gra”.
• Po każdym ruchu gracza, wyjmij planszę w dowolnym rozsądnym formacie. Nie musi wyglądać ładnie (np. Tablice przedstawiające pozycje planszy są w porządku).
• Po każdym ruchu gracza, MENACE powinien wykonać ruch. Wyjmij planszę po ruchu MENACE
• Po każdej grze wypisz zawartość wszystkich 304 pudełek zapałek. Koraliki mogą być reprezentowane przez literę, nazwę koloru, znak lub dowolny ciąg lub liczbę całkowitą, którą lubisz (bez wskaźników, anonimowych funkcji itp.).

Zasady

1. To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
2. Muszę być w stanie wprowadzać ruchy po zobaczeniu odpowiedzi MENACE. Nie „przekaż wszystkich ruchów do tej funkcji i zobacz, jak gra się rozgrywa”.
3. Plansza musi być wyczyszczona między grami.
4. Pudełka zapałek nie mogą być czyszczone między grami (spowoduje to zresetowanie uczenia maszynowego)
5. Musisz mieć 304 pudełka zapałek. Każdy może zaimplementować ten algorytm we wszystkich 19683 pudełkach zapałek, ale nauka jest powolna (ponieważ wymaga wielu gier, aby uzyskać wszystkie z przydatnymi treściami).
6. Dane wyjściowe mogą być w dowolnym rozsądnym formacie, a dane wejściowe można pobierać zgodnie ze standardami PPCG (o ile jest to zgodne z regułą 2). Jeśli musisz zmienić format wejściowy (zgodnie z opisem w sekcji „ Wejście ”), to jest OK, o ile ma to sens.
7. Gra kończy się, gdy gracz wygrywa (zdobywając trzy z rzędu po przekątnej, w poziomie lub w pionie) lub gdy jest remis (plansza jest pełna i nie ma zwycięzcy)
8. Podczas gdy MENACE musi wykonywać możliwe ruchy (i mieć tylko możliwe koraliki wewnątrz każdego pudełka zapałek), ze względu na wyzwanie nie musisz sprawdzać poprawności wkładu użytkownika. Jeśli wpiszesz coś złego, twój program może zrobić cokolwiek (całkowicie zwariować, wyrzucić błąd itp.) - możesz założyć, że dane wejściowe są prawidłowe.

R , 839 bajtów

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)))}

Wypróbuj online!

Dość długa odpowiedź, ale nie było to proste wyzwanie. Link TIO tutaj zawiedzie, ponieważ oczekuje interaktywnego wejścia. Oto wersja, która gra przeciwko drugiemu losowemu graczowi, który wybiera losowo miejsce. Wynik dla tej drugiej wersji jest tylko zwycięzcą (1, 2 lub 0 w przypadku remisu). Pudełka zapałek są inicjowane dla wszystkich pozycji na planszy, ale są używane tylko dla 304 zgodnie ze specyfikacją. Są one realizowane jako kopie planszy z liczbami ujemnymi, aby wskazać liczbę perełek na każdej pozycji. Eksperymentowałem z listą wektorów według oryginalnej specyfikacji, ale była mniej intuicyjna.

Jest to wersja mniej golfowa z komentarzami (ale wciąż krótkimi nazwami zmiennych). Pamiętaj, że nie wypisuje pudełka zapałek, ponieważ są one bardzo długie. Może zaimplementować interaktywnego gracza 2, losowego gracza 2 lub tę samą strategię matchbox dla gracza 2.

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]
}