Mainkan Game Sempurna 4x4 Hex

10

Latar Belakang

Hex adalah gim strategi abstrak dua pemain yang dimainkan pada K×Kbelah ketupat ubin heksagonal. Dua sisi yang berlawanan dari belah ketupat berwarna putih, dan dua lainnya hitam, dan dua pemain, hitam dan putih, secara bergiliran menempatkan token warna mereka pada ubin kosong. Pemain yang pertama kali berhasil membangun jalur antara sisi yang berlawanan dari warna mereka adalah pemenangnya. Diketahui bahwa permainan tidak dapat berakhir imbang, dan bahwa pemain pertama memiliki strategi kemenangan terlepas dari ukuran papan (lihat halaman Wikipedia untuk detailnya).

Tugas

Dalam tantangan ini, kami memperbaiki ukuran papan di K = 4, dan mewakili papan sebagai kisi berikut. Garis tebal menunjukkan ubin yang berdekatan.

Kisi 4x4.

Tugas Anda adalah menghasilkan strategi kemenangan untuk pemain pertama, yang dapat Anda pilih untuk menjadi hitam atau putih. Ini berarti bahwa tindakan legal apa pun yang dilakukan pemain lawan, permainan Anda harus menghasilkan kemenangan. Input Anda adalah posisi permainan (pengaturan token di papan tulis), dan output Anda adalah langkah hukum, dalam format yang ditentukan di bawah ini. Jika Anda ingin menemukan strategi pemenang sendiri, jangan baca spoiler ini:

Garis besar satu strategi kemenangan yang mungkin, dengan anggapan putih menjadi yang utama. Pertama pilih 5. Setelah itu, jika Anda memiliki jalur dari 5 ke baris bawah ATAU hitam memilih 0 atau 1 di titik mana pun, balas dengan memilih mana dari 0 atau 1 yang kosong. Jika hitam memilih 9 atau 13, pilih 10 lalu 14 atau 15 mana yang kosong. Jika hitam tidak memilih 9, 13 atau 14, maka pilih 9 dan selanjutnya 13 atau 14 mana yang kosong. Jika hitam memilih 14, balas dengan memilih 15. Berikutnya, pilih 10 jika kosong; jika hitam memilih 10, jawab dengan 11. Jika hitam lalu pilih 6, jawab dengan 7, dan selanjutnya 2 atau 3 mana yang kosong. Jika hitam tidak memilih 6, pilih itu, sehingga Anda memiliki jalur dari 5 ke baris bawah.

Masukan dan keluaran

Input Anda adalah string 16 karakter WBE, yang berarti putih, hitam dan kosong. Mereka mewakili ubin papan, sebagaimana disebutkan di atas. Anda dapat memilih metode input (yang juga menentukan metode output Anda) dari yang berikut:

  1. Input dari STDIN, output ke STDOUT.
  2. Input sebagai satu argumen baris perintah, output ke STDOUT.
  3. Input sebagai 16 argumen argumen perintah karakter tunggal, output ke STDOUT.
  4. Input sebagai argumen fungsi bernama, output sebagai nilai balik.

Output Anda mewakili ubin tempat Anda meletakkan token berikutnya, karena giliran Anda untuk bergerak. Anda dapat memilih dari format output berikut:

  1. Indeks berbasis nol (seperti yang digunakan dalam gambar di atas).
  2. Indeks berbasis satu.
  3. String input dengan satu Ediganti oleh yang mana Watau BAnda pilih untuk pemain Anda.

Aturan

Strategi Anda harus deterministik. Anda tidak diharuskan untuk menangani posisi permainan dengan benar yang tidak dapat dijangkau dari papan kosong menggunakan strategi Anda, atau posisi yang sudah menang untuk salah satu pemain, dan Anda mungkin menabraknya. Sebaliknya, di papan yang dapat dijangkau menggunakan strategi Anda, Anda harus mengembalikan langkah hukum.

Ini adalah kode-golf, sehingga jumlah byte terendah menang. Celah standar tidak diijinkan.

Pengujian

