'Othello' çözüldü mü?

 (arxiv.org)
3 puan yazan GN⁺ 2023-11-05 | 1 yorum | WhatsApp'ta paylaş
  • 8×8 Othello/Reversi için, iki taraf da kusursuz oynadığında nihai sonucun beraberlik olduğu hesaplamalı olarak kanıtlandı; bu da araştırmacılara göre oyunun zayıf çözüm düzeyine ulaştığını gösteriyor
  • Olası oyun kayıtlarının yaklaşık 10^58, tahta konumlarının ise yaklaşık 10^28 olduğu tahmin edildiğinden, arama uzayı çok büyük ve bu nedenle oyun, daha önce çözülmüş olan checkers'tan çok daha zor bir problem olarak kalmıştı
  • Bu sonuç, başlangıç konumunun oyun kuramsal değerini ve bu değere ulaştıran stratejiyi ortaya koyuyor; oyundaki tüm ara konumları hesaplayan güçlü çözüm değil
  • Araştırmacılar, Othello yazılımı tabanlı sezgisel arama ile alpha-beta search kullandıklarını ve kesin çözüme ulaşmak için gereken arama ölçeğinin önceki tahminlerden daha küçük olduğunu belirtiyor
  • Sonucun yeniden üretilebilmesi için ham veriler ve programlar GitHub, Zenodo ve figshare'de yayımlandı; böylece saf strateji oyunlarını çözme araştırmaları için doğrulanabilir bir örnek olarak kullanılabilir

Othello'nun hesaplamalı çözümü

  • 8×8 tahtadaki Othello zayıf biçimde çözüldü ve başlangıç konumunun oyun kuramsal değeri beraberlik olarak hesaplandı
  • Her iki taraf da hata yapmadan en iyi oyunu oynarsa sonuç beraberlik oluyor ve bu çalışma bunu hesaplamalı olarak kanıtlıyor
  • Figure 1'de en iyi oyun kayıtlarından biri ve nihai sonuç sunuluyor
    • Bu varyantta herhangi bir anda sapma olursa, araştırmacıların yazılımı rakip taraf olarak beraberliği veya galibiyeti garanti ediyor
  • Bu sonuç, insan Othello uzmanlarının uzun süredir öngördüğü beraberlikle uyumlu; araştırmacılar bu yüzden sonucun kendisini şaşırtıcı bulmuyor

Çözümün kapsamı ve oyun kuramsal değer

  • Tam bilgili bir oyunu çözmek, iki tarafın da kusursuz oyun sergilemesi durumundaki nihai sonucu, yani oyun kuramsal değeri belirlemek anlamına gelir
  • Çözülmüş oyunlar genelde üç düzeyde sınıflandırılır
    • Ultra-zayıf çözüm (ultra-weakly solved): Yalnızca başlangıç tahtası konumunun oyun kuramsal değerinin bilinmesi
    • Zayıf çözüm (weakly solved): Başlangıç konumunun oyun kuramsal değeriyle birlikte, makul hesaplama kaynakları içinde iki tarafın da bu değere ulaşmasını sağlayan stratejilerin bilinmesi
    • Güçlü çözüm (strongly solved): Oyun sırasında ortaya çıkabilecek tüm olası konumların sonucunun hesaplanması
  • Bu çalışma, Othello'nun zayıf çözüldüğü bir örnek; tüm olası pozisyonları hesaplayan güçlü çözüm değil
  • checkers da aynı anlamda zayıf çözülmüş bir oyun olarak veriliyor

Othello'nun neden bu kadar uzun süre çözümsüz kaldığı

  • Othello, stratejik derinliği yüksek popüler bir oyun; 19. yüzyılda İngiltere'de icat edildi, 20. yüzyılda bugünkü biçimi Japonya'da yaygınlaştı ve dünya genelinde oynanıyor
  • Dünya şampiyonası 1977'den beri her yıl düzenleniyor; bu da küresel popülerliğini gösteriyor
  • Arama uzayı son derece büyük
    • Bir konum başına ortalama yaklaşık 10 hamle
    • Bir oyunun tamamında ortalama yaklaşık 58 hamle
    • Olası oyun kayıtları yaklaşık 10^58
    • Olası tahta konumları yaklaşık 10^28
  • Bu ölçek, şimdiye kadar çözülmüş zor oyunların, özellikle de checkersın, çok üzerindeydi
  • Bu devasa arama uzayı nedeniyle Othello, bilgisayar biliminin uzun soluklu problemlerinden biri olarak kaldı

