Apakah 'Othello' telah terpecahkan?

 (arxiv.org)
3 poin oleh GN⁺ 2023-11-05 | 1 komentar | Bagikan ke WhatsApp
  • Othello/Reversi 8×8 telah dibuktikan secara komputasional berakhir seri ketika kedua pihak bermain sempurna, sehingga menurut standar peneliti telah mencapai status terpecahkan lemah
  • Ruang pencariannya sangat besar, dengan estimasi sekitar 10^58 catatan permainan yang mungkin dan sekitar 10^28 posisi papan, sehingga selama ini tetap menjadi masalah yang jauh lebih sulit daripada checkers yang sebelumnya sudah terpecahkan
  • Hasil kali ini memperoleh nilai teori permainan dari posisi awal beserta strategi untuk mencapainya, namun belum merupakan penyelesaian kuat yang menghitung semua posisi tengah permainan
  • Para peneliti menjelaskan bahwa mereka memanfaatkan pencarian heuristik berbasis perangkat lunak Othello dan alpha-beta search, dan skala pencarian yang diperlukan untuk solusi presisi ternyata lebih kecil daripada perkiraan sebelumnya
  • Data mentah dan program untuk mereproduksi hasil telah dibuka di GitHub, Zenodo, dan figshare, sehingga dapat digunakan sebagai contoh yang dapat diverifikasi untuk riset penyelesaian permainan strategi murni

Penyelesaian komputasional Othello

  • Othello pada papan 8×8 telah terpecahkan secara lemah, dan nilai teori permainan dari posisi awal dihitung sebagai seri
  • Jika kedua pihak bermain optimal tanpa kesalahan, hasilnya akan seri, dan penelitian ini membuktikannya secara komputasional
  • Figure 1 menampilkan salah satu catatan permainan optimal beserta hasil akhirnya
    • Jika pada urutan langkah tersebut terjadi penyimpangan pada titik mana pun, perangkat lunak peneliti sebagai pihak lawan dapat menjamin hasil seri atau kemenangan
  • Hasil ini sejalan dengan prediksi para ahli Othello manusia yang selama ini memperkirakan hasil seri, sehingga para peneliti menilai hasilnya sendiri tidak terlalu mengejutkan

Cakupan penyelesaian dan nilai teori permainan

  • Menyelesaikan permainan informasi sempurna berarti menentukan hasil akhir ketika kedua pihak melakukan permainan sempurna, yaitu nilai teori permainan
  • Permainan yang terpecahkan biasanya dibagi menjadi tiga tingkat
    • Terpecahkan ultra-lemah (ultra-weakly solved): hanya mengetahui nilai teori permainan dari posisi papan awal
    • Terpecahkan lemah (weakly solved): mengetahui nilai teori permainan dari posisi awal dan strategi agar kedua pihak dapat mencapai nilai tersebut dengan sumber daya komputasi yang wajar
    • Terpecahkan kuat (strongly solved): menghitung hasil dari semua kemungkinan posisi yang dapat muncul selama permainan
  • Penelitian ini adalah contoh Othello yang terpecahkan lemah, bukan penyelesaian kuat yang menghitung semua kemungkinan posisi
  • checkers juga disebut sebagai permainan yang terpecahkan lemah dalam pengertian yang sama

Mengapa Othello bertahan lama

  • Othello adalah permainan populer dengan kedalaman strategi tinggi; ditemukan di Inggris pada abad ke-19, lalu dalam bentuknya sekarang menyebar luas di Jepang pada abad ke-20 dan dimainkan di seluruh dunia
  • Kejuaraan dunia telah diadakan setiap tahun sejak 1977, menunjukkan popularitasnya secara global
  • Ruang pencariannya sangat besar
    • Rata-rata sekitar 10 langkah per posisi
    • Rata-rata sekitar 58 langkah untuk satu permainan penuh
    • Sekitar 10^58 catatan permainan yang mungkin
    • Sekitar 10^28 posisi papan yang mungkin
  • Skala ini disebut jauh lebih besar daripada permainan yang sejauh ini berhasil dipecahkan, khususnya checkers
  • Karena ruang pencarian yang besar, Othello tetap menjadi tantangan jangka panjang dalam ilmu komputer

