Bilgisayar Arimaa - Computer Arimaa

Bu makalenin birden çok sorunu var. Lütfen yardım et onu geliştir veya bu konuları konuşma sayfası. (Bu şablon mesajların nasıl ve ne zaman kaldırılacağını öğrenin) Bu makale için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. Kaynakları bulun: "Bilgisayar Arimaa"  – Haberler  · gazeteler  · kitabın  · akademisyen  · JSTOR (Mart 2016) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) Bu makalenin kullanımı Dış bağlantılar Wikipedia'nın politikalarına veya yönergelerine uymayabilir. Lütfen bu makaleyi geliştir kaldırarak aşırı veya uygunsuz harici bağlantılar ve uygun olan yerlerde yararlı bağlantıları dipnot referansları. (Mart 2016) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Bilgisayar Arimaa oyununu ifade eder masa oyunu Arimaa tarafından bilgisayar programları.

2002 yılında, Hintli Amerikalı bilgisayar mühendisi Omar Syed kuralları Arimaa'da yayınladı ve 2020'ye kadar her yıl en iyi üç bilgisayar programını yenebilen ilk bilgisayar programı (standart, hazır donanım üzerinde çalışan) için 10.000 $ 'lık bir ödül açıkladı. üç oyunluk bir seride insan oyuncuları sıraladı.^[1] Ödül, bir bilgisayar programının üç insan oyuncuya karşı 7: 2 oynadığı 2015 yılında alındı.^[2] Oyun birkaç kişinin konusu olmuştur Araştırma kağıtları.

Arimaa'nın durum uzayı

Açılış

Oyunun başında her oyuncunun taşlarını yerleştirebileceği farklı yolların sayısı:

${ displaystyle { dbinom {16} {8}} cdot { dbinom {8} {2}} cdot { dbinom {6} {2}} cdot { dbinom {4} {2}} cdot { dbinom {2} {1}} cdot { dbinom {1} {1}} = 64,864,800}$

Oyuncu 16 olası kareye 8 tavşanı, ardından kalan 8 kareye 2 kedi, kalan 6 kareye 2 köpek, kalan dört kareye 2 at, kalan iki kareden birine bir deve ve fil koyabilir. son kullanılmayan meydanda.

Her oyuncu 64.864.800 açılış kurulumundan biriyle oyuna başlayabildiğinden, açılış için toplam durum alanı:

${ displaystyle 64,864,800 ^ {2} yaklaşık 4,2 cdot 10 ^ {15}}$

Christ-Jan Cox'un yüksek lisans tezinde söylediği gibi, olası başlangıç ​​durumlarının sayısı çok fazla olduğu için, "[i] t, açılış hareketlerinin eksiksiz veri tabanlarını geliştirmenin çok zor olduğu sonucuna varır."^[3]

Yapay zeka teknikleri

Materyal değerlendirme

Bilgisayarın tahtadaki parçaların değerini değerlendirebilmesi önemlidir, böylece bir ele geçirme veya takasın istenip istenmeyeceğini değerlendirebilir. Parçaların göreceli değerinin değerlendirilmesi, devam eden Arimaa araştırmasının bir alanıdır. Şu anda kullanılan bazı sistemler DAPE ve FAME'dir.

Arimaa botlarında kullanılan teknikler

Aşağıdaki teknikler, Arimaa'yı oynayan yapay zeka programlarının bir kısmı veya tamamı tarafından kullanılır:

• Bitboard'lar
• Transpozisyon tabloları
• Zobrist hashing
• Minimax ve Alfa beta budama
• Katil hareketleri ve çürütme tabloları
• Statik değerlendirme işlevi
• Sessiz arama
• Monte-Carlo Ağacı Arama
• UCT

Arimaa botlarında nadiren kullanılan teknikler

• Kitap açma
• Endgame tablebase

Bilgisayar performansı

Bu bölüm için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. (Mart 2010) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Arimaa'nın birçok yönü, bilgisayar programlarının iyi insan oyuncuları yenmesini zorlaştırıyor. Çünkü güçlünün gelişmesi için çok çaba sarf edildi satranç oynama yazılımı, satranca uygulanabilir tekniklerin Arimaa için neden daha az etkili olduğunu anlamak özellikle önemlidir.

Kaba kuvvet arama

