(Istnieją pewne wyzwania, które wymagają użycia najlepszej strategii, ale tutaj nie. Nawet jeśli jesteś w stanie wygrać, możesz zrobić remis)

Wyzwanie

Napisz program, który gra w kółko i krzyżyk. Nie może przegrać (dlatego powinien zakończyć grę remisem lub wygraną).

Dozwolone metody we / wy

1. Wejściem może być bieżąca płyta. Możesz założyć, że wszystkie poprzednie ruchy drugiego gracza były odtwarzane przez silnik.
2. Dane wejściowe mogą być ruchami pierwszego gracza, a funkcja zapisuje ruchy, które miały miejsce w przeszłości. W takim przypadku funkcja jest wywoływana wiele razy, raz dla każdego ruchu; lub wielokrotne wprowadzanie pytania o funkcję / program.
3. Możesz wziąć dodatkowy wkład, mówiąc, że jesteś pierwszym graczem, lub napisać dwie (ewentualnie powiązane) funkcje, aby rozwiązać problem pierwszego gracza i drugiego gracza. Jeśli Twój program wymaga użycia metody wprowadzania 2 (wielokrotne wywołanie), możesz zdecydować, co zostanie przekazane w pierwszym wywołaniu.
4. Wyjściem może być tablica po twojej turze.
5. Wyjściem może być twój ruch.
6. Ruch może być reprezentowany jako para liczb (może to być indeksowanie 0 lub indeksowanie 1), liczba z zakresu 0 ~ 8 lub liczba z zakresu 1 ~ 9.
7. Tablica może być reprezentowana jako tablica 3 × 3 lub tablica o długości 9. Nawet jeśli język ma tablicę indeksowania 0, można użyć indeksowania 1.
8. Komórki na starcie może używać 3 różne wartości w celu wskazania X, Oi opróżnić.

Kryteria wygranej

Najkrótszy kod w każdym języku wygrywa.

Befunge, 181 168 bajtów

>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

Pozycje na planszy są ponumerowane od 1 do 9. Domyślnie dostajesz pierwszy ruch, ale jeśli chcesz pozwolić komputerowi iść pierwszy, możesz po prostu wpisać 0 dla pierwszego ruchu. Po wykonaniu ruchu komputer odpowie numerem wskazującym ich ruch.

Nie ma czeków, aby upewnić się, że nie wprowadzisz prawidłowego ruchu, a także czeków, aby sprawdzić, czy ktoś wygrał lub przegrał. Gdy nie ma już więcej ruchów do wykonania, program przechodzi w nieskończoną pętlę.

Testowanie tego online jest trochę trudne, ponieważ nie ma tłumaczy internetowych z interaktywnym wejściem. Jeśli jednak wiesz, jakie ruchy wykonasz z wyprzedzeniem (co zakłada, że ​​wiesz, jak zareaguje komputer), możesz w pewien sposób przetestować TIO z tymi zaprogramowanymi ruchami.

Użytkownik gra jako pierwszy: Wypróbuj online!
Komputer gra pierwszy: wypróbuj online!

Aby łatwiej było zobaczyć, co się dzieje, mam również wersję, która wyświetla planszę między ruchami.

Użytkownik gra jako pierwszy: Wypróbuj online!
Komputer gra pierwszy: wypróbuj online!

Pamiętaj, że zanim zobaczysz wyniki, musisz poczekać na przekroczenie limitu czasu TIO.

Wyjaśnienie

Płytka jest przechowywana w obszarze pamięci Befunge jako płaska tablica 9 wartości, indeksowana od 1 do 9. To pozwala nam użyć zerowego przesunięcia jako specjalnego przypadku „bez ruchu”, gdy chcemy pozwolić komputerowi grać jako pierwszy. Ruchy gracza są zapisywane jako 4, a ruchy komputera jako 5. Na początek wszystkie pozycje są inicjowane na 32 (domyślna pamięć Befunge), więc za każdym razem, gdy wchodzimy na planszę, modyfikujemy 8, więc wracamy albo 0, 4 lub 5.

Biorąc pod uwagę ten układ, jeśli zsumujemy wartości dowolnych trzech pozycji na planszy, wiemy, że komputer dzieli jeden ruch od wygranej, jeśli suma wynosi 10, gracz jest o jeden krok od wygranej, jeśli suma wynosi 8, a pozycje są dzielone między komputerem a graczem (ale nadal jedna pozycja jest wolna), jeśli suma wynosi 9.

Nasza cała strategia opiera się na tej koncepcji. Mamy procedurę, która bierze listę potrójnych wskazujących zestawy trzech pozycji na planszy, obliczamy sumę tych pozycji, a jeśli suma jest równa pewnej sumie, komputer przesuwa się na dowolną pozycję w zestawie.