Metode pencarian dan efisiensi komputasi

  • Para peneliti menggunakan alpha-beta search untuk menargetkan penyelesaian lemah
  • Algoritme penyelesaian permainan berbeda tergantung tujuan dan sifat permainannya
    • Untuk penyelesaian lemah, alpha-beta search sering digunakan
    • Untuk penyelesaian kuat, retrograde analysis sering dimanfaatkan
    • Untuk puzzle dengan urutan solusi yang sangat panjang, dikembangkan metode seperti df-pn search
  • alpha-beta search adalah algoritme yang menelusuri graf permainan secara berurutan dengan pendekatan depth-first, sehingga efisiensi pencarian sulit meningkat besar hanya dengan paralelisasi sederhana
  • Berbagai metode telah diteliti untuk pencarian paralel
    • Dalam lingkungan shared memory, YBWC dan Lazy SMP merupakan metode yang populer
    • Dalam lingkungan distributed memory, APHID dan ABDADA disajikan sebagai algoritme terkait
  • Dalam lingkungan distributed memory, kondisi seperti bandwidth dan latensi antar node sangat bervariasi, sehingga pengembang mungkin perlu memilih algoritme yang sesuai dengan lingkungannya atau mengembangkan yang baru
  • Bahkan dengan klaster komputer modern, penyelesaian Othello tetap menjadi hambatan besar, dan terobosan terjadi lewat modifikasi perangkat lunak Othello modern untuk meningkatkan efisiensi pencarian

Permainan lain yang sudah terpecahkan dan potensi pemanfaatannya

  • Sebelum Othello, contoh terbaru dari masalah sulit yang berhasil dipecahkan disebutkan adalah checkers
  • Connect Four, Qubic, Go-Moku, Nine Men’s Morris, dan Awari juga disebut sebagai contoh permainan nontrivial yang telah terpecahkan
  • Tingkat kesulitan penyelesaian permainan umumnya sangat dipengaruhi oleh banyaknya posisi atau situasi di dalam permainan
  • Menyelesaikan permainan bukan hanya mengungkap hasil akhirnya, tetapi juga dapat dimanfaatkan untuk pembuatan puzzle berbasis permainan tersebut
  • Para peneliti menyediakan data mentah dan program untuk reproduksi di GitHub, Zenodo, dan figshare

Bacaan terkait