Geleneksel satranç programları kullanım kaba kuvvet arama maddi hususların hakim olduğu statik konum değerlendirmesi ile birleştiğinde. Pek çok olası hamleyi incelerler, ancak bir tarafta diğerinden daha fazla taşa sahip olmadıkça, bir dizi hamlenin sonunda kimin kazandığını belirlemede (insanlara kıyasla) iyi değiller. Aynısı Arimaa programları için de geçerlidir, ancak sonuçları pratikte o kadar iyi değildir.

Arimaa'ya kaba kuvvetle arama uygulandığında, aramanın derinliği her oyuncunun her turda sahip olduğu çok sayıda seçenekle sınırlıdır. Bilişimsel olarak, bir oyuncunun kullanabileceği seçeneklerin sayısı, oynayabileceği farklı yolların sayısını yönetir. Bu, dallanma faktörü. Bir satranç oyununda ortalama dallanma faktörü yaklaşık 35'tir.^[4] oysa Arimaa'da yaklaşık 17.000'dir.^[5]

Bu farklı dallanma faktörleri, satrançta her oyuncu için sekiz tur derinliğinde arama yapabilen bir bilgisayarın, Arimaa'daki her oyuncu için yalnızca üç tur derinliğinde arama yapabileceği anlamına gelir:

${ displaystyle 35 ^ {8} yaklaşık 17000 ^ {3}}$

Alfa beta budama

Satranç yazılımı için kaba kuvvet arama derinliği, neredeyse iki katına çıktı. alfa-beta budama Bu, yazılımın, zayıf hareketin olası her devamını incelemeden bir hareketin diğerinden daha iyi olduğu sonucuna varmasını sağlar. Rakip belirli bir hamleyi tek bir cevapla ezebilirse, diğer yanıtları incelemek gerekli değildir, bu da arama hızını önemli ölçüde artırır. Bununla birlikte, Arimaa'da, anahtarları sadece dört adımda bir hareket ettiren taraf, adım tabanlı aramada mevcut kesintilerin sayısını azaltır.

Ayrıca, alfa-beta budamasının faydası, büyük ölçüde hareketlerin dikkate alındığı sıraya bağlıdır. Kötü olanların ihmal edilebilmesi için iyi hareketler kötü olanlardan önce düşünülmelidir. Özellikle, hareketleri kontrol etmek ve yakalamak, budama için anahtardır, çünkü bunlar genellikle diğer hareketlerden çok daha iyidir. Arimaa yazılımında alfa-beta budamanın sağladığı hızlanma daha azdır çünkü yakalamalar daha nadirdir. Arimaa.com'da oynanan derecelendirilmiş oyunlarda, yakalamayla sonuçlanan satranç hamlelerinin yaklaşık% 19'una kıyasla, adımların yalnızca% 3'ü yakalamayla sonuçlanır.

Çoğu Arimaa pozisyonunda, özellikle de tahta hala kalabalıkken oyunun başlangıcına doğru, yetkin bir oyuncu sonraki iki turda herhangi bir taşı kaybetmekten kaçınabilir. Satrançla karşılaştırıldığında, Arimaa her iki oyuncunun da yakalamaları daha uzun süre geciktirmesine izin verir. Aslında, satrançta ilk ele geçirmenin medyan hamle numarası 6. sıradır, Arimaa'da ise 12. sıradır. Mücadele, başlangıçta Arimaa'da daha konumsaldır ve gelecekte bir noktada yakalamaları kaçınılmaz hale getirmek etrafında döner. Bu, kimin maddi olmayan yollarla zemin kazandığını doğru bir şekilde değerlendirmenin önemini büyütür. Bu nedenle, bilgisayar programlarının gücü (milyonlarca pozisyonu inceleyerek), zayıflıkları kadar önemli değildir (pozisyonu kimin daha fazla parçaya sahip olduğundan ayrı olarak değerlendirmek).

Arimaa programlarının açılış aşamalarındaki zayıflığı, kurulum aşamasıyla daha da büyütülür. Satrançta her oyun aynı pozisyondan başlar. Satranç programları, oyundan önce tüm standart açılış hamlelerine cevapların bir listesini derleyerek, "düşünmeye" başlamadan önce genellikle bir düzine veya daha fazla mükemmel hamle yapabilir. İnsanlar da aynı şeyi yapar, ancak açılışlarla ilgili daha küçük ve daha az güvenilir bir hafızaya sahiptir, bu da insanları satrançta görece dezavantajlı konuma sokar. Aksine, Arimaa, parçaları daha ilk parça hareket etmeden önce yerleştirmek için milyonlarca olası yola sahiptir. Bu, programların anlamlı bir açılış kitabına sahip olmasını engeller.

