Monte Carlo tree search with temporal-difference learning for general video game playing
Zamansal-fark öğrenmeli Monte Carlo ağaç araması ile genel video oyunu oynama
- Tez No: 485239
- Danışmanlar: DOÇ. DR. AYŞE ŞİMA UYAR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 109
Özet
Günümüzdeki en önemli ve güncel bilimsel konulardan biri Yapay Zeka (Artificial Intelligence, AI)'dır. Akıllı davranışlar sergileyen sistemlerin tasarlanması ve geliştirilmesi konularını ele alan AI, bir araştırma alanı haline gelmesinden bu yana insan hayatını bir çok yönüyle etkilemiş ve her geçen gün daha fazla ilgi çeker hale gelmiştir. AI özellikle son dönemlerde otomobil, bilgisayar, akıllı telefon gibi cihazların yanı sıra güvenlik, içerik üretimi gibi uygulamaların da vazgeçilmez bir parçası olmuştur.“Akıllı”kelimesi her ne kadar geniş ve ucu açık bir tanıma sahip olsa da, AI'nın hedefindeki başlıca akıllılık öğeleri öğrenme, algılama, planlama ve muhakeme olarak sıralanabilir. Her biri kendine ait alt araştırma alanlarına sahip olan bu yeteneklerin bir çoğunda henüz insan-seviyesinde başarımlar elde edilememiştir. Buna rağmen, AI'nın nihai hedeflerinden biri olan Genel Yapay Zeka (Artificial General Intelligence, AGI) konusunda çalışmalar ise hız kazanmaya devam etmektedir. AGI'ya göre gerçek akıllılık, sadece öğrenme, algılama gibi belirli görevlerde tek başına başarılı olmak değil, tıpkı insanlar gibi tüm bu görevler bütününde belli bir başarıma sahip olmaktır. Bu tür zorlu problemleri bir arada sunan uygulama alanlarından biri olan robotik ve benzeri konular her ne kadar kapsamlı olsalar da çoğu zaman yöntemlerin denenip geliştirimeleri aşamalarında yavaş ve maliyetli olmaktadırlar. Bu sebeptendir ki, AGI için yeterli zorluktaki problemleri barındıran, ancak daha hızlı, daha az maliyetli ve daha basit bir deney ortamı arayışı ile AI araştırmalarının genelinde önemli bir yeri oyunlar, AGI için de son yıllarda sıkça kullanılan bir uygulama alanı haline gelmiştir. Oyunlar, AI araştırmaları için her zaman ilgi çekici konular olmuşlardır. Bunun nedeni kolayca değiştirilebilir, kontrol edilebilir olmaları ve bu sayede istenen zorlukta ve çeşitlilikte problem düzenekleri haline getirilebilmeleridir. Oyunların bir araştırma konusu haline gelmelerinden bu yana, bu konudaki çalışmalar da tüm hızıyla devam etmektedir. Satranç, tavla gibi masa oyunlarından klasik Atari oyunlarına kadar geniş yelpazede bir çok oyunda bugün insan-seviyesinin üzerinde başarımlara sahip teknikler geliştirilmiştir. Ancak bu oyunlardan Go gibi daha karmaşık olanlarındaki başarılar ancak yakın bir geçmişte elde edilebilmiştir. Ve halen, başarılı bir şekilde oynanabilmesi amacıyla üzerinde etkili algoritmalar geliştirilemeyen bir çok oyun bulunmaktadır. Buna ek olarak, tek bir oyuna yönelik yapılan çalışmaların ötesinde, birden çok farklı oyunu oynayabilecek düzeyde bir yapay zekanın geliştirilmesi, AGI araştırmalarında kaydedilecek önemli ve bir o kadar da zorlu bir adım olarak görülmektedir. Bu problemin çözümüne yönelik atılan ilk önemli adımlardan biri Stanford Logic Group tarafından Genel Oyun Oynama (General Game Playing, GGP) konseptinin oluşturulması olmuştur. GGP, tur bazlı masa oyunlarını Oyun Tanımalama Dili (Game Description Language, GDL) ile tanımlayarak farklı oyunların AI etmenleri tarafından anlaşılıp üzerlerinde çalışılmasına olanak sağlamıştır. Yakın geçmişte ise, bu konsepti iki-boyutlu ve gerçek-zamanlı Atari oyunlarına genişleten Genel Video Oyunu Oynama (General Video Game Playing, GVGP) konusu ortaya çıkmıştır. GVGP farklı özelliklerdeki birden fazla video oyununu başarılı bir şekilde oynayabilecek etmenlerin geliştirilmesi problemine verilen isimdir. GVGP, AGI araştırmasında oldukça güncel ve önemli bir konu olması sebebiyle kayda değer miktarda ilgi çekmiş, ve bu alandakı araştırmalar Genel Video Oyunu Yapay Zekası (General Video Game AI, GVG-AI) iskeleti ve yarışmasının çıkışı ile birlikte artış göstermiştir. Günümüz itibariyle bu probleme bir çok farklı yöntem ile yaklaşılmış olsa da, problem hala tam manasıyla çözülememiştir. Literatürde GVGP için geliştirilmiş temel algoritmalardan en önemlilerinden biri Monte Carlo Ağaç Araması'dır (Monte Carlo Tree Search, MCTS). MCTS üzerinde her ne kadar evrimsel algoritmalar, yol bulma teknikleri, ve çok-hedefli yöntemler ile iyileştirmeler yapılmış olsa da, her yönüyle en iyi olabilecek düzeyde bir performansa henüz erişilememiştir. Buna ek olarak, bu geliştirmelerin sadece bir ufak bir kısmında, özellikle oyun alanında çokça kullanılan bir pekiştirmeli öğrenme yöntemi olan zamansal-fark öğrenme kullanılmıştır. Bu tez kapsamındaki çalışmada, MCTS algoritmasının GVG-AI ortamındaki uzağı görememe, oyuna özgü bilgilerden yararlanamama gibi zayıflıkları analiz edilip, bu zayıflıklar özgün bir karma yöntem ile ele alınmıştır. MCTS, genelliğini korurken bir yandan da üzerinde koştuğu oyunlara adapte olabilmesi amacıyla yakın zamanda geliştirilen gerçek çevrimiçi Sarsa(lamda) isimli zamansal-fark öğrenme algoritması ile iyileştirilmiştir. Bu algoritmada, oyun durumlarının doğru bir şekilde değerlendirilerek daha iyi kararlar verilebilmesi amacıyla, MCTS elde ettiği deneyimler ile lineer fonksiyon yaklaşımı tabanlı bir çevrimiçi bir öğrenme gerçekleştirmektedir. Bu lineer fonksiyon yaklaşımı ise oyunlara ait durumlardan çıkarılan GVG-AI'na ait her biri 10 oyun içeren 2 farklı küme üzerinde, önerilen algoritmayı temel MCTS ile kıyaslamak için yapılan toplam 10000 oyun koşturmalı kapsamlı deneylerden elde edilen %20.0 (küme 1 için) ve %49.4 (küme 2 için) kazanma yüzdesi artışları ve oyunlara özgü sonuçlar göstermiştir ki önerilen bu yeni algoritma, oyunların genelinde temel MCTS yönteminden belirgin bir şekilde daha iyidir. Çevrimiçi bir öğrenme tekniğinin kullanılması MCTS'nın bir çok zayıf yönünü giderdiği gibi, kullanılan bu zamansal-fark öğrenmesinin temel algoritma üzerinde yapılan diğer geliştirmelere alternatif olabileceği görülmüştür. Önerilen algoritmanın temel MCTS'nın gerisine düştüğü durumlar ise, kullanılan öznitelik temsilinin bazı oyunlardaki puan kazanma aksiyonları ile bağlantılı olamamasından kaynaklanmaktadır. Bu durumlarda, temel MCTS herhangi bir öğrenme tekniği kullanmadığı için, yaptığı rastgele arama yanlış bir sezgisel eğilim ile yapılan aramadan daha iyi sonuç vermektedir. Bu çalışmalar bir çok geliştirmeye açıktır. İlk olarak, önerilen algoritmada ayarlanması gereken fazlaca parametre bulunmaktadır. Her oyun ve parametre kümesini denemek için gereken süre ve bu parametrelerin birbirlerini de etkilediği faktörü göz önüne alındığında, oyunların genelinde başarılı olacak bir parametre kümesi bulunmasının zorlu bir çalışma olduğu görülmektedir. Buna ek olarak, önerilen algoritmanın her oyunu, oyuna özgü parametreler ile oynamasının genel bir parametre ayarı kullanılmasına göre daha iyi sonuç verdiği gözlemlendiğinden, yapılacak oyun-tabanlı bir otomatik parametre ayarlama çalışması oldukça yararlı olacaktır. Son olarak, deneyler göstermiştir ki uygulanan öğrenme tekniğinin başarısı kullanılan öznitelik temsillerinin kapsamı ile yakından ilgilidir. Bu çalışmada kullanılan, oyun içerisindeki farklı parçaların birbirleri arasındaki en yüksek yakınlıklardan oluşan öznitelik temsili yön, oyun içi kaynaklar gibi bilgileri içermediğinden bazı durumlarda zayıf kalabilmektedir. Daha kapsamlı ve gerekli tüm bilgileri içerecek bir öznitelik temsili geliştirmek de önerilen algoritmanın başarısını artıracak önemli bir çalışma olacaktır.
Özet (Çeviri)
General Video Game Playing (GVGP) is a problem where the objective is to create an agent that can play multiple video games with different properties successfully, with no prior knowledge about them. By being an important field in Artificial General Intelligence (AGI) research, GVGP has drawn a considerable amount of interest, and the research in this field got intensified with the release of General Video Game AI (GVG-AI) framework and competition. As of today, even though this problem has been approached with many different techniques, it is still far from being solved. Monte Carlo Tree Search (MCTS) is one of the most promising baseline approaches for GVGP in literature. Despite having a large set of enhancements including evolutionary algorithms, pathfinding techniques and multi-objective methods, an overall best performance still could not be achieved with MCTS in GVG-AI domain. Moreover, only a little portion of these extensions have utilized temporal-difference learning which is a widely used reinforcement learning technique especially in game domains. In this study, the weaknesses of baseline MCTS method in GVG-AI such as its shortsightedness and not being able to exploit any sorts of domain knowledge are analyzed and addressed with a novel hybrid method. With the aim of making MCTS adapt to the specific games while preserving its generality, it is enhanced with a recently developed temporal-difference learning method, namely true online Sarsa(lambda) for the first time in literature. In this algorithm, MCTS uses its own experience to perform online learning by employing linear function approximation in order to evaluate game states accurately and consequently make better decisions. Experiments have shown that the proposed algorithm significantly outperformed the baseline MCTS in GVG-AI in terms of win percentages and average scores obtained in two sets of 20 games in total with very different properties. It was concluded that incorporating an online learning in MCTS is a way to overcome most of its weaknesses and temporal-difference learning is a viable alternative to the other modifications done in MCTS for GVGP problem. Analyzing MCTS with temporal-difference learning in a larger set of games in order to develop a game-adaptive parameter tuning technique and a more robust feature extraction methods will be important extensions to this work.
Benzer Tezler
- Informed Monte Carlo tree search for board games
Tahta oyunları için bilgilendirilmiş Monte Carlo ağaç araması
EMRE YILMAZ
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara Yıldırım Beyazıt ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATİH NAR
- Düşük hesaplama maliyetine sahip miyopik olmayan adaptif örnekleme ve çevresel izleme için Monte Carlo arama ağacı ve dallanma sınırlama yöntemlerinin uygulanması
Application of Monte Carlo tree search and branch-and-bound methods for non-myopic adaptive sampling and environmental monitoring with low computational cost
PERİHAN KARAKÖSE
Doktora
Türkçe
2024
Mekatronik MühendisliğiFırat ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CAFER BAL
DR. ÖĞR. ÜYESİ HARUN YETKİN
- Verifying maze-like game levels with model checker SPIN
Model kontrolcüsü SPIN ile labirent benzeri oyun seviyelerini doğrulamak
ONUR TEKİK
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilişim Sistemleri Ana Bilim Dalı
DOÇ. DR. AYSU BETİN CAN
DR. ÖĞR. ÜYESİ ELİF SÜRER
- Automated video game testing using reinforcement learning agents
Pekiştirmeli öğrenme yöntemleri kullanarak oyunların otomatik test edilmesi
SİNAN ARIYÜREK
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilişim Sistemleri Ana Bilim Dalı
DOÇ. DR. ELİF SÜRER
DOÇ. DR. AYSU BETİN CAN
- Artificially intelligent players for PVP in MMORPG
MMMORPG'lerde PVP için yapay akıllı oyuncular
TARIK KARŞI
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Grafiği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ZÜMRA KAVAFOĞLU