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:
[email protected]
[email protected]
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.