Oyun ilerledikçe, takas ve tavşanların ilerlemesi pozisyonu daha açık ve taktik hale getirme eğilimindedir. Arimaa programları genellikle bu tür bir pozisyonda daha iyi oynar çünkü insanların gözden kaçırdığı taktik atışları görürler. Bununla birlikte, insanların muhafazakar oyunlarla geniş açık pozisyonlardan kaçınması ve bilgisayarların daha kötü olduğu stratejik pozisyonlara açı vermesi genellikle mümkündür. Muhafazakar bir rakibe karşı, Arimaa'da pozisyonu açmak neredeyse imkansızdır, oysa satrançta sadece zordur. Defansif oyunu, programların pek başarılı olmadığı küçük, uzun vadeli avantajların birikimiyle yenmek gerekir.

Arimaa için geçerli olmayan bilgisayar satrancından ek bir teknik: oyunsonu tabloları. Ustalık seviyesindeki satranç oyunları bazen sadece birkaç taşla belirsiz son oyunlara dönüşür, örneğin şah ve at, şah ve kale gibi. Tarafından inşa etmek mümkündür retrograd analizi tüm bu konumlarda doğru hareketin kapsamlı bir tablosu. Programlar yeniden "düşünmek" yerine, bu tür konumlarda önceden oluşturulmuş bir tabloya başvurmak zorundadır, bu da onlara insanlara göre bir avantaj sağlar. Arimaa, aksine, nadiren bir oyunsonuna gelir. Eşit taş alışverişi satrançta olduğundan daha az yaygındır, bu nedenle bir Arimaa oyununun "değiş tokuşu" yapması ve hala belirsiz olması nadirdir. Ortalama bir Arimaa oyununda yalnızca sekiz ele geçirme vardır (satranç için on yedi ele geçirme) ve en iyi insanlar genellikle tek bir taş bile kaybetmeden Arimaa'daki en iyi programları yenebilir, örneğin 2014 Challenge maçının ikinci oyunu. Düşük yakalama yoğunluğunun başka bir örneği de 2012 Dünya Şampiyonası'nın bu yarı final maçı, yalnızca tek bir yakalama, hedefe zorlayan bir fil kurbanı içeriyor.

Omar Syed, geleneksel yapay zeka tekniklerinin Arimaa için yalnızca orta derecede etkili olması nedeniyle, programcıların güçlü bir Arimaa oynama programı oluşturmak için yeni yapay zeka tekniklerini kullanmaya zorlanacağını umuyor. Dünya şampiyonası kalitesinde bir satranç programı inşa etme arayışı, oyunları başarılı bir şekilde oynamak için birçok teknik üretti, ancak esasen daha genel mantığa hiçbir katkıda bulunmadı; aslında, satranç oynama programlarının teknikleri, bazı tanımların dışında bırakılmıştır. yapay zeka; Arimaa için bir amaç, onu oynamaya dahil olan tekniklerin yapay zekanın daha büyük hedeflerine yardımcı olacağıdır.

Syed'in insan-makine mücadelesinin yapısı, donanımdaki ilerlemeleri değil, yapay zeka yazılımındaki gelişmeleri ödüllendirmeye odaklanıyor. Yıllık mücadelede, programlar, tipik, ucuz, kullanıma hazır bir ev bilgisayarı olma kriteri altında Syed'in kendisi tarafından seçilen ve sağlanan makinelerde çalıştırılır. Üst düzey satranç oyuncularına meydan okumak için kullanılanlar gibi pahalı çok işlemcili makinelere ihtiyaç duyan hiç kimseye açık olmayacaktı, özel yapım süper bilgisayar gibi bir şey çok daha az Koyu mavi Arimaa'nın icadına ilham veren bu donanım yoğun yaklaşımın başarısı olmasına rağmen. Syed, 2004 yarışma maçında kullanılan bilgisayarın bile (512 MB RAM'e sahip Pentium 4 2,4 GHz sistemi), eğer sadece uygun yazılımı çalıştırıyorsa, yarışma ödülünü kazanmak için yeterli donanıma sahip olduğuna inanıyor. Süper bilgisayarlar, Arimaa'yı geleneksel AI yazılımını kullanarak kaba kuvvetle fethetme gücüne zaten sahip olabilir ve eğer donanım mevcut hızda ilerlemeye devam ederse, sonunda kişisel bilgisayarlar da olacaktır. Bu nedenle Arimaa yarışma ödülü başlangıçta yalnızca 2020 yılına kadar teklif edildi.

