Soru:
Bir motor ilk olarak hangi düğümü arayacağına nasıl karar verir?
Allure
2017-12-25 18:01:34 UTC
view on stackexchange narkive permalink

Bu, Motor Oynatmada Rastgele bir takip sorusudur. SmallChess'in cevabı, bir durumda Stockfish'in 20'lerden sonra belirli sayıda düğüm aradığını ve diğer 20'lerde farklı bir sayıyı aradığını, dolayısıyla rastgelelik olduğunu gösteriyor.

Soru: Her düğüm belirli bir konumsa Stockfish ilk olarak hangi düğümü arayacağına nasıl karar veriyor? Örneğin ilk yarım katı alın. Beyazın 20 olası ilk hamlesi vardır, yani 20 düğüm vardır. Stockfish'in beş düğüm aradıktan sonra bir hamle yapmasını talep ediyorum. Bu, Stockfish'in bir hamle yapmadan önce yalnızca 1. a4, 1. a3, 1. b4, 1. b3 ve 1. c3'ü değerlendirmiş olabileceği anlamına mı geliyor? Bunun gibi sistematik bir arama, Stockfish'in en yaygın ilk hamleleri değerlendirmediği anlamına gelir.

Oyunun ilerleyen bölümlerinde, yarım başına düğüm sayısında büyük bir sıçrama olacağını hayal ediyorum. kat. Bu, Stockfish'in bazen yarım kattaki her düğümü değerlendirmeyi bitirmemiş olsa bile bir hamle yapmaya karar vereceği anlamına gelir. En umut verici düğümlerde arandığını nasıl bilebilirdi?

https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
Bağlantı için teşekkürler, yine de gerçekten anlamadım. Alttaki grafiği söyleyin. A'nın mevcut pozisyon olduğunu ve B, C & E'nin üç aday hamle olduğunu varsayıyorum. İki derinlikte IDDFS A, B, D, F, C, G, E, F'ye giderse ve en iyi hamle E ise, ulaşmadan önce aramayı sonlandırmak zorunda kalırsa, muhtemelen en iyi hamleyi kaçırabilir.
Nasıl bir kopya olabileceğini anlamıyorum - soru açıkça (?) Farklı.
Üzgünüm @user3727079, bu olumsuz oyu kaldırabilir misin? Yardımcı olup olmadığını da söyle.
@XcoderX onu kaldıramaz çünkü sana olumsuz oy veren benim
gönderimi düzenlersem onu ​​kaldırabilir misin?
@SmallChess, SF'nin MCTS (Monte Carlo Ağaç Arama) kullanıp kullanmadığını biliyor musunuz?
Iki yanıtlar:
Fred Knight
2018-01-04 17:59:47 UTC
view on stackexchange narkive permalink

http://rebel13.nl/rebel13/ideas.html bunu iyi açıklıyor.

Temel fikir, programın arama yapmadan en iyi hareket olduğunu düşündüğü şeye dayanarak hareketleri sıralamaktır. Bu puan genellikle hareketlilik, parça kare değeri, merkez kontrolü, geçmiş, saldırı potansiyeli, yakalamalar ve programcının önemli olduğunu düşündüğü diğer unsurlara dayanır. Tıpkı insanlar aday hareketlerini sezgiye ve geçmişe dayandırdığı gibi, bilgisayar da önce en yüksek puanlı hamleyi arar.

Bilgisayar yalnızca beş düğümle sınırlıysa, evet, bilgisayar yalnızca en yüksek beş düğümü arar. puanlama hareketleri. Bu zaman sınırı faktörü, kötü bir şekilde puanlanmışsa, bilgisayarın bir mat-in-one'ı kaçırmasına neden olabilir. Bunu düzeltmenin ilk yöntemi arıza korumaları oluşturmaktı. Durum fark edilir şekilde daha kötü veya önemli ölçüde daha iyi hale gelirse, bunlar aramayı yarıda keser. Umut, zamanı daha iyi kullanabilecek daha fazla varyasyon aramak için daha fazla zaman vermekti. Yinelemeli derinleştirme gibi diğer arama algoritmaları, arıza korumasını yürürlüğe koymadan önce daha kısa bir uzunluğa sahip oldukları için zaman yönetimini iyileştirdi.

QuIcKmAtHs
2017-12-27 12:13:49 UTC
view on stackexchange narkive permalink

Bu sorun, bazı kodlama sorunlarına oldukça benzer. Stockfish'in halihazırda önceden hesaplanmış birden fazla hareket seti var. Birden fazla bitboard kullanan satranç tahtasının durumunu temsil eder ve daha sonra kategorik (kontroller, temposlar, şah matlar) ve istatistiksel gösterimler (parça değerleri) kullanarak tahta konumlarını değerlendirmek için kullanır. Hemen hemen, gelişmiş bir alfa beta arama algoritması kullanır. Aynı konumu birkaç kez analiz etmemek için, bir aktarım tablosu kullanılır. Bu, aslında birçok grafik teorisi programlama probleminde temel olan arama fonksiyonuna uygulanan ezberlemedir. Bu nedenle, aslında oldukça basit bir algoritma kullanır. İşte daha önce yapılan bazı araştırmalar:

