Satranç oyunu, taşlarının yapabileceği hamle olasılıkları ve diğer kuralları düşünüldüğünde basit gibi algılanıp çabuk öğrenilebilse de, ileriki hamleler düşünülüp yapılabilecek hamlelere ait çözüm uzayı oluşturulduğunda, oyunun zorluğu ve stratejik yönü daha iyi anlaşılabilmektedir. Optimizasyon ise mevcut durumlar arasında en iyi çözüm olarak tanımlanmakta olup, bu çalışmada satranç oyununa ait amaç fonksiyonu için kullanılmıştır. Satranç oyununda derinliğe göre milyonları bulabilen olası hamlelerin taranabilme zorluğu dolayısıyla, belli bir derinlikten sonra klasik arama algoritmaları ile çözüme ulaşılamamaktadır. Bu çalışmada, sezgisel algoritmaların gücü ile bu sorun aşılmaya çalışılmıştır. Sezgisel algoritmalar gücünü tüm uzayı taramak yerine umut vaat eden bölgelere odaklanıp en iyi sonucu aramalarıyla elde etmektedirler. Bu tez çalışmasında, satranç oyununda daha derinlerde yer alan çözümlerin aranmasında sezgisel yöntemlerden yararlanılıp, kümeleme tabanlı global optimizasyon, yapay arı kolonisi vb. popüler yöntemler açıklanmıştır. Bu yöntemlerin kendi aralarında yaptıkları karşılaşmalar, SCHACKNYTT (chessnews)'de yayınlanan ünlü satranç oyuncularının oynadığı popüler oyunlardaki stratejik hamlelerin tahmini ve çeşitli oyun sonu hamlelerinin tahmini baz alınıp, yöntemlerin performansları elde ettikleri puanlara göre test edilip karşılaştırılmıştır. Ayrıca geliştirilen yazılım, kullanıcı arabirimi sayesinde insan ve piyasadaki diğer satranç motorlarına karşı da oyun oynayabilmektedir. Deneysel çalışmalarda elde edilen sonuçlar, satranç oyununda arama yöntemi olarak sezgisel yöntemlerin kullanılmasının avantajlarını vurgularken, daha derinlerde arama yapılabilmesi olanağını da ortaya koymaktadır. Anahtar Kelimeler: Satranç oyunu, Arama algoritmaları, Sezgisel arama, Kümeleme tabanlı global optimizasyon, Oyun teorisi, Oyun ağacı.
Chess game, despite perceived to be as simple and learned quickly, in terms of the possibilities that can move the pieces and when the other rules are considered, the difficulty of the game and its strategic aspect can be better understood, when further moves are considered and the solution space of the for coming moves is created. Optimization is defined as the best solution in the present circumstances, and used for the objective function of the chess game in this study. Due to the difficulty of screening the possible moves which according to the depth of the chess game can be millions in numbers, after a certain depth, a solution can not be reached by conventional search algorithms. In this study we tried to overcome this problem with heuristic algorithms power. Power of heuristic algorithms are achieved by focusing on the promising regions and searching for the best results instead of scanning the entire space. In this thesis study, in the aspect of investigation of in depth solutions to the chess game, benefited from the intuitive method, global optimization based on clustering, and popular methods such as artificial bee colony et al. are described. These methods that they encounter among themselves, are based on the estimation of strategic moves in the popular games that the famous chess players took part in as published in SCHACKNYTT (chess news), and estimation of various endgame moves, the performances of the methods are tested according to the points earned and compared. Furthermore, the developed software, thanks to the user interface, can play against people and other chess engines in the market. The results obtained in experimental studies, emphasizing the advantages of the use of heuristic method as a searching tool as well as revealing the possibility of deeper search. Keywords: Chess game, Search algorithms, Heuristic search, Global optimization based on clustering, Game theory, Game tree.
Tez (Doktora) - Süleyman Demirel Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Anabilim Dalı, 2016.
Kaynakça var.
Satranç oyunu, taşlarının yapabileceği hamle olasılıkları ve diğer kuralları düşünüldüğünde basit gibi algılanıp çabuk öğrenilebilse de, ileriki hamleler düşünülüp yapılabilecek hamlelere ait çözüm uzayı oluşturulduğunda, oyunun zorluğu ve stratejik yönü daha iyi anlaşılabilmektedir. Optimizasyon ise mevcut durumlar arasında en iyi çözüm olarak tanımlanmakta olup, bu çalışmada satranç oyununa ait amaç fonksiyonu için kullanılmıştır. Satranç oyununda derinliğe göre milyonları bulabilen olası hamlelerin taranabilme zorluğu dolayısıyla, belli bir derinlikten sonra klasik arama algoritmaları ile çözüme ulaşılamamaktadır. Bu çalışmada, sezgisel algoritmaların gücü ile bu sorun aşılmaya çalışılmıştır. Sezgisel algoritmalar gücünü tüm uzayı taramak yerine umut vaat eden bölgelere odaklanıp en iyi sonucu aramalarıyla elde etmektedirler. Bu tez çalışmasında, satranç oyununda daha derinlerde yer alan çözümlerin aranmasında sezgisel yöntemlerden yararlanılıp, kümeleme tabanlı global optimizasyon, yapay arı kolonisi vb. popüler yöntemler açıklanmıştır. Bu yöntemlerin kendi aralarında yaptıkları karşılaşmalar, SCHACKNYTT (chessnews)'de yayınlanan ünlü satranç oyuncularının oynadığı popüler oyunlardaki stratejik hamlelerin tahmini ve çeşitli oyun sonu hamlelerinin tahmini baz alınıp, yöntemlerin performansları elde ettikleri puanlara göre test edilip karşılaştırılmıştır. Ayrıca geliştirilen yazılım, kullanıcı arabirimi sayesinde insan ve piyasadaki diğer satranç motorlarına karşı da oyun oynayabilmektedir. Deneysel çalışmalarda elde edilen sonuçlar, satranç oyununda arama yöntemi olarak sezgisel yöntemlerin kullanılmasının avantajlarını vurgularken, daha derinlerde arama yapılabilmesi olanağını da ortaya koymaktadır. Anahtar Kelimeler: Satranç oyunu, Arama algoritmaları, Sezgisel arama, Kümeleme tabanlı global optimizasyon, Oyun teorisi, Oyun ağacı.
Chess game, despite perceived to be as simple and learned quickly, in terms of the possibilities that can move the pieces and when the other rules are considered, the difficulty of the game and its strategic aspect can be better understood, when further moves are considered and the solution space of the for coming moves is created. Optimization is defined as the best solution in the present circumstances, and used for the objective function of the chess game in this study. Due to the difficulty of screening the possible moves which according to the depth of the chess game can be millions in numbers, after a certain depth, a solution can not be reached by conventional search algorithms. In this study we tried to overcome this problem with heuristic algorithms power. Power of heuristic algorithms are achieved by focusing on the promising regions and searching for the best results instead of scanning the entire space. In this thesis study, in the aspect of investigation of in depth solutions to the chess game, benefited from the intuitive method, global optimization based on clustering, and popular methods such as artificial bee colony et al. are described. These methods that they encounter among themselves, are based on the estimation of strategic moves in the popular games that the famous chess players took part in as published in SCHACKNYTT (chess news), and estimation of various endgame moves, the performances of the methods are tested according to the points earned and compared. Furthermore, the developed software, thanks to the user interface, can play against people and other chess engines in the market. The results obtained in experimental studies, emphasizing the advantages of the use of heuristic method as a searching tool as well as revealing the possibility of deeper search. Keywords: Chess game, Search algorithms, Heuristic search, Global optimization based on clustering, Game theory, Game tree.