Bitboard - Bitboard

Bir bitboard , her bir bitin bir oyun tahtası alanına veya parçasına karşılık geldiği, tahta oyunları oynayan bilgisayar sistemlerinde yaygın olarak kullanılan özel bir bit dizisi veri yapısıdır . Bu, paralel bitsel işlemlerin oyun durumunu ayarlamasına veya sorgulamasına veya oyundaki hamleleri veya oyunları belirlemesine izin verir.

Aynı bitboard'daki bitler, oyunun kurallarına göre birbirleriyle ilişkilidir ve genellikle birlikte alındığında bir oyun konumu oluşturur. Diğer bitboard'lar, konumlar hakkındaki sorguları dönüştürmek veya yanıtlamak için genellikle maske olarak kullanılır. Bitboard'lar, uzay durumlarının veri yapısındaki bitlere eşleştirilmesiyle, ilerlemesi bir oyun tahtasının ayrı alanlarının durumu veya üzerinde parçaların varlığı ile temsil edilen herhangi bir oyuna uygulanabilir. Bitboard'lar, panodaki her parça veya alanın bir dizi öğesi olduğu geleneksel posta kutusu gösterimine göre daha verimli bir alternatif pano temsilidir .

Bitboardlar, kart üzerindeki çeşitli ilgili durumların ilişkili bitleri, CPU mimarisinin tek bir kelimesine veya çift kelimesine sığdığında özellikle etkilidir, böylece AND ve OR gibi tek bitsel operatörler oyun durumlarını oluşturmak veya sorgulamak için kullanılabilir.

Bitboard kullanan bilgisayar oyunu uygulamaları arasında satranç , dama , othello ve kelime oyunları sayılabilir . Program ilk olarak 1950'lerde dama programlarında kullanıldı ve 1970'lerin ortalarından beri bilgisayar otomatlarında oyun tahtası temsili için fiili standart haline geldi.

Açıklama

Daha fazla bilgi: Bit alanı

Bir bitboard, özel bir bit alanı, birden çok ilgili boole değişkenini aynı makine kelimesine paketleyen, tipik olarak bir tahta oyunundaki bir pozisyonu veya bir oyunun durumunu temsil eden bir formattır. Her bit bir alanı temsil eder; bit pozitif olduğunda, bu uzayın bir özelliği doğrudur. Bitboardlar, bilgisayarın bir bit düzeyinde işlemle oyun durumuyla ilgili bazı soruları yanıtlamasına izin verir. Örneğin, bir satranç programı beyaz oyuncunun tahtanın merkezinde (ortadaki dört kare) herhangi bir piyonu olup olmadığını bilmek isterse, oyuncunun piyonları için bit tahtasını, tahtanın ortası için olan bir bit ile, bit şeklinde VE kullanarak karşılaştırabilir. operasyon. Merkez piyon yoksa, sonuç sıfır bit olacaktır (yani sıfıra eşittir). Birden çok bitboard, pano üzerindeki alanların farklı özelliklerini temsil edebilir ve özel veya geçici bitboardlar (geçici değişkenler gibi) yerel özellikleri temsil edebilir veya ara harmanlanmış sonuçları tutabilir.

Bitboardların etkinliği, uygulamanın diğer iki özelliği ile artırılır. İlk olarak bitboardlar, bir parça hareket ettirildiğinde parça konumu için bir bitboarddaki kaynak ve hedef konumlardaki bitleri çevirmek gibi, artımlı olarak güncellenmek için hızlıdır. İkincisi, bir satranç tahtasındaki her konum için her taş türünün saldırdığı tüm boşluklar gibi statik özellikleri temsil eden bitmap'ler önceden harmanlanabilir ve bir tabloda saklanabilir, böylece "e4 alanında bir atın yasal hareketleri nelerdir? " tek bir bellek getirme ile yanıtlanabilir.

Bitfield uygulamaları verimli olmak için modern CPU mimarilerinde AND, OR, NOT ve diğerleri gibi tam kelime (32-bit veya 64-bit) bitsel mantıksal işlemlerin varlığından yararlanır. Bitboard'lar önceki 8 ve 16 bit mini bilgisayar ve mikroişlemci mimarilerinde etkili olmayabilir.

Uygulama sorunları

