(Ada beberapa tantangan yang mengharuskan untuk menggunakan strategi terbaik, tetapi di sini kita tidak. Bahkan jika Anda bisa menang, Anda diperbolehkan membuat dasi)

Tantangan

Tulis program yang memainkan permainan tic-tac-toe. Itu tidak boleh kalah (karena itu, itu harus mengakhiri pertandingan baik dengan dasi atau dengan menang).

Metode I / O yang diizinkan

1. Input mungkin papan saat ini. Anda dapat mengasumsikan bahwa semua gerakan sebelumnya dari pemain ke-2 dimainkan oleh mesin Anda.
2. Input mungkin merupakan gerakan pemain pertama, dan fungsi Anda menyimpan gerakan yang terjadi di masa lalu. Dalam hal ini fungsinya disebut beberapa kali, satu kali untuk setiap gerakan; atau input prompt fungsi / program beberapa kali.
3. Anda diizinkan untuk mengambil input tambahan dengan mengatakan jika Anda adalah pemain pertama, atau menulis dua fungsi (mungkin terkait) untuk menyelesaikan masalah pemain pertama dan pemain kedua. Jika program Anda perlu menggunakan metode input 2 (panggilan ganda), Anda dapat memutuskan apa yang diteruskan pada panggilan pertama.
4. Output mungkin papan setelah giliran Anda.
5. Output mungkin menjadi langkah Anda.
6. Suatu gerakan dapat direpresentasikan sebagai sepasang angka (bisa 0-indeks atau 1-indeks), angka dalam rentang 0 ~ 8, atau angka dalam kisaran 1 ~ 9.
7. Papan dapat direpresentasikan sebagai larik 3 × 3, atau larik panjang 9. Bahkan jika bahasa tersebut memiliki larik pengindeksan 0, Anda dapat menggunakan indeks 1.
8. Sel-sel pada grid dapat menggunakan 3 nilai berbeda untuk menunjukkan X, Odan mengosongkan.

Kriteria menang

Kode terpendek di setiap bahasa menang.

Befunge, 181 168 bytes

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

Posisi di papan diberi nomor 1 hingga 9. Secara default Anda mendapatkan langkah pertama, tetapi jika Anda ingin komputer untuk bergerak lebih dulu, Anda bisa memasukkan 0 untuk langkah pertama Anda. Ketika Anda sudah bergerak, komputer akan merespons dengan angka yang menunjukkan langkah mereka.

Tidak ada cek untuk memastikan Anda tidak memasukkan langkah yang valid, dan juga tidak ada cek untuk melihat apakah ada yang menang atau kalah. Setelah tidak ada lagi langkah yang harus dibuat, program hanya akan berjalan tanpa henti.

Agak sulit untuk menguji ini secara online, karena tidak ada penerjemah online dengan input interaktif. Namun, jika Anda tahu gerakan apa yang akan Anda buat di muka (yang mengasumsikan Anda tahu bagaimana komputer akan merespons), Anda dapat menguji di TIO dengan gerakan-gerakan yang diprogram sebelumnya.

Pengguna bermain lebih dulu: Cobalah secara online!
Komputer diputar terlebih dahulu: Cobalah online!

Untuk membuatnya lebih mudah untuk melihat apa yang terjadi, saya juga punya versi yang menampilkan papan antara gerakan.

Pengguna bermain lebih dulu: Cobalah secara online!
Komputer diputar terlebih dahulu: Cobalah online!

Perhatikan bahwa Anda harus menunggu hingga TIO habis sebelum Anda dapat melihat hasilnya.

Penjelasan

Papan disimpan di area memori Befunge sebagai susunan rata dari 9 nilai, diindeks dari 1 hingga 9. Ini memungkinkan kita menggunakan offset nol sebagai case khusus "no move" ketika kita ingin komputer dimainkan terlebih dahulu. Gerakan pemain disimpan sebagai 4, dan komputer bergerak sebagai 5. Untuk memulai dengan semua posisi diinisialisasi ke 32 (memori Befunge default), jadi setiap kali kita mengakses papan kita mod dengan 8, jadi kita akan kembali 0, 4 atau 5.

Mengingat pengaturan itu, jika kita menjumlahkan nilai dari tiga posisi di papan tulis, kita tahu bahwa komputer adalah satu langkah menjauh dari kemenangan jika totalnya 10, pemain satu langkah menjauh dari menang jika totalnya 8, dan posisi dibagi antara komputer dan pemain (tetapi masih satu posisi gratis) jika totalnya 9.

Seluruh strategi kami didasarkan pada konsep ini. Kami memiliki rutin yang mengambil daftar tiga kali lipat yang menunjukkan set tiga posisi di papan tulis, kami menghitung jumlah posisi-posisi itu, dan jika jumlahnya sama dengan total tertentu, komputer bergerak ke posisi mana pun dalam set yang bebas.

