Tic-Tac-Latin!

Ini adalah kisah nyata, jadi nama telah diubah.

Guru latin saya, Tn. Latin, menciptakan varian tac toe miliknya sendiri (bukan lelucon). Sebut saja tic-tac-latin. Permainan ini sederhana, pada dasarnya tic toe dimainkan pada empat dengan empat kotak.

Deklarasi aturan formal

Garis adalah baris, kolom atau diagonal. Ada dua simbol, 'X' dan 'O', tetapi satu atau keduanya dapat diganti untuk simbol yang berbeda.
Anda mencetak satu poin ketika Anda memiliki tiga simbol dan satu karakter lainnya.

Skor pengaturan ini:

---HAI
-HAI--
XXXO
XOOX

O -XX
- O -
- X -
--- O

Ini tidak memberi skor:

----
XXXX
----
OOOO

----
XXX-
----
OOO-

Permainan dimenangkan setiap kali satu pemain memiliki lebih banyak poin daripada yang lain. Gim ini hanya seri jika papan diisi.

Tantangan

Selesaikan game ini. Tugas Anda adalah menyediakan cara untuk menjamin kemenangan atau dasi, mana yang merupakan hasil optimal.

Solusi Anda dapat memilih untuk memulai pertama atau kedua (dan karena itu dapat memilih simbolnya). Ini tidak wajib untuk mengimplementasikan permainan interaktif di mana input pengguna bergerak dan tampilan yang sesuai berubah. Ini juga bisa berupa fungsi atau program yang mengambil input sebagai kondisi permainan, dan mengeluarkan papan baru atau deskripsi langkah mereka . Pilihan mana pun harus dijalankan dalam waktu sekitar sepuluh detik per gerakan yang dilakukan.

---

Memainkan pemain Anda melawan setiap urutan gerakan harus memberikan hasil yang optimal. Ini berarti Anda dapat menganggap posisi input adalah posisi yang dapat dijangkau dari bermain dengan pemain Anda. Kiriman harus bersifat deterministik, dan tidak perlu memberikan bukti optimalitas, tetapi jika kiriman tersebut retak (dengan dipukuli) kiriman Anda akan dianggap tidak valid (Anda dapat membiarkannya, tetapi menambahkan (retak) pada informasi utama).

---

Ini adalah tugas yang tidak sepele, jadi setiap pengajuan yang valid sangat mengesankan dan layak untuk centang yang diterima, tapi saya akan menjadikan kode golf kriteria utama yang menang.

Pemenang dipilih dengan turun daftar ini sampai satu pemenang dipilih.

• Implementasi terselesaikan terpendek yang selalu menang
  
• Implementasi terpendek
  

Perl, 147 byte (tidak bersaing, membutuhkan lebih dari 10 detik per gerakan)

Termasuk +4 untuk -0p

Program diputar X. Ini akan memainkan game yang sempurna.

Masukkan papan pada STDIN, misalnya:

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

Ouptut akan menjadi papan yang sama dengan semua Xdigantikan oleh Odan sebaliknya. Bintik-bintik kosong akan diisi dengan angka yang mengindikasikan hasil jika X akan bermain di sana, yang 1artinya hasilnya adalah menang, 2seri, dan 3kalah. Game yang telah selesai hanya mengembalikan posisi yang sama dengan warna yang dibalik.

Dalam contoh ini, hasilnya adalah:

1O1X
1O33
O3O3
X33X

Jadi posisinya adalah kemenangan karena Xdia bermain di 3 tempat di bagian atas dan kiri. Semua gerakan lainnya kalah.

Output membingungkan ini sebenarnya nyaman jika Anda ingin tahu bagaimana permainan berlanjut setelah pindah. Karena program selalu dimainkan, XAnda harus menukar Xdan Omelihat pergerakannya O. Di sini misalnya cukup jelas bahwa Xmenang dengan bermain di kiri atas, tetapi bagaimana jika Xbermain di posisi ketiga sepanjang atas? Cukup salin output, letakkan Odi tempat langkah yang Anda pilih dan ganti semua angka lainnya -lagi, jadi di sini:

-OOX
-O--
O-O-
X--X

Yang menghasilkan:

3XXO
3X33
X3X3
O33O

Tentunya setiap gerakan Oharus kalah, jadi bagaimana dia bisa kalah jika dia bermain di kiri atas? Sekali lagi lakukan ini dengan meletakkan Odi kiri atas dan mengganti digit dengan -:

OXXO
-X--
X-X-
O--O

Memberi:

XOOX
1O33
O3O3
X33X

Jadi X hanya memiliki satu cara untuk meraih kemenangannya:

XOOX
OO--
O-O-
X--X

Memberi

OXXO
XX33
X3X3
O33O