Büyük tabloların içeriğinin gerekli sıkıştırılması ve kodlanması ve transkripsiyon veya kodlama hataları olasılığının bir sonucu olarak, bitboard programları yazılım geliştiricilerin yazması veya hata ayıklaması için sıkıcıdır. Tabloları oluşturmak için genellikle uygulamanın parçası olmayan yardımcı üretim yöntemleri gerekir.

İşlemci kullanımı

Artıları

Bitboard gösterimleri , bir döngüde tamamlanan ve tamamen ardışık düzenlenmiş ve önbelleğe alınmış hemen hemen tüm CPU'larda bulunan paralel bitsel işlemleri kullanır . Neredeyse tüm CPU'larda AND , OR , NOR ve XOR bulunur . Dahası, modern CPU'lar, yürütme için talimatları sıralayan komut ardışık düzenlerine sahiptir . Birden fazla yürütme birimine sahip bir işlemci, ardışık düzen içinde birden fazla komut mevcutsa döngü başına birden fazla komut gerçekleştirebilir. Dalları olan normal komut dizileri, bir dalın yanlış tahmin edilmesi durumunda boru hattının boşalmasına neden olabilir. Çoğu bitboard işlemi daha az koşul gerektirir ve bu nedenle ardışık düzeneği artırır ve birçok CPU'da birden çok yürütme birimini verimli bir şekilde kullanır.

CPU'lar tasarlandıkları bir bit genişliğine sahiptir ve bu genişlikte bir döngüde bitsel işlemleri gerçekleştirebilirler. Bu nedenle, 64 bit veya daha fazla CPU'da, bir komutta 64 bit işlemler gerçekleşebilir. Daha yüksek veya daha düşük genişlikli talimatlar için destek olabilir. Çoğu 32-bit CPU'nun bazı 64-bit komutları olabilir ve bunlar birden fazla döngü sürebilir veya 32-bit komutlarına kıyasla başka şekilde engellenmiş olabilir.

Bitboard, komut setinin genişliğinden daha büyükse, üzerinde tam genişlikte bir işlem gerçekleştirmek için birden fazla talimat gerekecektir. Dolayısıyla, 64 bit bitboard kullanan bir program 64 bit işlemcide 32 bit işlemciye göre daha hızlı çalışır.

Eksileri

Bitboard temsillerinin hem kaynak hem de nesne kodu olmak üzere çok daha uzun kodu vardır. Uzun bit döndürme dizilerinin yazılması ve hata ayıklaması teknik olarak zordur. Bitboardların kendileri seyrektir, bazen 64'te yalnızca tek bir bit içerir, bu nedenle bitboard uygulamaları yoğun bellek kullanır. Her iki sorun da önbellek atlamalarını artırabilir veya önbelleğin çöpe atılmasına neden olabilir.

İşlemcinin 'birincisi' (veya ' baştaki sıfırları say ') ve ' birleri say ' (veya 'sıfırları say') için donanım talimatları yoksa , bu işlemler kodlama açısından son derece verimsiz olduğundan uygulama önemli ölçüde engellenecektir. assembly dili döngüleri.

Önbellek ve hafıza kullanımı

Artıları

Bit kartlar, parça liste panosu veri yapılarından daha fazla bellek gerektirir, ancak yürütme açısından daha verimlidir çünkü birçok döngü ve karşılaştırma işlemi tek bir (veya az sayıda) bitsel işleme (ler) indirgenir. Örneğin, posta kutusunda, belirleme olup parça saldırıları alan üreten ve hamle döngü gerektirir parça ile son alanı karşılaştırılması alanı . Bitboards ile yasal hamle parça bir bitmap saklanır ve bu harita için bitmap bağlantısı ile bağlanır boşluk . Sıfır olmayan bir sonuç, parçanın uzaya saldırdığı anlamına gelir .

Eksileri

Bazı oyunlar için, bir bitboard motoru yazmak, kompakt posta kutusu / numaralandırma uygulamasından daha uzun olacak veri tabloları dahil olmak üzere makul miktarda kaynak kodu gerektirir. Sınırlı sayıda kayıt veya işlemci talimat önbelleğine sahip mobil cihazlar (cep telefonları gibi) için bu bir soruna neden olabilir. Tam boyutlu bilgisayarlar için, birinci düzey ve ikinci düzey önbellek arasında önbellek eksikliğine neden olabilir. Çoğu makinede bunun bir sorun olmaması için yeterli talimat önbelleğine sahip olacağından, bu yalnızca potansiyel bir sorundur, büyük bir dezavantaj değildir.