Daftar utama tiga kali lipat yang kami uji adalah kombinasi pemenang (1/2/3, 1/5/9, 1/4/7, dll.). Kami pertama-tama mencari total 10 (komputer akan menang), dan kemudian total 8 (pemain akan menang dan kami perlu memblokir gerakan itu). Kurang jelas, kami juga memeriksa total 9 (jika masing-masing pemain dan komputer memiliki salah satu posisi, itu strategi yang baik bagi komputer untuk mengambil yang ketiga).

Sebelum skenario terakhir itu, langkah strategis lain yang kami buat adalah memeriksa semua set sudut (1/2/4, 2/3/6, dll.) Serta dua kombinasi sudut yang berlawanan (1/8/9 dan 3 / 7/8). Jika salah satu dari kombinasi ini berjumlah 8, yaitu pemain telah mengambil dua posisi, itu adalah strategi yang baik bagi komputer untuk mengambil posisi bebas yang tersisa.

Akhirnya, ada dua gerakan kasus khusus. Pertama, kami selalu mencoba dan mengambil posisi tengah sebelum ada gerakan lain. Ini dicapai dengan rutin yang sama dengan semua gerakan kami yang lain, hanya melewati triple triple, 5/5/5, dan jumlah target 0. Selain itu, jika semua tes lain gagal menemukan langkah, kami mencoba untuk mengambil salah satu sudut atas sebagai pilihan terakhir. Sekali lagi ini hanya dicapai dengan menguji tiga kali lipat 1/1/1 dan 3/3/3, dengan jumlah target 0.

Saya tidak berpikir ini adalah strategi yang sempurna - mungkin ada game yang diundi oleh komputer yang berpotensi dimenangkan - tetapi cukup bagus untuk tidak pernah kalah dalam pertandingan. Saya telah menjalankan skrip uji yang mencoba memainkan setiap gerakan yang mungkin terhadap komputer, dan untuk setiap urutan gerakan yang valid, komputer dapat memenangkan atau menggambar permainan.

Python 2: 399 401 349 333 317 370 byte

2x Perbaikan Bug: kredit ke l4m2

-52 karakter: kredit ke bawah tanahmonail

-16 karakter: kredit untuk Jonathan Frech

-26 karakter: kredit ke pengguna202729

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

Cobalah secara Online!

Pada hari pertama kursus aljabar linear yang saya ambil semester lalu, instruktur mahasiswa pascasarjana yang cerdik mengusulkan bahwa jika Anda mewakili papan tic-tac-toe sebagai matriks:

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

kemudian mendapatkan tiga berturut-turut sama dengan memilih tiga angka dalam rentang [1,9] yang menambahkan hingga 15. Jawaban ini mengeksploitasi ide ini. Fungsi mengambil daftar yang berisi sembilan angka yang mewakili papan. 0 menunjukkan ruang kosong, 1 ditempati oleh lawan, dan 2 mewakili permainan sebelumnya yang dibuat oleh program. 3 baris pertama mencari tahu nomor apa yang telah diambil program (p), oposisi telah memilih (o), dan masih tersedia (a). Kemudian melihat melalui nomor yang tersedia dan melihat apakah ada dari mereka, dikombinasikan dengan dua angka yang sudah dipetiknya menambah lima belas. Jika ya, itu akan memilih kotak itu dan menang. Jika tidak ada gerakan kemenangan langsung, itu akan memeriksa untuk melihat apakah lawan dapat menang menggunakan metode yang sama. Jika mereka bisa, itu akan membawa kemenangan mereka. Jika tidak ada langkah kemenangan atau pemblokiran yang tersedia, itu akan bergerak di sudut. Ini mencegah pasangan bodoh:

- - - 
- X -
- - -

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

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Jika tidak ada satu pun dari situasi ini yang terjadi, ia akan memilih kotak secara sewenang-wenang. Fungsi ini menghasilkan angka [0,8] yang mewakili 0 diindeks kuadrat yang dipilih oleh algoritma.

Sunting: Algoritme sekarang memprioritaskan pusat di atas diagonal, yang akan mencegah kemungkinan pasangan bodoh lain yang ditunjukkan oleh l4m2 dan strategi terkait.

Sunting: Untuk memperjelas, fungsi mengambil papan dalam bentuk array dan output bergerak sebagai integer pada [0,8]. Karena strategi I / O ini begitu kikuk, inilah skrip wrapper yang membuatnya lebih interaktif. Dibutuhkan argumen baris perintah tunggal, yang harus menjadi 1 jika pemain pergi dulu, dan 0 jika program berjalan pertama.

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