Saya telah menulis kontroler Python 3 untuk memvalidasi entri, karena akan sangat membosankan untuk dilakukan dengan tangan. Anda dapat menemukannya di sini . Ini mendukung tiga format input pertama dan fungsi Python 3 (fungsi dalam bahasa lain harus dimasukkan ke dalam program), ketiga format output, dan kedua pemain. Jika sebuah strategi tidak menang, itu akan menghasilkan permainan yang hilang itu ditemukan, sehingga Anda dapat mengubah program Anda.

Zgarb
sumber
Tantangan ini mengingatkan saya pada upaya untuk mengompresi AI jari kaki ketika saya sedang menulis program kalkulator. ticalc.org/archives/files/fileinfo/354/35408.html
Sparr
2
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.Saya seharusnya menang sejak lama, atau saya salah?
Sebastian Höffner
@ SebastianHöffner Itu terlihat seperti bug di controller. Saya akan mencoba memperbaikinya ketika saya punya waktu.
Zgarb
@ SebastianHöffner Bugnya sekarang harus diperbaiki.
Zgarb

Jawaban:

6

Marbelous, 973b

Ini adalah implementasi yang naif dari strategi yang diisyaratkan dalam pertanyaan. Itu mengharapkan papan akan diberikan sebagai 16 commandline / parameter mainboard suka hex.mbl B W E E E W E E E B E E E E E Edan itu akan menampilkan posisi nol-diindeks dari langkah selanjutnya putih.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

Saya pikir saya mungkin bisa bermain golf sekitar 200 karakter dari ini dengan percabangan yang lebih baik dan penghapusan penggunaan kembali kode.

Sparr
sumber
Saya menambahkan opsi untuk 16 argumen baris perintah dan memperbarui skrip verifikasi, sehingga solusi ini dapat diuji.
Zgarb
Marbelous +1 (PPCG berpikir menambahkan karakter ini meningkatkan komentar)
Rohan Jhunjhunwala
1

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])
  • Player: BLACK
  • Metode: STDIN / STDOUT, MODIFIED_BOARD

Strateginya adalah pertama mencari Bdi papan tulis. Jika tidak ada yang kembali -1, yang dalam python sama dengan last index. Jadi di papan kosong indeks pertama saya akan index=-1, di situlah saya mulai bergerak.

Jika bidang di sebelah kiri saya ( index-1) gratis, langkah saya berikutnya ada di sana. Jika diambil, saya naik ke kiri. Saya tidak pernah harus naik: jika saya lakukan, saya kehilangan tempo dan akan kehilangan permainan.

Di papan penuh (tidak ada Etempat) saya tidak bergerak.

The printtampaknya sedikit aneh pada awalnya: Saya harus membangun dewan baru (yang saya lakukan melalui mengiris) tapi kemudian saya harus memotong 16 karakter. Ini adalah peninggalan karena saya bekerja dengan indeks negatif dan b[i+1:]dengan demikian akan mengembalikan papan lubang dan sisanya yang saya harapkan, sehingga penting untuk memotong sisanya. Cara lain adalah bekerja dengan indeks positif, misalnya dengan mengambil (b.find('B')+16)%16, tetapi (+16)%16satu byte lebih dari ()[:16].

Tidak Disatukan:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Uji

Saat menjalankan suite tes hex controller, saya menemukan beberapa perilaku aneh:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Saya pikir saya seharusnya menang setelah giliran ke-4 atau menjawab dengan papan yang sama untuk papan penuh harus menjadi jawaban yang benar. Tidak yakin apa yang salah di sana, tidak menyelam jauh lebih dalam - saya hanya ingin memeriksa apakah saya memiliki semua kasus "khusus" yang tertutup. Tapi karena saya tidak harus menutupi situasi di mana seseorang mulai di ruang 4 atau lebih, itu tidak masalah.

85b

Namun, jika saya membiarkan diri saya tidak memeriksa papan penuh (yaitu meninggalkan, 'E' in bsaya selanjutnya dapat menyederhanakan kode untuk hanya menggunakan 85 byte:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Ini akan mengarah pada yang berikut:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Ini mungkin atau mungkin tidak dihitung, dan karena saya menemukan itu bukan langkah yang valid saya memutuskan untuk mencari jawaban yang lebih lama tetapi lebih benar.

Sebastian Höffner
sumber