Artımlı güncelleme

Bazı bitboard türleri, satrançtaki saldırı haritaları gibi ayrıntılı bir çapraz korelasyon süreciyle diğerlerinden türetilir. Her oyun durumu değişikliğinde (bir hareket gibi) tüm bu haritaların yeniden biçimlendirilmesi çok pahalı olabilir, bu nedenle türetilmiş bit eşlemler aşamalı olarak güncellenir, bu da karmaşık ve kesin kod gerektiren bir süreçtir. Bunu yürütmek çok daha hızlıdır, çünkü yalnızca değişen alanlarla ilişkili bitmap'lerin değiştirilmesi gerekir, kart üzerindeki tüm bitmap'lerin değil. Artımlı güncelleme olmadan, bit eşlemli gösterim, güncellemenin özünde yerel ve artımlı olduğu eski posta kutusu gösteriminden daha verimli olmayabilir.

Önceden hesaplanmış bit eşlemler ve tablo araması

Tahta konfigürasyonlarına bağlı olmayan bazı bitmap türleri, bir at veya kralın saldırdığı 64 boşluğun her birinde yer alan alanlar gibi, tahtanın bir hareketinden veya durum değişikliğinden sonra harmanlanmak yerine tablo aramasıyla önceden hesaplanabilir ve alınabilir. Aksi takdirde bir numaralandırma gerektiren satranç tahtası.

Satranç bitboardları

Bir satranç tahtası üzerindeki taşların konfigürasyonunun açık ve en basit temsili, her bir parçayı tahtadaki konumuna eşleyen, uygun şekilde aranabilir bir sıradaki (en küçüğünden en büyüğüne gibi) bir parça listesi (dizi) şeklindedir. Benzer şekilde, her bir parçanın saldırdığı boşlukları harmanlamak, bir parça için bu tür boşlukların seri bir şekilde sıralanmasını gerektirir. Bu şemaya posta kutusu adresleme denir . Beyaz ve siyah taşlar için ve genellikle beyaz ve siyah piyonlar için ayrı listeler tutulur. Haritalar her harekette güncellenir, bu da parça listesinde doğrusal bir arama (veya bir parça ele geçirilmişse iki) gerektirir. Posta kutusunun avantajı basit koddur; dezavantajı doğrusal aramaların yavaş olmasıdır. Parçaları konumlara eşleyen daha hızlı, ancak daha ayrıntılı veri yapılarına bitboardlar denir .

Standart

Image
Cebirsel gösterim

Bitboard gösterimlerinde, 64 bitlik bir kelimenin her biti (veya 32 bit mimarilerde çift kelime) satranç tahtasının bir karesiyle ilişkilendirilir. Bitlerin karelere herhangi bir eşlemesi kullanılabilir, ancak geniş bir kural olarak, bitler soldan sağa ve alttan üste karelerle ilişkilendirilir, böylece bit 0, a1 karesini, bit 7, h1 karesini, bit 56, a8 karesidir ve bittir. 63, h8 karesidir.

Tahtanın birçok farklı konfigürasyonu genellikle kralların yerleri, tüm beyaz piyonlar, tüm siyah piyonlar ve diğer her bir taş türü için bit tahtaları veya tüm beyaz taşlar gibi parça kombinasyonları dahil olmak üzere kendi bitboard'larıyla temsil edilir. İki saldırı bitboard da evrenseldir: kareye saldıran tüm parçalar için kare başına bir bitboard ve bir parça içeren her kare için bir parçanın saldırdığı tüm kareler için ters bitboard. Bitboardlar, aynı zamanda, 0 - 7 konumlarında bir biti olan, birinci sırayı temsil eden sabitler gibi sabitler olabilir. "Karşıt parçalar tarafından saldırıya uğrayan şahın bitişiğindeki tüm boşluklar" gibi diğer yerel veya geçiş bitboardları, gerekli veya uygun şekilde harmanlanabilir.

Bitboardların kullanımına bir örnek, bir parçanın ödül olup olmadığını belirlemek olabilir : "<boşluk> 'u koruyan tüm dost parçalar için bitboardlar" ve "<boşluk>' a saldıran tüm karşıt parçalar", bir hedef olup olmadığını kolayca belirlemek için parçaları eşleştirmeye izin verir. <boşluk> üzerindeki parça en büyük ödüldür .