Situasi untuk Otetap tanpa harapan. Sangat mudah untuk melihat sekarang bahwa setiap gerakan memungkinkan Xuntuk segera menang. Mari kita setidaknya mencoba untuk mendapatkan 3 O berturut-turut:

OXXO
XX--
X-X-
O-OO

Memberi:

XOOX
OO13
O3O3
X3XX

Xmemainkan satu-satunya langkah yang menang (perhatikan bahwa ini dilakukan di XXXOsepanjang kolom ketiga:

XOOX
OOO-
O-O-
X-XX

Di sini hasilnya adalah:

OXXO
XXX-
X-X-
O-OO

karena permainannya sudah selesai. Anda dapat melihat kemenangan di kolom ketiga.

Program aktual tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Diterapkan ke papan kosong ini mengevaluasi posisi 9506699 yang memakan waktu 30Gb dan 41 menit di komputer saya. Hasilnya adalah:

2222
2222
2222
2222

Jadi setiap langkah awal menarik. Jadi game ini seri.

Penggunaan memori ekstrim sebagian besar disebabkan oleh penggunaan rekursi do$0. Menggunakan versi 154 byte ini menggunakan fungsi sederhana membutuhkan 3Gb dan 11 menit:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

yang lebih tertahankan (tapi masih terlalu banyak, sesuatu pasti masih bocor memori).

Menggabungkan sejumlah speedup mengarah ke versi 160 byte ini (posisi 5028168, 4 menit dan 800M untuk papan kosong):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

Yang terakhir digunakan 0untuk menang (jangan bingung dengan O), 1untuk seri dan 2untuk kekalahan. Hasil yang satu ini juga lebih membingungkan. Ia mengisi langkah kemenangan untuk X jika menang tanpa swap warna, tetapi jika game input sudah dimenangkan masih melakukan swap warna dan tidak mengisi langkah apa pun.

Semua versi tentu saja menjadi lebih cepat dan menggunakan lebih sedikit memori saat papan terisi. Versi yang lebih cepat akan menghasilkan gerakan dalam waktu kurang dari 10 detik segera setelah 2 atau 3 gerakan dilakukan.

Pada prinsipnya, versi 146 byte ini juga harus berfungsi:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

tetapi pada mesin saya itu memicu bug perl dan dump inti.

Semua versi pada prinsipnya akan tetap berfungsi jika caching posisi 6 byte yang dilakukan $$_||=dihapus tetapi menggunakan begitu banyak waktu dan memori sehingga hanya berfungsi untuk papan yang hampir penuh. Namun secara teori setidaknya saya punya solusi 140 byte.

Jika Anda menempatkan $\=(biaya: 3 byte) tepat sebelum $@<=>0papan output maka masing-masing akan diikuti oleh status seluruh papan: 1untuk Xmenang, 0untuk menarik dan -1untuk kerugian.

Ini adalah driver interaktif berdasarkan versi tercepat yang disebutkan di atas. Pengemudi tidak memiliki logika untuk kapan permainan selesai sehingga Anda harus menghentikan diri sendiri. Kode golf tahu. Jika langkah yang disarankan kembali tanpa -diganti oleh apa pun, permainan telah berakhir.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 byte

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

Pemakaian

"Bot" akan dimainkan kedua.

Gambar kotak 4x4 yang diberi nomor seperti ini:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Mari kita jalankan ini di konsol browser: Taruh f=sebelum kode

Jadi, jika saya ingin mulai 1, saya akan lari f([1])([])dan itu akan memberi saya 14.

Langkah yang bagus ... Bagaimana jika saya bermain 2sesudahnya? f([2,1])([14]). Itu akan kembali 13.

Biar mencoba menyerah. Bermain 3. f([3,2,1])([14,13]). Oh 0! Saya ketahuan!

Bermain 0? f([0,2,1])([14,13]). 15Ok mari kita terus bermain ...

Catatan

1. Mainkan secara interaktif. Mulai dengan f([your-step])([]).

2. Tambahkan langkah Anda selanjutnya. (Lihat demo di atas)

3. Bantu "bot" memasukkan langkah-langkahnya. Itu tidak akan memberi Anda hasil yang baik jika Anda memberikannya pengaturan acak. (Suka f([1,2,4])([14,12])akan memberi 14- Hei bot ingin bermain di 13langkah kedua!

Ringkasan singkat

Selama Anda tidak menyerah, bot akan memainkan gerakan cermin.

Terima kasih @EHTproduk karena memberi tahu saya bahwa saya salah membaca aturan permainan dan kiat bermain golf: P.

Sekarang ini juga akan mendeteksi jika mendapat skakmat. Jika ya, blokir!

Prioritasnya: Block> Mirror> (fallback) mencari cara untuk mereproduksi cermin