Arama yöntemi ve hesaplama verimliliği

  • Araştırmacılar zayıf çözümü hedefleyerek alpha-beta search kullandı
  • Oyun çözme algoritmaları, hedefe ve oyunun doğasına göre değişir
    • Zayıf çözüm için alpha-beta search sık kullanılır
    • Güçlü çözüm için retrograde analysis sıkça tercih edilir
    • Çok uzun çözüm dizilerine sahip bulmacalar için df-pn search gibi yöntemler geliştirilmiştir
  • alpha-beta search, oyun grafiğini derinlik öncelikli biçimde sıralı olarak tarayan bir algoritma olduğundan, yalnızca basit paralelleştirmeyle arama verimliliğini büyük ölçüde artırmak zordur
  • Paralel arama için çeşitli yöntemler araştırılmıştır
    • Paylaşımlı bellek ortamlarında YBWC ve Lazy SMP popüler yöntemlerdir
    • Dağıtık bellek ortamlarında APHID ve ABDADA ilgili algoritmalar arasında gösterilir
  • Dağıtık bellek ortamlarında düğümler arası bant genişliği ve gecikme gibi koşullar büyük farklılık gösterdiğinden, geliştiriciler ortama uygun algoritmayı seçmek veya yenisini geliştirmek zorunda kalabilir
  • Modern bilgisayar kümeleri kullanılsa bile Othello'yu çözmek büyük bir engeldi; ancak güncel Othello yazılımının değiştirilerek arama verimliliğinin artırılması bir dönüm noktası oldu

Çözülmüş diğer oyunlar ve olası kullanım alanları

  • Othello'dan önce çözülmüş zor oyunların en güncel örneği olarak checkers veriliyor
  • Connect Four, Qubic, Go-Moku, Nine Men’s Morris ve Awari gibi trivial olmayan oyunlar da çözülmüş örnekler arasında sıralanıyor
  • Bir oyunu çözmenin zorluğu büyük ölçüde oyun içindeki konum veya durum sayısına bağlıdır
  • Bir oyunu çözmek, yalnızca nihai sonucu ortaya koymakla kalmaz; o oyun temelinde bulmaca üretimi için de kullanılabilir
  • Araştırmacılar, yeniden üretim için ham verileri ve programları GitHub, Zenodo ve figshare üzerinden sağlıyor

İlgili okumalar