Główna lista testowanych przez nas potrójnych kombinacji to zwycięskie kombinacje (1/2/3, 1/5/9, 1/4/7 itd.). Najpierw szukamy w sumie 10 (komputer wkrótce wygra), a następnie w sumie 8 (gracz ma zamiar wygrać i musimy zablokować ten ruch). Mniej oczywiste jest to, że sprawdzamy łącznie 9 (jeśli gracz i komputer mają po jednej z tych pozycji, dobrym rozwiązaniem jest zajęcie trzeciego przez komputer).

Przed tym ostatnim scenariuszem innym naszym strategicznym ruchem jest sprawdzenie wszystkich zestawów narożnych (1/2/4, 2/3/6 itd.), A także dwóch przeciwstawnych kombinacji narożnych (1/8/9 i 3 / 7/8). Jeśli dowolna z tych kombinacji wynosi 8, tj. Gracz zajął dwie pozycje, dobrą strategią jest zajęcie przez komputer pozostałej wolnej pozycji.

Wreszcie istnieją dwa specjalne ruchy skrzynek. Po pierwsze, zawsze staramy się zająć pozycję środkową przed każdym innym ruchem. Osiąga się to w ten sam sposób, jak w przypadku wszystkich naszych innych ruchów, po prostu przekazując jeden potrójny, 5/5/5 i docelową sumę 0. Dodatkowo, jeśli wszystkie inne testy nie znalazły ruchu, staramy się jeden z górnych rogów w ostateczności. Ponownie osiąga się to po prostu przez przetestowanie potrójnych 1/1/1 i 3/3/3, z docelową sumą 0.

Nie sądzę, że jest to idealna strategia - mogą być gry, które losuje komputer, które potencjalnie mogłyby zostać wygrane - ale jest wystarczająco dobra, aby nigdy nie przegrać meczu. Uruchomiłem skrypt testowy, który próbował odtworzyć każdy możliwy ruch przeciwko komputerowi, i dla każdej prawidłowej sekwencji ruchów komputer wygrał lub narysował grę.

Python 2: 399 401 349 333 317 370 bajtów

2x Bug Bug: kredyt na poziomie 4 m2

-52 znaki: zaliczenie do podziemnej kolejki

-16 znaków: podziękowania dla Jonathana Frecha

-26 znaków: kredyt dla użytkownika202729

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

Wypróbuj online!

Pierwszego dnia kursu algebry liniowej, który odbyłem w ostatnim semestrze, mój bystry absolwent instruktor zaproponował, że jeśli reprezentujesz tablicę kółko i krzyżyk jako matrycę:

4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

zdobycie trzech z rzędu jest równoznaczne z wybraniem trzech liczb z zakresu [1,9], które sumują się do 15. Ta odpowiedź wykorzystuje ten pomysł. Funkcja przyjmuje listę zawierającą dziewięć liczb reprezentujących tablicę. 0 oznacza puste miejsce, 1 jest zajęty przez przeciwnika, a 2 oznacza poprzednią grę wykonaną przez program. Pierwsze 3 linie wyjaśniają, jakie numery wybrał program (p), przeciwnik wybrał (o) i są nadal dostępne (a). Następnie przegląda dostępne liczby i sprawdza, czy któryś z nich, w połączeniu z dwoma wybranymi przez siebie liczbami, dodaje do piętnastu. Jeśli tak, wybierze ten kwadrat i wygra. Jeśli nie ma natychmiastowych zwycięskich ruchów, sprawdzi, czy przeciwnik może wygrać przy użyciu tej samej metody. Jeśli mogą, zajmie ich zwycięski kwadrat. Jeśli nie jest dostępny ruch wygrywający ani blokujący, poruszy się w kącie. Zapobiega to głupcom:

- - - 
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Jeśli żadna z tych sytuacji nie wystąpi, wybierze kwadrat arbitralnie. Funkcja generuje liczbę [0,8] reprezentującą kwadrat indeksowany 0 wybrany przez algorytm.

Edycja: Algorytm priorytetowo traktuje teraz środek nad przekątną, co zapobiegnie kolejnej możliwości głupców wskazanej przez l4m2 i powiązane strategie.

Edycja: Aby wyjaśnić, funkcja przyjmuje tablicę w postaci tablicy i wysyła ruch jako liczbę całkowitą na [0,8]. Ponieważ ta strategia we / wy jest tak niezgrabna, oto skrypt opakowujący, który czyni ją bardziej interaktywną. Wymaga pojedynczego argumentu linii poleceń, który powinien wynosić 1, jeśli gracz idzie pierwszy, i 0, jeśli program idzie pierwszy.

import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2