Poster - Mühendislik Fakültesi
Transkript
Poster - Mühendislik Fakültesi
TAVLA OYUNU HAZIRLAYANLAR: Ömer Çağatay AKDOĞAN Gazi BOZKURT DANIġMAN: Ögr. Gör. Dr. Mehmet DĠKMEN BaĢkent Üniversitesi Mühendislik Fakültesi Bilgisayar Mühendisliği Bölümü E-posta: cgtyakdgn@gmail.com gazibozkurttt@gmail.com Projenin Amacı: Ġki kiĢilik tavla oyunu platformunun tasarlanması ve oynanabilir hale getirilmesi. Ġkinci bölümde ise tavla oyununun iki farklı algoritma ve yapay zeka kullanarak bilgisayara karĢı oynatılması. 1) ÖZET 5) TD GAMMON Projede iki kişilik tavla oyunu platformu tasarlanmıştır. Daha sonra çeşitli yapay zeka algoritmaları kullanılarak tavla oyunu bilgisayara karşı iki farklı seviyeyle oynanabilecek hale getirilmiştir Yapay sinir ağları insan beyninin elektronik olarak benzetilmesidir. Yapay sinir ağları büyük sayıda girdisi olan fonksiyonların sonuçlarını istatiksel öğrenme modelleri ile tahmin ya da yakınsama için kullanılmaktadır. Bu bağlantıların sayısal ağırlıkları vardır ve bu ağırlıklar değiştirilerek yapay öğrenme yerine getirilir. Bir nöronun, birçok girdisi vardır. Her girdi kendisini çekirdek ile bağlayan bağlantıdaki ağırlık ile çarpılır. Çekirdek kısmında bu çarpımlardan elde edilen değerler toplanır. Bu toplamdan elde edilen değere aktivasyon değeri denir . 2) MONTE CARLO TREE SEARCH . Karar vermede, özellikle tahta oyunlarında, kullanılan sezgisel (heuristic) bir arama algortimasıdır. MCTS algoritması, ağacın her seviyede yapılan 4 ana adımdan oluşmaktadır: 4) OYUNUN ARAYÜZÜ 1. Seçim: Ağacın kök düğümü R'den başlayarak yaprak düğüm L'ye kadar seçim yapılır. Şekil 1‟de görülen örnekte düğümlerdeki değerler kazanılan oyun sayısı/oynanan oyun sayısı olarak gösterilmiştir. 2. Genişleme: L düğümüne bir ya da daha fazla alt düğüm eklenir. 3. Simülasyon: Eklenen alt düğümden seçimlerle oyun bitene kadar oynanır. başlayarak rastgele 4. Geri dönüş: Oyunun sonucuna göre eklenen alt düğümden kök düğüme kadar olan düğümlerin ağırlıklarını güncellenir. Bir yapay sinir ağı birçok nöronun katmanlar halinde birleştirilmesi ile oluşur. Girdiler katmanı, saklılar katmanı ve çıktılar katmanı olarak adlandırılan bu katmanlar „de görüldüğü gibi oluşturulur. Yapay sinir ağının eğitilmesi içinde geçici fark algoritması, “Temporal Difference Algortiması”, kullanılmıştır. Temel olarak çalışma prensibi, oyuncuya gelen her hamle sırasında yapay sinir ağı kullanarak oynanacak oyun için kazanma tahmini yaptırılır. Bir önceki oyun sırasında yapılan tahmini doğru olduğu varsayılır ve yeni yapılan tahmin ile karşılaştırılır. Buna geriye yayılım, “backpropagation” denilir. Matematiksel olarak her hamleden sonra sinir ağındaki ağırlıklar şu formüle göre düzenlenir: MCTS algoritmasındaki en önemli aşama seçim aşamasıdır. Bu aşamada, eklenmiş alt düğümlerden kazanma oranı (ağırlığı) en yüksek olanı seçmek (expoilation-faydalanma) ile simülasyona en az girmiş düğümlerden birini seçme (exploration-keşfetme) arasında bir denge sağlanmalıdır. Bu iki durum arasındaki dengeyi sağlamak için L. Kocsis ve Cs. Szepesvári tarafından ortaya konan “Upper Confidence Bound for Trees” formülü kullanılmaktadır. 6) SONUÇLAR 3) MCTS TAVLAYA UYGULANMASI MCTS algoritmasının tavla oyununa uygularken, iki tip ağaç düğümü belirlenmiştir; şans düğümleri ve seçim düğümleri. Seçim düğümleri oyuncunun seçim yapması gerektiği durumlarda ağaca eklenmektedir. Şans düğümleri ise zar atıldığında oluşabilecek durumları belirtmek için ağaca eklenmektedir. Dolayısıyla MCTS ağacında bir seviye şans düğümleri ise alt seviyesi seçim düğümü ya da tam tersi olabilmektedir. MCTS ağacındaki seçim düğümü olan kök düğümden başlayarak bütün düğümlerde tekrarlayacak şekilde aynı işlemler uygulanmaktadır: 1. 2. 3. 4. 5. Alt düğümler eklenmemişse alt düğümlerini hesapla ve ekle Eklenen alt düğümlerden birini seç Eğer oyun bitmişse, oyunun sonucu dön. Eğer oyun bitmemişse, seçilen düğümde MCTS çalıştır. (1‟e dön) Çalıştırılan MCTS‟nin sonucunu çağıran düğüme dön. TD-Gammon algoritması, birçok yapay sinir ağı algoritmasının temelini oluşturan geçici fark ile öğrenme yönetimini kullanmaktadır. Eğitilen bu oyuncunun başarısı, eğitim sırasında ne kadar eğitildiğine bağlıdır. Oyuncunun oynayacağı oyuna karar verme süresi çok hızlıdır. MCTS algoritması ise daha önceden bir eğitim gerektirmeyen daha sezgisel bir yöntemdir. Bu algoritmanın başarısı oynanan oyun sayısı ile arttığı için her oyuncu sırasında 30 saniye boyunca bilgisayara düşünme imkanı verilmiştir. 7) KAYNAKLAR 1. Monte Carlo Tree Search. [Çevrimiçi] http://en.wikipedia.org/wiki/Monte_Carlo_tree_search. 2. Bandit based Monte-Carlo Planning. Kocsis, Levente ve Szepesvári, Csaba. 2006, Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science, s. 282–293. 3. Artificial neural network. [Çevrimiçi] http://en.wikipedia.org/wiki/Artificial_neural_network. 4. Bruns, Pete. Monte-Carlo Tree Search in the game of Tantrix. [Çevrimiçi] http://www.tantrix.com/Tantrix/TRobot/MCTS%20Final%20Report.pdf. 5. Game Playing Programs that Learn from Experience. [Çevrimiçi] http://www.cse.unr.edu/robotics/bekris/cs482_f09/sites/cse.unr.edu.robotics.bekris.cs482_f09/fi les/backgammon.pdf. 6. Neural Networks in Plain English. [Çevrimiçi] http://www.aijunkie.com/ann/evolved/nnt1.html. 7. Tesauro, Gerald. Temporal Difference Learning and TD-Gammon. Communications of the ACM. March, 1995, Cilt 38, 3. 8. Lee, Mark. TD-Gammon. [Çevrimiçi] 04 01 2005. http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node108.html. 9. Tsinteris, Kimon ve Wilson, David. TD-learning, neural networks, and backgammon. [Çevrimiçi] http://www.cs.cornell.edu/boom/2001sp/Tsinteris/gammon.htm. 10. Lishout, Francois Van, Chaslot, Guillaume ve Uiterwijk, Jos W.H.M. Monte Carlo Tree Search in Backgammon. [Çevrimiçi] http://www.researchgate.net/profile/Jos_Uiterwijk/publication/228378473_MonteCarlo_tree_search_in_backgammon/links/0fcfd511dfb63a7ab6000000.pdf.