1 yorum

 
GN⁺ 2023-11-05
Hacker News görüşleri

  • “2.958.551 konum arasından 2.587 konum seçip sonuç hakkında bir hipotez kurduk; bu hipotezlerin hepsi doğruysa başlangıç konumunun beraberlik olduğunu kanıtlamış oluruz” deniyor ama daha ayrıntılı bir açıklama yok
    Bu, oyunun tamamen çözüldüğünden çok, yazarın kazanma varyantlarını epey uğraşıp aradığı ama bulamadığı izlenimini veriyor

    • Hızlıca göz attım ama hemen sonraki cümle ile Algorithm 1 bu kısmı açıklıyor gibi görünüyor
      “Başlangıç konumunun beraberlik olduğunu kanıtlayabilecek bir altküme seçmenin birçok yolu var, ama biz Algorithm 1 ile küçük bir altküme elde ettik” deniyor
      Algorithm 1’in, “50 boş kareli tüm konumların tahmin skorlarını alıp, bu altkümedeki tüm konumlar çözülür ve çözümler tahminlerle uyuşursa başlangıç konumunun da sonuç olarak çözülmesini sağlayan” bir altküme döndürdüğü açıklanıyor
    • Ben de bu noktada kafam karıştı. Makaleyi iki kez okudum ama yöntemi gerçekten anlayıp anlamadığımdan hâlâ emin değilim
      Genel olarak makalenin anlatımı sezgisel değil. Yazar haklı olabilir ama mantığı gerçekten oturup adım adım takip etmek gerekiyor gibi; ilk izlenimim şüpheci yönde
    • Daha makul yorum, o 2.587 konumun tüm olasılıkları kapsadığı yönünde
      Bu tür kanıtlar başka yerlerde de var. Örneğin Dört Renk Teoremi de sonlu sayıda konfigürasyona indirgenip sonra elle renklendirilmişti
    • Görünüşe göre çeşitli 36 boş kareli konumların sonuçları kümede hesaplanıp https://figshare.com/articles/dataset/Analyses_of_the_Game_o... adresine yüklenmiş
      https://github.com/eukaryo/reversi-scripts/blob/main/reversi... içindeki betik, her şeyin doğru olduğu varsayımıyla kusursuz oynuyor. Depodaki diğer betikler, 36 boş kareli konum çözümleriyle hesaplanan verileri kullanıyor; bu kadarı sıradan bir makinede de yapılabilir gibi görünüyor
      Özünde yapı, zayıf çözümden erişilebilen 37 ile 64 boş kareli tüm konumları içeren 300 GB’ın altındaki bir tabloya bakıyor; 36 veya daha az boş kareli konumları ise edax -solve ile çözüyor gibi

  • Othello, temel heuristic kurallarla bile ne kadar güçlü olunabileceğini göstermeye çok uygun bir oyun
    Oyun ilerlerken asla oynanmaması gereken kareler var; tersine mümkünse mutlaka oynanması gereken kareler de var
    Sadece bu kuralları uygulasanız bile epey iyi bir rakip çıkıyor ortaya ve insanların çok basit şeylere bile ne kadar hızlı “zeka” atfettiğini görmek ilginç

    • Çok uzun zaman önce Othello programlama üzerine bir yazı okumuştum; sanırım 1980’lerin başında BYTE Magazine’deydi
      Benzer basit heuristics kullanan bir uygulamayı, yine aynı derecede basit ama korkunç derecede kötü olan “en çok taşı çevir” stratejili bir uygulamayla karşılaştırmışlardı
      Heuristic algoritma ezici biçimde kazanmıştı; 60’a 4 ya da daha da kötü bir skor olduğunu hatırlıyorum
    • PDP-11 üzerinde çalışan 200 satırlık bir Pascal programının laboratuvardaki herkesi yendiğini hâlâ hatırlıyorum
      19 boş kare kaldığında oyunun geri kalanını tamamen çözüyordu ve bu oldukça etkileyiciydi
    • Burada gerçekten kimin buna “zeka” atfettiğini bilmiyorum
      Othello, iki AA pille çalışan 10 dolarlık LCD el oyunlarında bile bulunan bir oyundu

  • Oyunla ilgileniyorsanız, bilgisayar bilimi ve yapay zeka araştırmacıları arasında da popüler olan Othello Dünya Şampiyonası şu anda İtalya'nın Roma kentinde sürüyor
    Maçlar liveothello.com ve Youtube @WorldOthello üzerinden canlı yayınlanıyor

    • Bu makale şampiyonayı anlamsız mı kılıyor? Ayrıca makaledeki yazılıma dayanan bir programın turnuvaya katılıp katılmadığını merak ediyorum
      Othello'nun da dama gibi üst düzey maçların çoğunun beraberlikle bittiği bir oyun olup olmadığını merak ediyorum

  • Harika
    Yaklaşık 15 yıl önce kardeşimle oynadığım daha basit bir oyunu çözmüştüm. Tahtanın iki yanında yaklaşık 10’ar çukur bulunan ve içine taş konan bir Afrika oyunuydu
    Bir alfa-beta motoru yazdım ve bizim oynama biçimimize göre saçma derecede her zaman kazandıran bir strateji keşfetti. Ondan sonra birden bütün oyunları kazanmaya başladım ve kardeşim bir daha benimle oynamak istemedi. Bilgisayar bilimciye karşı optometristin tipik mücadelesiydi

    • Gerçekten harika. Birkaç yıldır Mancala oynuyorum ve daha fazlasını duymak isterim
      Yaşlı Afrikalıların Mancala oynayışını izlerseniz öğrenecek çok şey var. İnanılmaz hızlı oynuyorlar ve hilenin oyunun bir parçası hâline geldiği bir poker hissi de var
      Taşları yeterince hızlı dağıtırsanız bir kabı atlayabilir ya da bir taşı fazladan bırakıp avantaj elde edebilirsiniz
      Ben o kadar becerikli değilim ve ailemle oynadığım için hile yapmıyorum. Yine de çok farklı bir oyuna dönüşüyor. İngiliz hanımefendilerinin çay içerken yavaş yavaş Mahjong oynamasıyla, Çin'de kumarhanelerde para üzerine oynanması arasındaki fark gibi
    • Daha fazlasını öğrenmek isterseniz https://en.wikipedia.org/wiki/Mancala sayfasına bakabilirsiniz
    • Kaynağı hatırlamıyorum ama insanların yalnızca kazanma oranları %30 ile %70 arasındayken oyunu sevdiklerini duymuştum
      Çok fazla kazanır ya da çok fazla kaybederseniz oyundan keyif almamaya başlarsınız
    • Mancala ve Connect Four, çözülmüş oyunların klasik örnekleri
      Ama optometrist olmanın burada neyle ilgili olduğunu bilmiyorum

  • Bu gerçek mi? Yazarın tek kişi olması ve daha önce adını duymadığım bir derin öğrenme girişiminde çalışması bana biraz tuhaf geldi

    • Sonuçlarını bizzat monumental diye nitelemesi bende soru işareti yarattı
      Herhâlde şu anda hakem değerlendirmesindedir, değil mi?
    • Tanınmayan birinin büyük bir problemi çözmesi ilk kez olmuyor
      Ayrıca Othello tam olarak Riemann hipotezi düzeyinde bir şey değil. O kadar çalışılmış bir alan değildi ve belki de hâlâ erişilebilir kolay problemler kalmıştı

  • Othello, çocuklarla birlikte oynamak için gerçekten en iyi oyunlardan biri.
    Kuralları basit, öğrenilecek kalıplar var ve bir sürü taşı birden çevirmenin verdiği keyif de cabası. En önemlisi, sadece çocuklar için değil yetişkinler için de aynı derecede eğlenceli.
    6 yaşındaki bir çocuğu ezmeden, ama oyunun da sırf şansa dayalı basit bir oyun gibi hissettirmemesini sağlayarak ben de gayet keyif alabildim

    • Benzer şekilde, Afrika taş oyunları ailesinden Hus'a da bir göz atmaya değer.
      https://mancala.fandom.com/wiki/Hus
      Teoride şans yok, ama pratikte zincirleme tepkimeler yüzünden o kadar ileriyi hesaplamak mümkün olmuyor.
      Tahtayı kendiniz de kolayca yapabilirsiniz
    • Benzer nedenlerle Blokus'u da seviyorum

  • Oyunu denemek isterseniz, çocuklarla birlikte yaptığımız bir sürümü buraya koymuştum: https://jawj.github.io/fliptiles
    “AI” oyuncusu çok zayıf

    • Beraberliğin ne kadar büyük bir şey olduğunu bilmiyorum ama ilk oyunda 32-32 çıktı.
      Yeni bir oyun öğrenmiş oldum
    • Etkileyici. Çocukken bu oyunu hep oynardım ama bir süredir varlığını unutmuştum; tekrar deneyince eğlenceli geldi.
      Bilgisayar 33 puan aldı, ben 31

  • Othello'nun önemsiz olduğunu düşünüyorsanız Zebra'yı deneyebilirsiniz
    Orijinal yazarın sitesi: http://radagast.se/othello/
    GitHub kaynak kodu: https://github.com/hoshir/zebra

    • Othello'nun ne olduğunu bilmiyorsanız, Reversi olarak da bilinir

  • Othello'da sevdiğim şey, hamle ile alan arasındaki çelişki
    Oyun ilerlerken kendi turumda hamle yapma eylemi bir bakıma benim aleyhime işliyor, ama yine de mutlaka oynamak zorundayım.
    Bu yüzden, alan fazla daralıp kesin bir etki gücünü yeniden kazanmanız gereken an gelene kadar, alan kaplarken aynı zamanda küçük ve içeride kalmanız gerekiyor

  • Bununla bağlantılı olarak, 6x6 Reversi'yi kusursuz oynayan bir şey de var
    https://mame.github.io/6x6-reversi-oracle/
    Kaynak: https://twitter.com/mametter/status/1476379841004183556
    8x8'in hâlâ çözülmediğini şimdiye kadar bilmiyordum

    • Siyah taşlardan bir tane bile alamıyorum. “Kusursuz” dedikleri şey bu mu?