Standart bitboardların dezavantajlarından biri, diğer işgal edilen alanlara bağlı olarak sınırsız sayıda saldırı alanına sahip oldukları için kayan parçaların (kale, fil, kraliçe) saldırı vektörlerini harmanlamaktır. Bu, parça başına birkaç uzun maske, vardiya ve tamamlayıcı dizisi gerektirir.

Yardımcı bitboard gösterimleri

Kayan parçaların saldırı vektörleri için bitboardlar oluşturmanın kod boyutu ve hesaplama karmaşıklığı kabul edilerek, bunları harmanlamak için alternatif bitboard veri yapıları tasarlandı. Şövalyelerin, kralların, piyonların ve diğer tahta konfigürasyonlarının bitboard temsilleri, kayan parçalar için yardımcı bitboard kullanımından etkilenmez.

Döndürülmüş bitboardlar

Döndürülmüş bitboardlar, kayan parça saldırı vektörlerinin tablo haline getirilmesini sağlayan tamamlayıcı bitboard veri yapılarıdır; bunlardan biri kalelerin dosya saldırı vektörleri için ve biri de fillerin çapraz ve diyagonal saldırı vektörleri için (kalelerin sıra saldırıları standart bit tahtalarından indekslenebilir) . Bu bitboard'larla, tek bir tablo araması, uzun bitsel işlem dizilerinin yerini alır.

Bu bitboardlar, kart kullanım yapılandırmasını 90 derece, 45 derece ve / veya 315 derece döndürür. Standart bir bitboard, satranç tahtasının her aşaması için bir bayta sahip olacaktır. Bu bitboard ile, bir rütbe boyunca, işgal edilen kare ve rütbedeki işgal edilen konumlar tarafından indekslenen bir tablo kullanarak kale saldırılarını belirlemek kolaydır (çünkü kale saldırıları ilk işgal edilen meydanda durur). Bitboard 90 derece döndürülerek, bir dosya yukarı ve aşağı kale saldırıları aynı şekilde incelenebilir. 45 derece ve 315 derece (-45 derece) döndürülmüş bitboardlar eklemek, köşegenlerin incelenmesinin kolay olduğu bitboardlar oluşturur. Vezir, kale ve fil saldırıları birleştirilerek incelenebilir. Aslında bir bitboard'u döndürmek, düzinelerce talimatı alabilen, önemsiz bir dönüşümdür.

Doğrudan hashing

Kalelerin sıra ve dosya saldırı vektörleri ile fillerin çapraz ve çapraz çapraz saldırı vektörleri ayrı ayrı maskelenebilir ve doluluk durumuna bağlı olarak önceden hesaplanmış saldırı vektörlerinin bir karma tablosunda indeks olarak kullanılabilir, kaleler için 8 bit ve 2-8 bit her biri piskoposlar için. Bir parçanın tam saldırı vektörü, hash tablosundan indekslenen iki tek yönlü vektörün her birinin birleşimi olarak elde edilir. Karma tablosundaki giriş sayısı, 8 * 2 ^ 8 veya 2K bayt sırasına göre mütevazıdır, ancak iki karma işlevi hesaplaması ve parça başına iki arama gereklidir., Kullanılan karma şemasına bakın.

Sihirli bitboardlar

Sihirli bitboardlar, saldırı vektörlerinin doğrudan hashing aramasının zaman-uzay değiş tokuşunun bir ekstrapolasyonudur. Bunlar, hash tablosuna bir indeks olarak tam saldırı vektörünün bir dönüşümünü kullanır. Sihir yanlış bir isimdir ve hafızada depolanması gereken karma tablonun potansiyel boyutunu azaltmak için hilelerle birlikte mükemmel bir karma işlevinin üretilmesi ve kullanılması anlamına gelir , bu 8 * 2 ^ 64 veya 144 eksabayttır. . İlk gözlem, dış karelerin veya birinci ve sekizinci sıraların 'a' ve 'h' dosyalarıyla birlikte saldırı vektörünün doluluğu ile ilgisiz olduğudur: taş bu karelere saldırır veya saldırmaz (diğer engelleyici parçalara bağlı olarak) ne olursa olsun doluluk, dolayısıyla bunlar dikkate alınmadan çıkarılabilir ve geriye sadece 6x6 veya 36 kare (karşılık gelen hash fonksiyonunda ~ bit) kalır. Mükemmel bir karma işlevi gerektiren diğer şemalarda olduğu gibi, karma işlevini oluşturmak için kısmen algoritmik ve kısmen deneme yanılma gibi kapsamlı bir sayım süreci gereklidir. Ancak çözülemeyen sorun devam ediyor: bunlar çok aktif tablolardır ve boyutları (çoğu durumda bir milyondan az giriş), modern yonga mimarilerinin daha düşük seviyeli önbellek boyutlarına göre çok büyüktür ve bu da önbellek taşmasına neden olur. Bu nedenle, birçok uygulamadaki sihirli bitboardlar, daha mütevazı hash oluşturma şemaları veya döndürülmüş bitboardlara göre hiçbir performans kazancı sağlamaz.