Arimaa Challenge'ı satranç zorluklarıyla karşılaştırmak

Bu bölüm muhtemelen içerir orjinal araştırma. Lütfen onu geliştir tarafından doğrulanıyor iddia edilen ve eklenen satır içi alıntılar. Yalnızca orijinal araştırmadan oluşan ifadeler kaldırılmalıdır. (Nisan 2015) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Arimaa Challenge'da (2015'e kadar) bir bilgisayarın dünya satranç şampiyonunu yendiğini ancak altı nedenden dolayı insanı yenemediği öne sürüldü:

1. Arimaa yeni bir oyundur. Bu nedenle, programcıların sayısı ve bilgisayar Arimaa'ya ayrılan zaman miktarı, bilgisayar satrancına göre çok daha azdır. Bilgisayar satrancında Arimaa'dan binlerce programcı ve 40 yıl daha vardı. Daha sonraki ve daha küçük çaba, bilgisayar Arimaa'da daha az ve daha yavaş ilerleme ile sonuçlandı.
2. Arimaa Challenge için kurallar, bilgisayarın satranç maçlarının kurallarından daha yüksek bir oynama yeteneği göstermesini gerektiriyordu. Arimaa Challenge'da, bilgisayar üç maçta üç insan oyuncuyu yenmelidir. Satranç maçlarında, bilgisayar bir insan oyuncuya karşı bir maç kazanmalıdır.
3. Arimaa Challenge'da, bilgisayarın kazanması için toplam puanın 2 / 3'ünü alması gerekir. Satranç maçlarında, bilgisayarın kazanması için toplam puanın 1 / 2'sinden fazlasını atması gerekir.
4. Arimaa Challenge'da bilgisayarın bir eleme maçı kazanması gerekir. İnsanların bilgisayarın zayıf yönlerini bulmak için bilgisayarın önceki oyunlarını incelemelerine izin verilir. Satrançta, herhangi bir yeterlilik maçı yoktur ve bilgisayarın önceki oyunlarının halka açık olması şartı aranmaz.^{[şüpheli – tartışmak]}
5. Arimaa Challenge'da, bilgisayar oyunlar arasında geliştirilemez. Satrançta bilgisayar oyunlar arasında geliştirildi.
6. Arimaa Challenge'da kurallar, fiyatı 1.000 doların üzerinde olan güçlü veya özel yapım bilgisayarları reddediyor. Ancak, güçlü bir ısmarlama bilgisayar dünya satranç şampiyonunu yendi.

Ancak, Arimaa topluluğu bu argümana nokta nokta itiraz etmektedir. İlk noktaya kadar, Arimaa yeni bir oyundur, bu nedenle oyun topluluğu hala küçüktür ve en iyi oyuncular bile profesyonel oyuncular değildir ve oyunu sadece birkaç yıldır oynamaktadırlar. Böylece Arimaa Challenge'daki insan oyuncular, satranç mücadelesindeki insan oyunculardan çok daha zayıf. İnsan oyuncuların zayıflığı, Arimaa Challenge'ı satrançtan daha kolay fethetmeli, bu da geliştiricilerin sorunu daha kısa bir süre çalıştıkları için telafi ediyor.

Kalan beş puan, Arimaa Mücadelesini yalnızca Kasparov ve Deep Blue ile karşılaştırır ve diğer tüm erkek ve makine satranç maçlarını göz ardı eder. Arimaa Challenge maçı ile en yakından karşılaştırılabilecek satranç maçı, Man vs Machine Dünya Takım Şampiyonası. 2004 ve 2005'te bir takım bilgisayar rakiplerinden oluşan bir takıma karşı oynadı. Her iki yılda da bilgisayarlar geniş bir farkla kazandı. 2005 yılında her üç insan da kaybetti, bilgisayarlar toplam puanın 2 / 3'ünü kazandı, satranç motorları ticari olarak insanların çalışması için mevcuttu ve kullanılan makine donanımı bir süper bilgisayar değil, Arimaa Challenge'da kullanılan donanımla karşılaştırılabilirdi. .

