XVII. Akademik Bilisim Konferansi

BaşlıkSatranç Oyuncusunun Düzeyinin Makine Öğrenmesiyle Tahmini
ÖğrenciHayır
Yazar(lar) Yazar 1
Name: A. Arda Gençali
Org: İTÜ Fizik Mühendisliği Bölümü
Country: TR
E-mail: arda1847_AT_gmail.com

Yazar 2
Name: Onur Kaplan
Org: İTÜ Elektronik ve Haberleşme Mühendisliği Bölümü
Country: TR
E-mail: kaplanonu_AT_gmail.com

Yazar 3
Name: Azmi Özgen
Org: İTÜ Elektronik ve Haberleşme Mühendisliği Bölümü
Country: TR
E-mail: ozgenaz_AT_itu.edu.tr

Yazar 4
Name: Mustafa Can Uslu
Org: İTÜ Fizik Mühendisliği Bölümü
Country: TR
E-mail: mustafacanuslu_AT_gmail.com

Yazar 5
Name: Berkin Malkoç
Org: İTÜ Fizik Mühendisliği Bölümü
Country: TR
E-mail: malkocb_AT_itu.edu.tr
Anahtar Kelimelersatranç, satranç motoru, Elo puanı, makine öğrenmesi
ÖzetSatranç Oyuncularının Yetkinlik Düzeylerinin Makine Öğrenmesine Dayalı Tahmini Bu çalışmada, bir maçı oynayan iki satranç oyuncusunun yetkinlik düzeylerini sadece oyuncuların bu maçtaki hamlelerinden hareketle öngörebilecek makine öğrenmesine dayalı bir yöntemin geliştirilmesi amaçlanmıştır. Günümüzde, satranç oyuncularının uzmanlık düzeyleri resmi olarak Uluslararası Satranç Federasyonu'nca uygulanmakta olan Elo sistemiyle [1] belirlenmektedir. Elo puanlarının hesaplanması tamamen ve sadece oyuncuların birbirleriyle yaptıkları maçların sonuçlarına (galibiyet/mağlubiyet/beraberlik) dayanmaktadır. Buna karşılık, son yıllarda, tarihsel maç sonuçlarına dayanan Elo sistemi yerine, verili bir maçı oynayan iki oyuncunun seviyelerini o maçta yaptıkları hamlelerden hareketle belirleme çabası belirmiştir [2]. Böyle içrek bir yöntemin geliştirilmesi çeşitli faydaları da beraberinde getirecektir: Tarafların Elo puanlarının mevcut olmadığı karşılaşmalar için yaklaşık yetkinlik seviyesinin belirlenebilmesi veya Elo puanının mevcut olduğu durumlarda maçta sergilenen performansın bu puan ile karşılaştırılması. Bu durumlardan ilkine, farklı ülkelerin ulusal değerlendirme puanlarına göre puanlanmış oyuncuların karşılaştırılabilmeleri; ikincisine ise, bir oyuncunun verili bir maçtaki performansının Elo puanından sapma miktarının tespiti ve bu sapmanın sebeplerinin incelenmesi verilebilir (örneğin oyunun gerçekleştiği koşullar veya kasten kötü oynayarak hile yapıyor olma ihtimali). Bu faydalardan daha genel olarak, satrancın standart bir deney zemini sağladığı “uzmanlık” veya “karar verme” gibi çalışma alanlarına genişletilebilecek bazı gözlemlerin edinilmesi mümkün olabilir [3]. Satranç, tam rasyonel bir oyunun sonucunda hangi çıktının elde edileceğinin öngörülememesi anlamında henüz çözülememiş bir oyundur. Bu çözülememişlik, satrancın devasa bir konfigürasyon uzayına sahip çok karmaşık bir oyun olmasından ileri gelmektedir: Satrançta yaklaşık olarak 10^43 tane meşru tahta ve bu tahtaların olası farklı sıralamalarından oluşan yaklaşık 10^120 maç vardır [4]. Buna karşılık, bir satranç maçının metin olarak kaydedilmesi çok kolaydır ve resmi satranç maçlarının hamle dizileri, maç sonuçları ve maçı oynayan iki tarafın Elo puanları çeşitli veritabanlarında tutulmaktadır. Satranç maçlarına dair bu bol miktardaki bilgi, oyuncuların uzmanlık seviyelerinin (Elo puanlarının), maçtaki hamlelerinden belirlenmesinin denenmesi gerekliliğini düşündürmektedir. Bu düşünceyi gerçeklemek adına, çalışmada 50.000 satranç maçından oluşan bir veri kümesi ele alınmış ve herbir maçı oynayan iki tarafın (beyaz ve siyah) Elo puanlarını tahmin edecek bir yöntem geliştirilmeye çalışılmıştır. Maçların yarısı eğitim ('training') kümesi, geri kalan yarısı ise sınama ('test') kümesi olarak kullanılmıştır. Maçların incelenmesi üç farklı açıdan gerçekleştirilmiştir. Birincisi, rok ve piyon terfisi gibi çeşitli bazı özel hamlelerin mevcudiyeti ve hangi hamlede yapılmış oldukları; ikincisi maçın sonucu ve uzunluğu; üçüncüsü ise maçta herbir hamleden sonra ortaya çıkan konfigürasyonların avantaj skorlarından oluşan dizi. Bu üçüncü bilgiyi elde etmek için, hızlanan bilgisayarlar sayesinde çok yüksek kapasitelere ulaşan satranç motorlarından Stockfish kullanılmıştır. Stockfish, çok çekirdekli çalışmayı destekleyen özgür ve açık kaynak kodlu bir satranç motorudur [5] ve günümüz itibarıyla satranç motorları arasında yapılan kuvvet sıralamasında lider konumundadır [6]. Stockfish ve benzeri satranç motorları, maç sırasında oluşan herhangi bir konfigürasyona beyaz tarafın o andaki avantajına tekabül eden ve avantaj skoru adı verilen bir sayı atarlar (siyah avantajlı ise negatif bir sayı). Bu skoru belirlemek için belirli sayıda hamle derinliğine giden bir senaryolama yapar ve ortaya çıkabilecek yeni konfigürasyonlar üzerinden bir hesaplama yaparlar. Yukarıda geçen üç kategoriden bilgilerden hareketle satranç maçları karakterize edilmiştir. Öncelikle, betimsel istatistiklerden, yüksek Elo puanına sahip (uzman) oyuncuların maçlarında beraberlik sonucunun daha sık gözlemlenmesi gibi beklenen bazı sonuçlar elde edilmiştir. Maçları başarılı bir şekilde karakterize eden özellikler arasında, maç boyunca beyazın ve siyahın Stockfish puanlarının ortalaması ve varyansları gibi şaşırtıcı olmayan parametreler bulunmuştur. Ayrıca, satranç maçlarının iyi bilinen üç evresi olan oyun açılışı-oyun ortası-oyun kapanışı evrelerinin tespit edilebildiği görülmüştür. Karakterizasyonu takiben çeşitli makine öğrenmesi yöntemleri (özgül olarak destek vektör makineleri ve saklı Markov modelleri) ile eğitim gerçekleştirilmiştir. Validasyon kümesi üzerinde yapılan parametre optimizasyonundan sonra sınama kümesindeki Elo değerlerinin sayısal olarak tahmini denenmiş ve oyuncuların Elo puanları ortalama olarak %10'dan daha düşük bir hata oranı ile tahmin edilebilmiştir. Elde edilen sonuçlar, satranç oyuncularının uzmanlık seviyelerinin maç hamlelerinden hareket eden içrek bir yöntemle tahmini açısından ümit vericidir. Öte yandan maç hamlelerinde saklı bilgiden daha yüksek oranda istifade eden yöntemlerin kullanılması ile başarımın arttırılabileceği ön görülmektedir. Bu yöntemler arasından yakın gelecekte denenmesi planlananlardan ikisi şunlardır: Oyundaki hamleler için satranç motoru puanlamasından daha fazla faydalanmak [7], örneğin artan hamle sayısı derinliklerinde yaparak oyuncuların hamlelerinin aldığı Stockfish puanlarının gelişimine bakmak (uzman oyuncuların puanlarının daha yüksek derinlikteki değerlendirmede daha yüksek olması eğilimi beklenir) ve maçlardaki farklı evrelerin baştan verili olarak kabul edilmesi yerine evreleri kendisi tespit edecek bir algoritmanın kullanılması (bu tür bir algoritma yakın bir geçmişte, satrançla benzer olarak evrelere sahip olma özelliğine sahip başka veri kümelerinde başarı ile uygulanmıştır [8]). Kaynaklar [1] A. Elo, “The Rating of Chess Players, Past and Present.”, Batsford, Londra (1978). [2] K. Regan ve G. Haworth, “Intrinsic Chess Ratings”, Proceedings of Twenty-Fifth AAAI Conference on Artificial Intelligence içinde, ABD (2011). [3] Örneğin bkz.: H. V. Ribeiro ve ark., “Move-by-Move Dynamics of the Advantage in Chess Matches Reveals Population-Level Learning of the Game”, PLoS ONE 8 (1): e54165. doi:10.1371/journal.pone.0054165 (2013); B. Blasius ve R. Tönjes, “Zipf’s Law in the Popularity Distribution of Chess Openings”, Physical Review Letters 103, 218701 (2009). [4] C.E. Shannon, “Programming a computer for playing chess”, Philosophical Magazine 41: 314 (1950). [5] https://stockfishchess.org/ Son ulaşım: 14.12.2014 [6] http://www.computerchess.org.uk/ Son ulaşım: 14.12.2014 [7] K. Regan ve ark., “Understanding Distributions of Chess Performances”, Proceedings of the 13th ICGA conference on Advances in Computer Games içinde, Hollanda (2011). [8] J. Yang ve ark., “Finding progression stages in time-evolving event sequences”, Proceedings of the 23rd international conference on World Wide Web (WWW '14) içinde, ACM, New York (ABD), 783-794 (2014).
Başlıklar AB-Bildiri
Veri Madenciliği
Yapay Zeka
Dosya
 

 

Powered by OpenConf®
Copyright ©2002-2014 Zakon Group LLC