1 komentar

 
GN⁺ 2023-11-05
Opini Hacker News

  • Meski disebutkan bahwa “dari 2.958.551 posisi, dipilih 2.587 posisi untuk membuat hipotesis tentang hasilnya, dan jika semua hipotesis ini benar maka posisi awal terbukti seri”, tidak ada penjelasan lebih rinci
    Kedengarannya bukan seperti game ini sudah sepenuhnya dipecahkan, melainkan penulis sudah berusaha keras mencari urutan kemenangan tetapi tidak menemukannya

    • Saya hanya membaca sekilas, tetapi tampaknya bagian ini dijelaskan di kalimat berikutnya dan Algorithm 1
      Tertulis bahwa “ada banyak cara memilih subset yang dapat membuktikan posisi awal seri, tetapi kami memperoleh subset kecil dengan Algorithm 1”
      Algorithm 1 dijelaskan sebagai algoritme yang, dengan menerima skor prediksi dari semua posisi dengan 50 kotak kosong, mengembalikan sebuah subset sehingga jika semua posisi dalam subset tersebut terpecahkan dan solusinya cocok dengan prediksi, maka posisi awal juga ikut terpecahkan sebagai konsekuensinya
    • Saya juga bingung di bagian ini. Walau sudah membaca makalahnya dua kali, saya belum yakin memahami metodenya
      Secara umum, penulisan makalahnya kurang intuitif. Penulis bisa saja benar, tetapi rasanya perlu duduk serius dan mengikuti logikanya; kesan pertama saya skeptis
    • Interpretasi yang lebih masuk akal adalah bahwa 2.587 posisi itu mencakup semua kemungkinan
      Bukti seperti ini juga ada di tempat lain. Misalnya teorema empat warna juga direduksi menjadi sejumlah konfigurasi berhingga lalu diwarnai secara manual
    • Tampaknya hasil untuk berbagai posisi dengan 36 kotak kosong dihitung di klaster dan diunggah ke https://figshare.com/articles/dataset/Analyses_of_the_Game_o...
      Skrip di https://github.com/eukaryo/reversi-scripts/blob/main/reversi... bermain sempurna dengan asumsi semuanya benar. Skrip lain di repositori memakai data yang dihitung menggunakan solusi posisi dengan 36 kotak kosong, dan tingkat ini tampaknya masih memungkinkan di mesin biasa
      Pada dasarnya, strukturnya tampak seperti melakukan lookup ke tabel berukuran di bawah 300GB yang berisi semua posisi dengan 37–64 kotak kosong yang dapat dicapai dari weak solution, lalu menyelesaikan posisi dengan 36 kotak kosong atau kurang menggunakan -solve dari edax

  • Othello adalah game yang bagus untuk menunjukkan seberapa kuat heuristik dasar saja bisa menjadi
    Saat permainan berlangsung, ada petak yang sama sekali tidak boleh dimainkan, dan sebaliknya ada petak yang sebaiknya selalu dimainkan jika memungkinkan
    Dengan mengimplementasikan aturan seperti ini saja, ia sudah menjadi lawan yang cukup lumayan, dan menarik melihat betapa cepat orang memberi label “kecerdasan” bahkan pada hal yang sangat sederhana

    • Saya pernah membaca artikel pemrograman Othello dulu sekali, mungkin di BYTE Magazine awal 1980-an
      Katanya mereka mempertemukan aplikasi yang memakai heuristik sederhana serupa dengan aplikasi strategi “membalik sebanyak mungkin” yang sama sederhananya tetapi sangat buruk
      Algoritme heuristik menang telak; kalau tidak salah skornya 60 lawan 4, atau bahkan lebih parah
    • Saya masih ingat program Pascal 200 baris yang berjalan di PDP-11 mengalahkan semua orang di lab
      Saat tersisa 19 kotak kosong, program itu menyelesaikan sisa permainan sepenuhnya, dan itu cukup mencengangkan
    • Saya tidak tahu siapa sebenarnya yang menyematkan “kecerdasan” pada ini
      Othello adalah game yang bahkan ada di perangkat game LCD 10 dolar dengan dua baterai AA

  • Jika Anda tertarik pada game ini, Kejuaraan Dunia Othello yang juga populer di kalangan peneliti ilmu komputer dan kecerdasan buatan sedang berlangsung di Roma, Italia
    Pertandingannya disiarkan langsung di liveothello.com dan YouTube @WorldOthello

    • Apakah makalah ini membuat kejuaraan itu kehilangan makna? Saya juga penasaran apakah ada perangkat lunak berbasis makalah ini yang ikut serta
      Saya penasaran apakah Othello, seperti checkers, adalah game yang sebagian besar pertandingan papan atasnya berakhir seri

  • Keren
    Sekitar 15 tahun lalu saya pernah memecahkan game yang lebih sederhana yang biasa saya mainkan dengan saudara saya. Itu game Afrika dengan sekitar 10 lubang di tiap sisi papan dan batu-batu di dalamnya
    Setelah saya menulis engine alfa-beta, ia menemukan strategi selalu menang yang tidak masuk akal untuk cara kami bermain. Setelah itu saya tiba-tiba menang di setiap permainan, dan saudara saya tidak pernah mau bermain lagi. Duel klasik ilmuwan komputer melawan optometris

    • Keren sekali. Saya pernah memainkan Mancala selama beberapa tahun dan ingin mendengar lebih banyak
      Banyak yang bisa dipelajari dari melihat orang Afrika yang lebih tua bermain Mancala. Mereka bermain sangat cepat, dan rasanya agak seperti poker, di mana tipu daya menjadi bagian dari permainan
      Jika Anda menyebarkan batu cukup cepat, Anda bisa melewati satu mangkuk atau menjatuhkan satu batu ekstra untuk mendapat keuntungan
      Saya tidak selihai itu dan bermain dengan keluarga, jadi saya tidak curang. Tetap saja, itu menjadi permainan yang sangat berbeda. Seperti perbedaan antara para wanita Inggris yang minum teh sambil bermain Mahjong perlahan dan orang-orang yang bermain taruhan uang di rumah judi Tiongkok
    • Jika ingin tahu lebih jauh, lihat https://en.wikipedia.org/wiki/Mancala
    • Saya tidak ingat sumbernya, tetapi saya pernah mendengar bahwa orang hanya menyukai game ketika tingkat kemenangan berada di kisaran 30–70%
      Jika terlalu sering menang atau terlalu sering kalah, mereka tidak lagi menikmati game tersebut
    • Mancala dan Connect Four adalah contoh klasik game yang sudah dipecahkan
      Tapi saya tidak tahu apa relevansi profesi optometris di sini

  • Apakah ini sungguhan? Agak terasa aneh karena penulisnya satu orang dan berafiliasi dengan startup deep learning yang belum pernah saya dengar

    • Alis saya terangkat saat ia menyebut hasilnya sendiri monumental
      Mungkin sedang menjalani peer review?
    • Ini tentu bukan pertama kalinya orang yang tidak terkenal memecahkan masalah besar
      Dan Othello juga tidak persis setara hipotesis Riemann. Penelitiannya tidak sebanyak itu, dan mungkin masih ada buah rendah yang tersisa untuk dipetik

  • Othello adalah salah satu gim yang sangat cocok dimainkan bersama anak kecil
    Aturannya sederhana, ada pola yang bisa dipelajari, dan ada keseruan membalik banyak bidak sekaligus. Yang terpenting, gim ini sama menyenangkannya bukan hanya untuk anak-anak, tetapi juga untuk orang dewasa
    Saya bisa cukup menikmatinya tanpa membuat anak berusia 6 tahun kewalahan, dan tanpa terasa seperti gim yang hanya bergantung pada keberuntungan

    • Dengan alasan serupa, Hus, salah satu keluarga permainan batu Afrika, juga layak dilihat
      https://mancala.fandom.com/wiki/Hus
      Secara teori tidak ada faktor keberuntungan, tetapi dalam praktiknya, karena reaksi berantai, kita tidak bisa menghitung sejauh itu
      Papannya mudah dibuat sendiri
    • Dengan alasan serupa, saya juga suka Blokus

  • Kalau ingin mencoba bermain, saya mengunggah sesuatu yang saya buat bersama anak-anak: https://jawj.github.io/fliptiles
    Pemain “AI”-nya sangat lemah

    • Saya tidak tahu seberapa hebat hasil seri itu, tetapi pada permainan pertama hasilnya 32-32
      Saya belajar gim baru
    • Mengesankan. Waktu kecil saya selalu memainkan gim ini, tetapi sempat lupa bahwa gim ini ada, dan ketika mencobanya lagi ternyata menyenangkan
      Komputer mendapat 33 poin, saya 31 poin

  • Kalau menganggap Othello itu sepele, coba mainkan Zebra
    Situs web penulis asli: http://radagast.se/othello/
    Sumber GitHub: https://github.com/hoshir/zebra

    • Jika tidak tahu apa itu Othello, gim ini juga disebut Reversi

  • Hal yang saya sukai dari Othello adalah kontradiksi antara aksi dan wilayah
    Selama permainan berlangsung, tindakan menaruh langkah pada giliran saya dalam arti tertentu merugikan saya, tetapi tetap harus dilakukan
    Karena itu, sampai tiba saat ruang menjadi terlalu kecil dan kita harus merebut kembali pengaruh yang pasti, kita perlu tetap kecil dan berada di bagian dalam sambil tetap menguasai area

  • Terkait hal ini, ada juga permainan Reversi 6x6 yang dimainkan dengan sempurna
    https://mame.github.io/6x6-reversi-oracle/
    Sumber: https://twitter.com/mametter/status/1476379841004183556
    Saya baru tahu bahwa 8x8 ternyata belum terpecahkan sampai sekarang

    • Saya bahkan tidak bisa merebut satu bidak hitam pun. Apakah ini yang dimaksud “sempurna”?