Tantangan ini adalah untuk menulis fungsi minimax dalam bahasa pilihan Anda, untuk menghasilkan langkah terbaik berikutnya dalam permainan NxN dari tic-tac-toe yang diberikan status papan saat ini . Input papan dapat diterima sebagai Matriks, Koleksi 2D atau apa pun yang masuk akal bagi Anda, tetapi mematuhi aturan . Keluaran menjadi langkah terbaik berikutnya untuk siapa pun giliran saat ini , di mana X dianggap telah dimulai .

Latar Belakang Cepat pada Algoritma Minimax

Ide dasar dari algoritma minimax adalah untuk menghitung semua hasil yang mungkin sebagai DAG kemudian membobotnya dengan manfaat bahwa urutan gerakan harus ke pemain, dikunci oleh langkah pertama yang dibuat. Semua hasil yang mungkin kemudian 'tertekuk' oleh langkah pertama, dan diberi skor berdasarkan jumlah semua hasil (-1 untuk kekalahan, 0 untuk dasi dan 1 untuk menang). Dalam implementasi yang membutuhkan banyak pemain untuk bermain, Anda menghitung semua gerakan yang mungkin dilakukan oleh pemain, dan semua respons yang mungkin dilakukan oleh lawan juga. Misalnya, dalam permainan tic-tac-toe (setelah langkah pertama) ada 8 gerakan pertama yang bisa Anda buat, dan semuanya mungkin tampak sama ketika hanya menganalisis belokan berikutnya. Tetapi dengan mengulangi semua hasil yang mungkin untuk setiap rangkaian gerakan yang memungkinkan yang menghasilkan hasil akhir dan merangkum semuanya,

Untuk ringkasan yang lebih baik, lebih mendalam dan kontekstual dari algoritma mini-max dalam hal tic-tac-toe, baca lebih lanjut di sini: http://neverstopbuilding.com/minimax

XKCD (3x3 Solusi Saja)

Aturan

• Bahasa apa pun dapat digunakan, tetapi tidak ada perpustakaan minimax eksternal yang diizinkan.
• Output dapat berupa koordinat (0-n, 0-n) atau angka (1-n * n) yang mengindikasikan langkah terbaik berikutnya.
  • Selain itu, Anda harus dapat mengidentifikasi kapan skenario kasus terbaik adalah kekalahan atau seri alih-alih menang.
  • Cara Anda menyatakan kehilangan atau dasi adalah, sekali lagi, terserah Anda.
• Input harus menggunakan X dan O tradisional, dan Anda harus menganggap X bergerak terlebih dahulu; ruang kosong dapat diwakili oleh apa pun.
• Anda dapat mengasumsikan input apa pun yang masuk ke program Anda memiliki nO dan n + 1 X, dengan kata lain Anda mungkin menganggap Anda mendapatkan papan yang dibentuk dengan baik.
• Keadaan dewan saat ini harus menjadi satu-satunya input untuk program Anda, jika Anda menggunakan rekursi, metode pembantu harus dibuat untuk memfasilitasi persyaratan input. Lihat /codegolf//a/92851/59376 untuk klarifikasi.
• Nilai 10> = n> = 1 harus didukung; jika program Anda "time out" untuk n> 10, saya menemukan ini dapat diterima juga, karena beberapa bahasa memiliki kekuatan pemrosesan yang jauh lebih rendah (Terutama menggunakan konsol yang menghadap web).

Menilai

• Ini adalah kode-golf, sehingga byte-count terendah dari program menang dan celah standar tidak diizinkan secara universal.
• Dalam kasus seri, program yang mendukung 'n' terbesar akan menang.

Contoh Input

2x2

[[X,O]
 [-,-]]

Output: 2 atau [0,1] (3 atau [1,1] juga bisa dibilang benar) (Beberapa bentuk indikasi lokasi, sewenang-wenang selama Anda dapat dengan mudah menjelaskan format yang Anda gunakan)

3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Output: -1 (Kerugian)

Sekali lagi format input apa pun yang Anda inginkan diizinkan, tetapi X dan O harus digunakan, contoh yang diberikan tidak dimaksudkan untuk membatasi format itu, hanya untuk menginspirasi.

Perl, 101 98 byte

Termasuk +4untuk-0p

Jalankan dengan input pada STDIN

tictactoe.pl
OXO
---
--X
^D

Output adalah diagram yang sama, tetapi dengan setiap gerakan diperbarui dengan statusnya, 1mewakili menang, 2mewakili imbang dan 3mewakili kerugian. Untuk kasus ini

OXO
223
21X

jadi 3 gerakan imbang, 1 menang dan 1 kalah (saya akan memperbarui solusi jika format output ini tidak dapat diterima, tetapi kode dasarnya akan tetap sama)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Ini sudah sangat lambat dan menggunakan banyak memori untuk papan kosong 3 * 3 (mengapa sebenarnya, rekursi tidak terlalu dalam. Pasti ada kebocoran memori). Menambahkan biaya memo 6 byte tetapi jauh lebih waras:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Javascript (ES6), 320 294 byte

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Memasukkan

1) Array array karakter yang menggambarkan papan saat ini, seperti:

[['X', '-'], ['-', 'O']]

2) Integer yang menggambarkan giliran saat ini: 1 = X, -1 =O

Keluaran

Array terbuat dari:

• sebuah array yang menggambarkan langkah terbaik dalam [x, y]format
• hasil pertandingan sebagai bilangan bulat: 1 = menang, -1 = kalah, 0 = seri

Contoh

Dalam contoh berikut, Xdijamin menang dengan bermain [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

_{PERMAINAN ANEH. PINDAH SATU-SATUNYA PEMENANG YANG TIDAK BERMAIN.
BAGAIMANA TENTANG GAME OF CHESS BAGUS?}