2005'ten beri insan-makine satranç maçları, bilgisayar hakimiyetinin arttığını göstermiştir. Örneğin, 2006 Deep Fritz, Vladimir Kramnik'e Karşı ve 2007 Rybka - Jaan Ehlvest maçları insan oyuncuya ek avantajlar sağladı, ancak bilgisayarlar (ticari donanımla çalışan) yine de galip geldi.

Yazılım geliştiriciler için kaynaklar

Arimaa Motor Arayüzü Brian Haskin tarafından geliştirilen, bir Arimaa motorunun bir kontrolör ile iletişim kurmasına izin veren bir protokol tanımlar.

Belgelere göre: "Bir motor, bir Arimaa oyununun durumunu alabilen ve yapmak için yasal bir hamle seçebilen bir programdır. Bir kontrolör, bir motorla iletişim kurmak ve onu kontrol etmek isteyen herhangi bir şeydir. Bu, basit bir komut dosyasından herhangi bir şey olabilir. motorun, oyunların insanlarla veya diğer motorlarla oynanmasına izin veren bir GUI programına tek bir konumu analiz etmesini sağlamak. "^[6]

Arimaa Motor Arayüzü, resmi Arimaa web sitesi de dahil olmak üzere protokolü destekleyen herhangi bir web sitesinde motoru kontrol etmek ve oyun oynamak için bir motor ve kontrolör uygulamasını, dokümantasyonu ve çeşitli komut dosyalarını içerir.^[7][8]

Araştırma kağıtları

• Wu, David J. (2015). "Kazanan bir Arimaa Programı Tasarlamak" (PDF). ICGA Dergisi. 38 (1): 19–40. doi:10.3233 / ICG-2015-38104.
• Arimaa zorluğu - MCTS ile alfa-beta yöntemlerinin karşılaştırma çalışması
  thesis by Thomas Jakl (Charles University, Prague) Ekim 2011
• Arimaa Oyununda Sıralama ve Değerlendirme Taşı
  David Jian Wu (Harvard College, Cambridge, Massachusetts, ABD), Mayıs 2011
• Arimaa, Yapay Zeka için Yeni Bir Zorluk
  Stefano Carlini (Modena Üniversitesi ve Reggio Emilia, İtalya), Nisan 2010
• MCTS Yöntemleri ve oyun Arimaa
  tezi, Tomas Kozelek (Prag Charles Üniversitesi, Çek Cumhuriyeti) Aralık 2009
• Arimaa oyununun dilbilimsel geometri ile modellenmesi
  Joséoberto Mercado Vega ve Zvi Retchkiman Kösberg tarafından yazılan makale (Instituto Politéico Nacional'den, Proceedings of the 5th International Conference on Computational Intelligence and Games, Milano, İtalya) Eylül 2009
• Arimaa Oynamak İçin Bir Bilgisayar Aracısı Araştırma ve Uygulama
  Sam Miller tezi (Southampton Üniversitesi, İngiltere) Mayıs 2009
• Çok Seçici Bir Aramaya Yönelik Planlar, Modeller ve Taşıma Kategorileri
  Gerhard Trippen tarafından hazırlanan makale (2009 Advances in Computer Games 12 konferansında sunulmuştur, Pamplona, ​​İspanya) Mayıs 2009
• Arimaa, Gerçek Zeka Oyunu?
  Nicolas A. Barriga'nın sunumu (University Tecnica Federico Santa Maria, Şili) Ağustos 2006
• Oyun Arimaa'nın Analizi ve Uygulanması ve Ek B
  Christ-Jan Cox tarafından hazırlanan tez (Universiteit Maastricht, Bilgi ve Ajan Teknolojisi Enstitüsü), Mart 2006
• Güçlü bir Arimaa oynama Programı Oluşturma
  Haizhi Zhong (University of Alberta, Dept. of Computing Science), Eylül 2005
• Dünya Şampiyonu Arimaa Programı Oluşturma
  David Fotland'ın makalesi (www.Smart-Games.com) 2004
• Arimaa - Bilgisayarlar İçin Zor Olacak Şekilde Tasarlanmış Yeni Bir Oyun
  Omar Syed ve Aamir Syed'in makalesi; Uluslararası Bilgisayar Oyunları Derneği Dergisi; Haziran 2003

Dipnotlar