Adım 1. Düğümü başlatın

Adım 2. Durdurulan aramayı ve anında çizmeyi kontrol edin. Burada düğüm sınırını zorunlu kılın. (Bu, Stockfish 2.3.1'den itibaren yalnızca 1 arama iş parçacığı ile çalışır.)

Adım 3. Montaj İlişkisi mesafesi budama. Bir sonraki hamlede çiftleşsek bile, puanımız en iyi ihtimalle mate_in (textssrightarrowtextply + 1textssrightarrowtextply + 1 olacaktır, ancak alfa zaten daha büyükse, ağaçta yukarı doğru daha kısa bir mat bulunursa, o zaman daha fazla aramaya gerek yoktur, asla Geçerli alfayı yen. Aynı mantık, ancak ters işaretler, eş vermek yerine çiftleşmenin tam tersi durumunda da geçerlidir, bu durumda bir başarısız-yüksek puan verir.

4. Adım Transpozisyon tablosu araması. Kısmi arama puanının önceki bir tam aramanın üzerine yazmasını istemiyorum. Hariç tutulan bir hareket durumunda farklı bir konum anahtarı kullanıyoruz.

Adım 5. Konumu statik olarak değerlendirin ve ebeveynin kazanç istatistiklerini güncelleyin

6. Adım. Tıraşlama (PV düğümlerinde ihmal edilir)

Adım 7. Statik boş hamle budama (PV düğümlerinde ihmal edilir). Rakibin bir Eğer boş bir hamle yaparsak, puanı futility_margin'den (derinlik) daha fazla azaltacak hamle.

Adım 8. Doğrulama denizi ile boş hareket araması rch

Adım 9. ProbCut. Çok iyi bir yakalamaya sahip olursak ve azaltılmış bir arama betanın çok üzerinde bir değer döndürürse, önceki hamleyi (neredeyse) güvenli bir şekilde budayabiliriz.

10. Adım. Dahili yinelemeli derinleşme.

Adım 11. Hareketler arasında döngü yapın. Hiçbir hamle kalmayana veya bir beta sınırlama oluşana kadar tüm sözde yasal hareketleri tekrarlayın

Adım 12. Kontrolleri ve tehlikeli hareketleri uzatın

Adım 13. Boşluk budama.

Adım 14. Harekete geçin

Adım 15. Azaltılmış derinlik araması (LMR). Hareket başarısız olursa, yüksekler tam derinlikte yeniden aranacaktır.

Adım 16. Tam derinlik arama, LMR atlandığında veya yüksek başarısız olduğunda.

Adım 17. Hareket etmeyi geri al

18. Adım. Yeni en iyi hamleyi kontrol edin

Adım 19. Ayrımı kontrol edin

Adım 20. Eşleşmeyi ve çıkmazlığı kontrol edin

21. Adım Tabloları güncelleyin. Transpozisyon tablosu girişini, katilleri ve geçmişi güncelleyin

Profesörün araştırmasının ne hakkında konuştuğunu açıklamaya çalışacağım. Stockfish, yasal hamle için bir arama ağacı oluşturur. enter image description here Ardından, önce sığ bir arama alanı yürüterek, her hareketin iyi mi yoksa kötü mü ve ne kadar iyi veya kötü olduğunu değerlendirmeye başlar, ve sonra elde edilen alfa / beta sınır değerlerini daha derin bir arama için başlangıç ​​değerleri olarak kullanmak. Stockfish ayrıca parçalara da öncelik veriyor. Örneğin, atlara merkezde öncelik verilir, yani bir at ve fil merkezde çatallanırsa, fili hareket ettirerek başka önemli kazançlar olmadığı sürece atı hareket ettirecektir. Bu karmaşık görünse de, bu uygulama yaklaşık olarak günlüktür (olası hamle sayısı), dolayısıyla hala oldukça hızlıdır.

@user3727079 bu yardımcı olur mu?
Hayır, maalesef. Cevabını anlamıyorum Görünüşe göre, Stockfish kararlarını nasıl alıyor (ağaçları aramanın ne anlama geldiğini anlıyorum) değil, ilk olarak hangi düğümde arama yapılacağı olan sorumu yanıtlıyor gibi görünmüyor.


Bu Soru-Cevap, otomatik olarak İngilizce dilinden çevrilmiştir.Orijinal içerik, dağıtıldığı cc by-sa 3.0 lisansı için teşekkür ettiğimiz stackexchange'ta mevcuttur.
Loading...