84.688 düzenli ifadeyle uygulanmış 2-ply minimax satranç motoru
(nicholas.carlini.com)- Regex Chess, yalnızca 84.688 düzenli ifade değiştirmesini sırayla çalıştırarak satranç tahtasında yasal ve “tamamen berbat olmayan” bir hamle seçen 2-ply minimax motorudur
- Durum, tek bir dizge içinde yığın ve değişkenleri birlikte barındırır;
push,pop, değişken okuma ve atama gibi komutlar düzenli ifade değiştirmeleriyle işlenir - Koşullu dallanma, etkin durumu ifade eden
%%işaretçisini değiştirme yöntemiyle taklit edilir; global değiştirme sayesinde birden çok durumu tek seferde işleyen SIMD tarzı paralel yürütme mümkün olur - Motor, tüm yasal hamleleri paralel durumlara dönüştürüp rakibin yanıtını da değerlendirir; ancak rakip yanıtının yasallığını da tamamen doğrulayan depth-3 araması yapmaz
- Başta tek hamleye yanıt vermek yaklaşık 30 dakika sürerken, ara değişken silme, eşleşme optimizasyonu, özel amaçlı komutlar ve paralelleştirme ile nihai uygulama konuma bağlı olarak 1-10 saniye seviyesine indi
Regex Chess’in temel yapısı
- Regex Chess, satranç motorunun tamamını 84.688 düzenli ifadeden oluşan bir listeyle kurar
- Çalışma yapısı basittir
- Düzenli ifade listesini sırayla dolaşır
- Mevcut satranç tahtası durum dizgesine her deseni ve değiştirme dizgesini uygular
- Son durumu ekranda gösterir
- Girdi PGN değil,
e2e4gibi başlangıç karesi ve hedef kareyi art arda yazan koordinat biçimidir - Proje kodu GitHub üzerinde yayımlanmıştır
Düzenli ifade CPU’su
- Satranç kurallarını doğrudan düzenli ifadelerle yazmak yerine, önce düzenli ifadelerle çalışan küçük bir bilgisayar oluşturulur
- Bu bilgisayar; dallanmasız koşullu yürütme, tek komut çoklu veri yürütme, yığın ve değişken işlemleri içeren bir komut kümesi kullanır
- Mevcut durum tek bir dizgeyle temsil edilir
%%, etkin yürütme durumunun başlangıcını gösterir#stack:altında yığın öğeleri birikir- Değişkenler
#variable: valuebiçiminde saklanır
-
Yığın ve değişken işlemleri
push,%%\n#stack:\nbaşlığını bulup altına değer ekleyerek bunu yığının en üstüne koyarpop,#stack:satırının hemen altındaki bir satırı kaldırarak yığının en üst değerini siler- Değişken okuma, durum dizgesi içinde
#değişken_adı:değerini bulup değeri kopyalar ve yığının en üstüne ekler - Değişken atama, değişkenin zaten var olduğu ve olmadığı iki durumu da işler
- Zaten varsa mevcut değişken değerini yığındaki değerle değiştirir
- Yoksa yeni bir değişken satırı ekler
- Aynı komutun yanlış sırada yeniden uygulanmasını önlemek için ters tik gibi geçici işaretçiler kullanılır
Dallanmasız koşullu yürütme ve döngü sınırı
- Koşullu yürütme
cond(tag)vereactivate(tag)ile uygulanır - Yığının en üstü
Falseise etkin işaretçi%%,%tagbiçimine çevrilir ve sonraki komutlar o duruma uygulanmaz - Daha sonra
reactivate(tag),%tagdeğerini yeniden%%yaparak ilgili durumu etkinleştirir - Bu yöntemle açık dallanma olmadan koşullu yürütme taklit edilir
- Program düzenli ifadelerin sıralı listesi olduğundan döngüleri doğrudan çalıştıramaz
- Turing-tam hesaplama yapamaz
- Ancak satrançta sonraki hamleyi hesaplama gibi sınırları belli hesaplamalar döngüler açılarak işlenebilir
Global değiştirmeyle paralel yürütme
- Düzenli ifade değiştirmesi dizgenin tamamına global olarak uygulandığı için, tek bir durum dizgesi içine birden fazla
%%yürütme durumu konduğunda aynı komut birden çok duruma aynı anda uygulanır - Örneğin iki yığında ayrı ayrı ikişer tam sayı varken
binary_add()çalıştırılırsa iki toplama aynı anda yapılır fork_inactive(tag), mevcut etkin durumu kopyalar ve kopyayı etkin olmayan etiket durumunda bırakırfork_bool(variable), tek bir durumuTrueveFalsedeğerlerine sahip iki duruma ayırır- Bu yapı, satrançta olası birden çok tahta durumunu tek tek yinelemek yerine eşzamanlı değerlendirmek için kullanılır
Makro assembler ve sembolik yürütme
- Motor, düzenli ifadeleri yalnızca elle doğrudan yazmaz; Python tarzı programları küçük komut dizilerine çeviren bir makro assembler kullanır
fib()gibi Python tarzı kodlarpush,lookup,binary_add,assign_popgibi komut listelerine dönüştürülür- Geleneksel parser ve kod üretimi yerine sembolik yürütme (symbolic execution) kullanılır
- Değişken nesnesi gerçek bir sözlük değil, yapılan işlemleri kaydeden özel bir nesnedir
a = b + 1,lookup('b'),push(1),binary_add(),assign_pop('a')olarak kaydedilir
ififadesi, koşulun doğru olduğu yol ile yanlış olduğu yolu birlikte kaydeder ve sonra yeniden birleştirir- Koşullu dallanmayla karşılaşınca çağrı ağacında iki yol oluşturur
- Birden çok izleme yaparken daha az ziyaret edilen dalı seçerek iki yolu da doldurur
- Birleşme noktası
reactivatekomutuna dönüştürülür
Satranç hamlesi üretme yöntemi
- Satranç motorunu yazmanın kendisi genel dillerdeki satranç motorlarına benzer; temel nokta birden çok durumu paralel işlemektir
- Piyon hamlesi üretimi şu akıştan oluşur
- Tüm beyaz piyon konumlarını bulur
- Her piyon için paralel durum oluşturur
- Özgün ana durumu durdurup piyon bazlı durumları etkinleştirir
- Bir kare ilerleme, iki kare ilerleme ve çapraz taş alma adaylarını tüm piyon durumlarında aynı anda kontrol eder
- Her durumun aday hamle listesini yeniden birleştirir
- Açıklama amaçlı örnek FEN dizgesini doğrudan işler, ancak gerçek uygulama satranç tahtasını 64 kareye ait değişkenlere genişleterek okur ve yazar
- Fil, kale, vezir gibi kayan taşlar ile rok ve geçerken alma da ayrı olarak uygulanmıştır
- Ayrıntılı uygulama chess_engine.py içindedir
Bir turun işlenmesi ve hamle doğrulama
- Bir tur; insanın girdiği hamleyi okumak, bu hamlenin yasal olup olmadığını doğrulamak ve ardından bilgisayarın yanıt hamlesini üretmek sırasıyla ilerler
from_pretty_utf8_to_fen(), Unicode satranç tahtası gösterimini FEN notasyonuna çevirir ve girdinin başlangıç/hedef karelerini çıkarır- İnsan hamlesinin yasallığı ayrı bir kural denetimi koduyla değil, tüm yasal sonraki tahtaları üretip karşılaştırarak doğrulanır
make_move, girilen hamleyi uygulanmış bir tahta oluştururcompute_legal_boards, mevcut konumdan mümkün olan tüm yasal tahtaları üretirfork_on_list, her tahtayı paralel duruma ayırır- Girilen hamlenin uygulanmış sonucundan farklı durumlar
destroy_active_thread()ile kaldırılır
- Yasal hamle yoksa tüm çıktı sabit kodlanmış
"Illegal Move"metnine çevrilir - Bilgisayar yanıtı, siyahın olası yanıt tahtalarını ve puanlarını oluşturduktan sonra
keep_best_scoring_board(score)ile yalnızca en iyi puanlı tahtayı bırakır
2-ply minimax ve kasıtlı sadeleştirme
compute_and_score_legal_boards, depth-2 minimax aramasının çekirdek rolünü üstlenir- Önce bilgisayarın oynayabileceği aday hamleleri üretir, ardından rakibin yanıtlayabileceği hamleleri oluşturarak şahın alınabilir olup olmadığını kontrol eder
- Şah durumu doğrulaması nedeniyle rakip yanıtı da üretildiğinden zaten depth-2 arama yapısı oluşur
- Her aday konum, rakibin en iyi yanıtı verdiği durumdaki puanıyla değerlendirilir
- Tam bir depth-2 minimax değildir
- Rakip yanıt hamlesinin kendi şahını tehdit altında bırakan yasa dışı bir hamle olup olmadığını doğrulamaz
- Bunu tamamen işlemek için depth-3 araması gerekir ve maliyet önemli ölçüde artar
- Bilgisayarın ürettiği yanıtın kendisi yasa dışı hamle değildir; ancak bazı durumlarda rakibin oynayamayacağı hamleleri hesaba katarak gerçekte olduğundan daha zayıf bir yanıt seçebilir
Performans optimizasyonu
- İlk uygulamada insanın bir hamlesine yanıt üretmek yaklaşık 30 dakika sürüyordu
- Nihai uygulama, yazarın makinesinde konuma bağlı olarak yaklaşık 1-10 saniye sürer
- Yaklaşık 100 katlık hız artışı, çeşitli optimizasyonların sonucudur
-
Ara değişken silme
- Değişken okuma, tüm durum dizgesi içinde değişken değerini bulmak zorunda olduğundan O(n) maliyetlidir
- Yürütme durumu fork edildiğinde değişkenler de birlikte kopyalandığı için bellek kullanımı büyür
- Artık gerekmeyen değişkenleri agresif şekilde silip değişken adlarını yeniden kullanarak zaman ve bellek azaltılır
- Bir hamle değerlendirmesinin iç durumu, optimizasyondan önce 10GB iken yaklaşık 300MB seviyesine düştü
-
Düzenli ifade eşleşme optimizasyonu
- Koşul komutunun temizlik amaçlı düzenli ifadesine baştaki satır sonu karakterini dahil etmek bile ilgili komutun verimliliğini yaklaşık 2 kat artırır
- Durum içinde çok sayıda
TrueveFalsedizgesi bulunduğundan, desenin yalnızca yığının en üstündeki değeri hızlı bulacak şekilde sınırlandırılması gerekir - Gereksiz aday eşleşmeleri azaltan küçük desen farkları toplam çalışma süresini etkiler
-
Özel amaçlı komutlar ve paralelleştirme
- Taş konumlarını bulma döngüsü gibi yavaş kısımlar, mevcut komutları birleştirmek yerine tek bir özel düzenli ifade komutunda birleştirilir
- Kale hamlesi üretiminde her yönü sırayla kontrol etmek yerine birden fazla paralel durum oluşturup tek seferde işler
- Konum değerlendirmesi de aday tahta başına paralel durum oluşturarak aynı anda yapılır
- Taş değeri hesaplama gibi aynı işlemin birçok durumda tekrarlandığı işlerde paralel yürütme özellikle etkilidir
Kaynakta yer alan ek uygulamalar
- Kaynakta, metinde derinlemesine açılmayan uygulama öğeleri de bulunur
- Fil, kale, vezir gibi kayan taşların paralel hamle üretimi
- Rok için “ilgili kare saldırı altında mı” prosedürü
- FEN satranç tahtası ile kare bazlı değişken temsili arasında dönüşüm
- Şah ve kale konumu izleyerek rok haklarını algılama
- Geçerken almayı algılama ve izleme
- Binlerce oyun boyunca motor doğruluğunu doğrulayan yaklaşık 2000 satırlık test
- Metin, bu tür amaçsız projelerin kişinin kendi alanı dışındaki birçok bilgisayar bilimi konusunu öğrenmesini sağladığı sözüyle sona erer
- İlgili projeler olarak C’nin
printffonksiyonuyla tic-tac-toe oynayan printf-tac-toe ve 13kB JavaScript Doom klonu da anılır
1 yorum
Hacker News yorumları
Bu, printf()'in Turing-complete olduğunu gösteren ve 13 kB JavaScript ile bir birinci şahıs nişancı oyunu yapan kişinin işi
https://github.com/HexHive/printbf
https://github.com/carlini/js13k2019-yet-another-doom-clone
Yarışmada tamamlama süresi bir aydı, ama mevcut kodu yeniden kullanabilmiş gibi görünüyor
İşin kendisi epey eğlenceli olmuş olmalı; bugün aile ve iş yüzünden böyle bir şeye ayıracak bir aylık serbest zamanı asla çıkaramayacak olmam biraz üzücü
Bu noktada bu işin çılgınca eğlenceli olmanın ötesine geçip tamamen olağanüstü hale geldiğini hissettim. Olası birçok konum hesabı hep paralel gerçekleşiyor; büyüyen bir durum/değişken kümesi, yani thread'ler üzerinde regex çalıştırılıyordu
“Şimdi yaptığımız dilin en sevdiğim kısmına geldik. Regex sihri ve tüm string üzerinde global substitution yapıyor olmamız sayesinde birden fazla thread'i aynı anda çalıştırabiliyoruz!”
Sonucu da güzeldi. “Böyle bir blog yazısının sonunda ne bekliyorsunuz? Pek bir sonuç yok. Sadece daha fazla insanın böyle tamamen işe yaramaz şeyler yapmasını isterim. Gerçekten eğlenceli; bitirmenin ne kadar sürdüğünü kimse umursamıyor, çalışıp çalışmadığını kimse umursamıyor ve bonus olarak kendi alanınızın dışındaki bilgisayar biliminin pek çok alanı hakkında istediğinizden daha fazlasını öğreniyorsunuz.”
Gerçekten harika bir tutum
Buradan çıkan şey, oturup zihnini tek bir şeye odakladığında nereye kadar gidebileceğini bilememenin gücü; aynı zamanda yazarın açıkça son derece yetenekli, deneyimli ve yaratıcı biri olduğu gerçeği
Bir yerlerde bug var gibi görünüyor. Aşağıdaki oyun illegal hamle olmadığı halde “Illegal move, you lose” ile bitiyor
Illegal Move
You Lose.
Game over.
Yukarıdaki oyunun FEN'i:
1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
Ama ikisi de legal hamle olduğu için gerçekten bug
84.688 regex ile satranç oynayan kişiden korkmam, ama tek bir regex ile satranç oynayan kişiden korkarım
Yardım edin, nerd-sniping'e uğruyorum
Aklıma hemen gelen olası sorun backreference
Regex çok uzayacaktır, ama sonuçta fiilen bir satranç motorunu encode ediyor olacaksınız…
Böyle şeyleri görünce şapkamı çıkarıp insanlığın gerçek kahramanlarına ciddi bir minnettarlık sunmak istiyorum
a dosyası hamle bug'ı düzeltildi: https://github.com/carlini/regex-chess/issues/1
Önceki örnek: sed ile yazılmış satranç https://news.ycombinator.com/item?id=6261314
Elbette sed sürümü sed'in kontrol akışı komutlarını kullanıyor ve muhtemelen yalnızca 1 hamle ileriyi arıyor; bu açıdan bu sürümden epey farklı
Bu yalnızca bir satranç motoru değil; aynı zamanda sadece regex kullanarak bir bilgisayar ve assembly dili yapmak da
Normalde a2a4 ile başlayınca bu kadar çabuk kaybetmezsiniz!
Şuna da bakmaya değer: https://codegolf.stackexchange.com/q/3503/32575