Tarih

Bir tahta oyununu temsil etmek için bitboard yöntemi 1950'lerin ortalarında Arthur Samuel tarafından icat edilmiş ve onun dama programında kullanılmış gibi görünüyor. Daha karmaşık satranç oyunu için, yöntemin daha sonra 1960'ların sonlarında Sovyetler Birliği'ndeki Kaissa takımı tarafından bağımsız olarak yeniden keşfedildiği ve 1970'lerin başında ABD Kuzeybatı Üniversitesi programı " Satranç " ın yazarları tarafından yeniden keşfedildiği görülmektedir . 1970'lerin Amdahl ve Cray makineleri gibi süper bilgisayarlarının 64 bitlik kelime uzunluğu, satranç tahtasının 64 karesini bir kelimenin bitlerine uygun bir şekilde eşleyen bitboard temsillerinin geliştirilmesini kolaylaştırdı.

Kayan parçaların hareketlerini harmanlamak için döndürülmüş bitboardlar, 1990'ların ortasında bir ara Cray Blitz ve Crafty satranç motorlarının yazarı Profesör Robert Hyatt tarafından icat edildi ve Dark Thought programlama ekibiyle paylaşıldı. Daha sonra Crafty ve Dark Thought'da uygulandılar, ancak ilk yayınlanan açıklama 1997'ye kadar değildi.

On yıl sonra, maske altındaki bitlerin doluluk durumuna bağlı olarak bir saldırı vektörleri tablosunu indekslemek için maskelenmiş rütbeler, dosyalar ve köşegenler kullanan doğrudan arama yöntemleri tanıtıldı. Karma çarpışmaları ortadan kaldırmak için mükemmel bir karma işlevi kullanan böyle bir şema "sihirli bitboardlar" olarak adlandırıldı. Bununla birlikte, bu tür tabloların büyük boyutu ve yüksek erişim oranları bellek doluluğu ve önbellek çekişmesi sorunlarına neden oldu ve döndürülmüş bitboard yaklaşımından mutlaka daha etkili değildi. Bugün, oyun programları bölünmüş durumda ve en iyi şema uygulamaya bağlı.

Diğer Oyunlar

Satranç dışındaki birçok oyun bitboardlardan faydalanır.

  • In Connect Four , onlar yön başına sadece iki shift + VE işlemleri ile dört ardışık diskler için çok verimli testleri için izin verir.
  • In Conway'in Hayat Oyunu , onlar diziler olası bir alternatiftir.
  • Othello / Reversi ( Reversi makalesine bakın).

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Dış bağlantılar

Hesap makineleri

Dama

Satranç

Nesne

Kod örnekleri

  • [1] Frenzee motorunun yazarı bazı kaynak örnekleri yayınladı.
  • [2] Bitboardların kullanımını gösteren 155 satırlık bir java Connect-4 programı.

Uygulamalar

Açık kaynak
  • Beowulf Unix, Linux, Windows. Döndürülmüş bitboardlar.
  • Crafty Crafty makalesine bakın. Düz C ile yazılmıştır. Eski sürümlerde döndürülmüş bitboardlar, artık sihirli bitboardlar kullanıyor.
  • GNU Satranç GNU Satranç Makalesine bakın.
  • Stockfish UCI satranç motoru 2010 yılı itibarıyla Elo'da ikinci sırada
  • Gray Matter C ++, döndürülmüş bitboardlar.
  • KnightCap GPL. 2300 ELO.
  • Pepito C. Bitboard, yazan Carlos del Cacho. Windows ve Linux ikili dosyalarının yanı sıra kaynak mevcuttur.
  • Simontacci Döndürülmüş bitboardlar.
Kapalı kaynak

Othello

Kelime oyunları