Search

Računalna igra GRAPHCOL2 je igra sume nula u kojoj igrač igra protiv računala. Računalo za odabir poteza koristi algoritam pretraživanja stabla zvan minimax. U igri korisnik i računalo naizmjenice bojaju vrhove grafa, pritom poštujući pravila bojanja grafa. U ovom radu opisana je povijest bojanja grafova, vrste bojanja grafova, algoritam minimax i njegove optimizacije, te način rada računalne igre GRAPHCOL2. Također su priložene upute za korištenje računalne igre. Ključne riječi: bojanje grafova, minimax algoritam, alfa-beta podrezivanje, ograničavanje dubine Computer game GRAPHCOL2 is a zero-sum game in which a player plays against the computer. The computer chooses its next move with a tree search algorithm called minimax. In the game the user and the computer during their turn color vertices of the graph, while following graph coloring rules. This thesis describes the history of graph coloring, the types of graph coloring, the minimax algorithm and its optimizations, as well as how the GRAPHCOL2 computer game works. Instructions for using the computer game are also provided. Keywords: graph coloringm, minimax algorithm, alpha-beta pruning, depth limiting

Many IoT applications and services such as smart parking and smart traffic control contain a network of different analytical components, which are composed in the form of a workflow to make better decisions. These workflows are also known as stream workflows. The focus of existing research works is on the streaming operator graph, which differs from stream workflow application as it involves heterogeneity, multiple data sources and multiple outputs. Considering the complexity and dynamism of stream workflow, meeting real-time data analysis requirements at deployment time is not the whole story as the velocity of data changes over time. This change is the most dynamic form of stream workflow that occurs frequently during the execution of this application. In this article, we propose a new dynamic scheduling technique that manages cloud resources over time to handle data velocity changes in stream workflow while maintaining user-defined real-time data analysis requirements and minimising execution cost. The efficiency of the proposed technique is evaluated, and experimental results showed that this technique outperformed its competitors and is close to the lower bound. Refereed/Peer-reviewed

En aquest projecte es farà l’estudi, el anàlisi i el disseny de diferents algoritmes de cerca heurística per el joc del escacs, entre els quals es troben dos tipus de estratègia computacional. Per una banda la força bruta, on trobem l’algoritme de Minimax, per el que es dissenyen heurístiques adequades al problema (joc), i també la poda alfa-beta, una millora de l’algoritme Minimax. Per altre banda tenim l’algoritme Monte Carlo Tree search que incorpora la aleatorietat i la estadística per trobar la millor jugada encara que no trobi la solució més optima. Posteriorment es passarà a implementar els algoritmes en Python, per avaluar i comparar el grau d’èxit de cada un de les solucions plantejats. Es dissenyaran un conjunt de proves per comparar les decisions al jugar màquina contra màquina i màquina contra humà. En este proyecto se hará el estudio, el análisis y el diseño de diferentes algoritmos de búsqueda heurística para el juego del ajedrez, entre los cuales se encuentran dos tipos de estrategia computacional. Por un lado, la fuerza bruta, donde encontramos el algoritmo de Minimax, para el que se diseñan heurísticas adecuadas al problema (juego), y también la poda Alfa-Beta, una mejora del algoritmo Minimax. Por otro lado, tenemos el algoritmo de Monte Carlo Tree Search que incorpora la aleatoriedad y la estadística para encontrar la mejor jugada aunque puede que no encuentre la solución óptima. Posteriormente se pasará a implementar los algoritmos en Python, para evaluar y comparar el grado de éxito de cada una de las soluciones planteadas. Se diseñarán un conjunto de pruebas para comparar las decisiones al jugar máquina contra máquina y máquina contra humano. In this project, the different heuristic search algorithms for chess will be studied, analyzed and designed, among which there are two types of computational thinking. On the one hand, brute force, where we find the Minimax algorithm, for which appropriate heuristics are designed for the problem (game), and also Alpha-Beta pruning, an improvement on the Minimax algorithm. On the other hand, we have the Monte Carlo Tree Search algorithm that incorporates randomness and statistics to find the best play although it may not find the optimal solution. Afterwards, the algorithms will be implemented in Python, to evaluate and compare the degree of success of each of the proposed solutions. A set of tests will be designed to compare the decisions when playing machine against machine and machine against human.

Chess is one of the most ancient games in humanity's history. It has been studied and explored for centuries, and the resulting knowledge has been stored in books of theory, still used today to teach chess apprentices. Since their introduction in the 20th century, chess algorithms have proved that chess is very computationally intensive at high-level play. However, thanks to the ever-increasing computational prowess of modern computers, as well as software-side optimizations, the best modern chess engines have long surpassed human capabilities. In 1997, the famous computer Deep Blue made history by defeating reigning world champion Garry Kasparov in a series of 6 games, after losing to the world champion the previous year. Being fascinated by the field of AI algorithms, and as a chess beginner myself, I set off to develop a game, called Easy Chess, as the Final Project of my Computer Engineering degree, that would help players hone their chess abilities and allow them to become better players. This article will go over the development of a chess engine within the computer game, by looking at my initial objectives, the methodology I followed to implement the algorithm, some development details, as well as the final results of the chess engine and the game's interface. Els escacs són un dels jocs més antics de la història de la humanitat. Han set estudiats i explorats durant segles, i el coneixement resultant ha sigut emmagatzemat en llibres de teoria, utilitzats encara avui dia per entrenar nous aprenents. Des de la seva introducció en el segle XX, els algorismes d'escacs han demostrat que és un joc molt exigent a escala computacional. Ara bé, gràcies a les constants millores pel que fa a la capacitat de còmput dels ordinadors actuals, i de les progressives optimitzacions quant a software, els millors motors d'escacs actuals són ja superiors als millors jugadors humans. L'any 1997, el famós ordinador Deep Blue va fer història en vèncer Garry Kasparov, el Campió del Món d'Escacs, en una sèrie de 6 partides, després d'haver perdut contra el campió l'any anterior. Degut a la meva fascinació pel món dels algorismes d'intel·ligència artificial i a la meva afició als escacs, vaig decidir desenvolupar un joc, anomenat Easy Chess, que permetés als usuaris millorar les seves habilitats i convertir-se en millors jugadors, en el marc del meu Treball Final de Grau pel grau d'Enginyeria Informàtica. Aquest article tracta sobre el desenvolupament del motor d'escacs i el joc 2D, a través de l'explicació dels objectius inicials, la metodologia seguida, detalls del desenvolupament i els resultats finals del projecte. El ajedrez es uno de los juegos más viejos de la historia de la humanidad. Ha sido estudiado y explorado durante siglos, y el conocimiento resultante ha sido almacenado en libros de teoría, utilizados aun hoy día para entrenar nuevos aprendientes. Desde su introducción en el siglo XX, los algoritmos de ajedrez han demostrado que es un juego muy exigente a escala computacional. Ahora bien, gracias a las constantes mejoras en la capacidad de cómputo de los ordenadores actuales, y de las progresivas optimizaciones a nivel de software, los mejores motores de ajedrez actuales son ya superiores a los mejores jugadores humanos. En el año 1997, el famoso ordenador Deep Blue hizo historia al vencer a Garry Kasparov, el Campeón del Mundo de Ajedrez, en una serie de 6 partidas, después de haber perdido ante el campeón el año anterior. Debido a mi fascinación por el mundo de los algoritmos de inteligencia artificial y como aficionado al ajedrez, decidí desarrollar un juego, llamado Easy Chess, el cual permitiera a los usuarios mejorar sus habilidades y convertirse en mejores jugadores, en el marco de mi Trabajo Final de Grado para el grado de Ingeniería Informática. Este artículo trata sobre el desarrollo del motor de ajedrez y el juego 2D, a través de la explicación de los objetivos iniciales, la metodología seguida, detalles del desarrollo y los resultados finales del proyecto.

Rad se sastoji od pisanog i praktičnog dijela. Tema rada je MiniMax algoritam pretrage u šahu, te način kako računalo igra šah. U uvodu se govori o povijesti računalnog šaha, i objašnjeni su principi na temelju kojih računalo odigrava poteze. U glavnom djelu rada govori se o dva algoritma: MiniMax i apha-beta odrezivanju, i objašnjen je njihov princip rada. Zatim slijedi praktični dio, gdje sam opisao kako sam napravio web stranicu u kojoj korisnik može započeti igru, te cilj mu je pronaći šah-mat u maksimalno dva poteza. U zaključku sam se osvrnuo na utjecaj računala na moderni šah., Subject of the thesis is MiniMax algorithm in chess engine. First part speaks about history of computer chess and how computer decides about which move is best to play. The main part is about two search algorithms: MiniMax and alpha-beta pruning. In this section I explained how these two algorithms work, and how computer search for best move to play. Final part is all about my practical work, which contains simple web page, where user can play against computer some chess position. The task of user is mate computer in two moves maximum. User can let computer to mate him or her in two moves also. In conclusion I speak about role of chess engine in modern chess.

With the development of computer game algorithms, some new chesses are gradually included in the competitions in China. Hex is a new game that Chinese have just begun to focus on recently. Since Hex has a priority problem, and the larger the chessboard, the larger the search space. Therefore, how to reduce the costs of search and calculation is an important problem in hex games. It has proposed two strategies based on geometry of its cell geometry (LRC) and chessboard region (CR) for Hex game, and combined them with Monte Carlo tree search. These strategies can be used in Monte Carlo tree search to filter out unreasonable or optimal results at the current level, so as to reduce the scope of search space. A platform has been designed and developed, it provides human-AI even AI-AI interface to the Hex game.

V tem delu predstavimo izvedbo in rezultate različnih algoritmov in metod za igranje večakcijske igre Less. Uporabili smo minimaks algoritem, njegovo optimizacijo z alfa-beta rezanjem in drevesno preiskovanje Monte-Carlo. Vse algoritme smo med seboj pomerili v dvobojih in nato analizirali rezultate in vpliv različnih vrednosti vhodnih parametrov algoritmov. Zaradi velikega vejitvenega faktorja igre Less se je drevesno preiskovanje Monte-Carlo izkazalo kot primernejše za igranje igre od minimaks algoritma. V nadaljni analizi smo ugotovili, da na izide iger ne vpliva prednost prve poteze, močno pa vpliva začetna postavitev igralnega polja. Rezultati so pokazali, da najboljši zasnovani algoritmi premagajo priložnostnega igralca igre Less. In this thesis we present implementation and results from different algorithms and methods for playing multi-action game Less. We have used minimax algorithm, its optimization with alpha-beta pruning and Monte-Carlo tree search. All algorithms have played games between themselves and then we have analyzed results and the influence of different input parameters. Due to the huge branching factor of game Less, the Monte-Carlo tree search has proven to be better choice than minimax algorithm. In the following analysis we have discovered, that the first move advantage does not play role in the outcome of the game, while the initial setting of the tiles does. Results have shown that best designed algorithms can beat occasional player of game Less.

Glavni zadatak diplomskog rada je realizirati automat koji igra klasičnu logičku igru „Poveži 4“. Tehnologije korištene u radu su Arduino IDE (za razvoj programskog koda), Wemos D1 mini Lite, MPR121 i EAGLE (za dizajniranje tiskane pločice). Rad se sastoji od pet cjelina. Prvo poglavlje je uvod, u drugom su opisuje igra „Poveži 4“ i njena pravila. U trećem poglavlju su opisane tehnologije korištene u radu te je detaljno opisan korišteni algoritam. Četvrto poglavlje detaljno opisuje programski kod i dizajniranje tiskane pločice u EAGLE. Posljednje poglavlje je testiranje sustava u kojem je vidljivo kako izgleda jedna partija igre Poveži 4 na realiziranom automatu. Igranje protiv računala je realizirano pomoću minimax algoritma s alfa-beta rezanjem. The main task of this thesis was to create an automat that would play the classic logic game of „Connect 4“. Technologies used in this environment are: Arduino IDE (IDE for code development), Wemos D1 mini Lite, MPR121 and EAGLE (used for the design of printed circuit board). The thesis is divided into five chapters. The first chapter is introduction, the second describes the game of „Connect 4“ and its rules. In the third chapter used technologies and algorithms are described and explained in detail. Forth chapter is explaining the code and the design of the printed circuit board in EAGLE in detail. Last chapter is testing, in which it can be seen how does one game of „Connect 4“ look like on the finished automat. Computer versus player mode is done with minimax algorithm and alpha-beta pruning.

Cilj ovog rada je istražiti kako izraditi šahovskog računalnog igrača. Prvi dio rada odnosi se na teorijsku podlogu zadatka, gdje se detaljno objašnjavaju algoritmi minimaks i alfa-beta podrezivanje. Također, teorijski se obrađuju pojmovi heuristike i isplatne funkcije. Drugi dio rada posvećen je implementaciji. Opisano je kako je izveden algoritam alfa-beta podrezivanja te kako je izvedena heuristička funkcija i jednostavni evaluator pozicije. Konačno, pokazani su rezultati aplikacije testirane na dva računala različitih specifikacija, iznesene su njezine prednosti i nedostatke. The aim of this thesis was to explore how to make a chess computer player, i.e. chess engine. The first part of the paper deals with the theoretical background of the task, where it explains in detail the minimax algorithm and alpha-beta pruning. Also, the concepts of heuristics and utility functions are theoretically addressed. The second part is devoted to implementation. It describes how to implement an alpha-beta pruning algorithm, how to implement a good heuristic function and a simple position evaluator. Finally, the application results are presented based on the performance on two computers with different specifications, its advantages and disadvantages are presented.

In order to solve the problem of time resource and hardware resource waste caused by repeated situations, based on a method proposed by the predecessors to construct a chess computer game knowledge base, this article improves the structure of the knowledge base and uses the hierarchical architecture method to expand the knowledge. The total storage capacity of the library increases the speed of operation. This article's knowledge base master records the best moves and current board situation each time the computer “thinks” through the historical heuristic Alpha-Beta algorithm. Next time, when encountering the same situation, directly search the knowledge base. To get the best move. A comparison of time consumption in the Visual Studio C++ environment demonstrates the validity of the proposed knowledge base.

Minimax Algorithm, is a solution to reduce the burden on hardware in chess engine. However, a more in-depth method is needed to further increase the search algorithm. One of those solutions is called Alpha-Beta Pruning algorithm. The idea is to eliminate the unnecessary nodes in the search tree.

In this study, a GA (Genetic Algorithm) basesented to reduce the chess game tree space. GA is exploited in some studies and by chess engines in order to: 1) tune the weights of the chess evaluation function or 2) to solve particular problems in chess like finding mate in number of moves. Applying GA for reducing the search space of the chess game tree is a new idea being proposed in this study. A GA-based chess engine is designed and implemented where only the branches of the game tree produced by GA are traversed. Improvements in the basic GA to reduce the problem of GA tactic are evident here. To evaluate the efficiency of this new proposed chess engine, it is matched against an engine where the Alpha-Beta pruning and Min-Max algorithm are applied.

Game theory is the formal study of conflict and cooperation, first time introduced as long back as 1921 by mathematician Emile Borel, then enriched in 1928 by von Neumann and Oskar Morgenstern, and much enriched by Josh Nash, has enormous applications, including in business, and even in the prediction of election results, etc. The game playing is also a search process. The chapter presents the classes of games as combinatorial and games of chance, then further as zero-sum games and non-zero-sum games, the prisoner’s dilemma, game playing strategies, the games of perfect information, arbitration scheme in games, minimax search in game playing, and analysis of specific games like tic-tac-toe. The more efficient search processes like alpha and beta are presented, as well as the alpha cutoff and beta cutoff methods to prune the search process are presented and analyzed, followed with chapter summary, and an exhaustive list of exercises along with a number of multiple-choice questions provided at the end.

In this paper, we present methods to strengthen a game AI using advice from other game AIs during game play. People can improve their strength with advice, such as finding better moves or avoiding mistakes. Therefore, to improve the performance of game AIs, we focused on advice. The issues to be considered are the definition of advice and mechanism with advice for move selection. In this paper, we propose that “advice” are moves selected by an adviser and propose a mechanism that makes a player search again when the player’s move is different from advice. We performed tournaments among the proposed systems and other methods against a single engine to compare the strength in shogi. We showed the effectiveness of the proposed method from the experimental results and demonstrated that game AIs can improve their strength with advice. In addition, we found that the advice from a weaker game AI is still useful for game AI.

AlphaZero used a combination of Monte-Carlo Tree Search as well as deep neural networks that learned without human knowledge. It demonstrated that reinforcement learning by self-play could surpass the human champions. The great success of AlphaZero seems that every AI tasks can be trained and learned without any human knowledge as well as any human heuristics. But this paper presents another viewpoint: the AlphaZero approach is good at the perspective of overall situations, and miniMax search (with alpha-beta pruning) is adept in discovering partial solutions. Therefore, we introduce the Two-Phase-Win strategy to combine AlphaZero and miniMax search with alpha-beta pruning for improving AlphaZero’s strength. It has improved the strength of the AlphaZero approach applied to Connect4. The results of experiments show that the Two-Phase-Win strategy has 58% win rate against the AlphaZero approach and doesn’t lose any game in a 100-game match.

Algorithms make up a crucial part of computer science studies. Learning and understanding new algorithms can be quite interesting, but also hard and complex, especially for students. Visualization can significantly help with the understanding of the dynamic behaviour of algorithms by visually displaying each step of the algorithm, its purpose and how it changes the data. Besides faster and more efficient learning, the better understanding can also lead to potential algorithm improvements in the future. The goal of this thesis is visualization of the alpha-beta tree search algorithm for determining the next optimal move in a two-player, zero-sum, complete information game. The algorithm is visualized using two games, Tic-Tac-Toe and Othello. The algorithm operation can also be demonstrated using a custom tree with parameters chosen by the user. Algoritmi predstavljajo ključni del študija računalništva. Učenje in razumevanje novih algoritmov je lahko zelo zanimivo, ampak tudi naporno in zapleteno, zlasti za študente. Vizualizacija lahko bistveno pripomore k razumevanju dinamičnega delovanja algoritma tako, da grafično prikaže vsak njegov korak, namen in način spreminjanja podatkov, kar lahko v prihodnosti pripomore k potencialnim izboljšavam algoritma. Cilj diplomske naloge je vizualizacija alfa-beta preiskovanja drevesa igre, s katerim določimo naslednjo optimalno potezo v igri z dvema igralcema, ničelno vsoto in popolno informacijo. Alfa-beta algoritem je optimizacija algoritma minimax, ki išče najboljšo rešitev skozi drevo igre, tako da odreže veje, ko je že našel boljši korak. To znatno skrajša čas računanja in omogoča, da veliko hitreje iščemo po drevesu iger. Upoštevati je treba tudi, da je stopnja izboljšanja, ki jo doseže algoritem alfa-beta, močno odvisna od vrstnega reda raziskovanja vozlišč. Prej ko se odkrije boljše stanje, prej lahko druge veje s slabšim stanjem zavržemo. Pri vizualizaciji algoritma iskanja dreves, zlasti za bolj zapletene igre, je treba določiti nekatere omejitve. V večini primerov ni mogoče poiskati celotnega drevesa, saj bi dobili obsežno drevo z ogromnim vejitvenim faktorjem in globino, ki ga ni mogoče pregledati v smiselnem času. Zaradi tega bi morali določiti nekatere omejitve, kot je omejitvi globina iskanja. Za vizualizacijo postopka odločanja algoritmov in predstavitev prednosti alfa-beta obrezovanja smo izdelali spletno aplikacijo z uporabo JavaScript in D3.js knjižnice za ustvarjanje močnih in interaktivnih vizualizacij v brskalniku. Vizualizacija delovanja algoritmov minimax in alfa-beta je izvedena na primeru dveh iger, križci-krožci in Othello. Delovanje algoritma je možno ponazoriti tudi na po meri ustvarjenem drevesu, katerega parametre izbere uporabnik. Spletna aplikacija tako služi kot uporabno učno orodje. Za postopek vizualizacije smo implementirali splošen programski vmesnik, ki ga je mogoče uporabiti za katero koli igro z dvema igralcema, ničelno vsoto in popolno informacijo. Uporabi se lahko tudi za kateri koli drug algoritem preiskovanja drevesa igre. Čeprav je vmesnik za vizualizacijski program uporaben za druge algoritme, je še vedno zelo odvisen od domene. Z nadaljnjimi izboljšavami se lahko njegove funkcionalnosti razširijo, da bi lahko ponudili še bolj specifične rezultate.

This paper deals with realization of search algorithms used in the game solvers on the FPGA. Three algorithms namely Minimax, Alpha-Beta Pruning, and NegaScout are realized and compared amongst each other, and also with their software realization for the sake of completion. Results show that the FPGA based implementations are exceptionally faster than their software counterparts, with the NegaScout algorithm outperforming the conventionally used Alpha-Beta Pruning, and the Minimax algorithm, both in software and hardware. The NegaScout algorithm is 1.3 times faster than the Alpha-Beta Pruning algorithm and 2.6 times faster than the Minimax algorithm on hardware, while incurring a nominal cost in terms of FPGA resource utilization.

Distributed approaches of the Alpha-Beta search algorithm are commonly used as decision-making resources in agents designed for operating in competitive environments involving elevated state spaces. In this context, the present paper proposes a new master-slave based distributed version of Alpha-Beta, named ADABA (Asynchronous Distributed Alpha-Beta Algorithm), which is inspired upon the relevant Alpha-Beta distributed version known as APHID (Asynchronous Parallel Hierarchical Iterative Deepening). ADABA aims at enhancing the APHID’s performance in the following ways: establishing a new policy for ordering the tasks that are executed by the slaves; and including a thread pool dedicated to improving the operation of the master processor in regards to the results returned by the slave processors. ADABA’s performance is validated by means of tournaments involving two Checkers agents trained by Reinforcement Learning: the ADABA-based Checkers player named ADABA-Draughts, implemented in this paper, and the well successful APHID-based agent called APHID-Draughts.

Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game. This formalism has been used to express games in general game playing and can also model many discrete approximations of real-world scenarios. In this paper, we describe both novel and existing algorithms that compute strategies for the class of two-player zero-sum simultaneous move games. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. We perform a thorough experimental evaluation on six substantially different games for both settings. For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. For the sampling algorithms, the results provide unique insights into their performance and identify favorable settings and domains for different sampling algorithms.

Algoritem minimaks je eden najbolj razširjenih algoritmov za igranje iger med dvema igralcema. Pri tem se uporablja hevristična funkcija, ki ocenjuje, kako koristno je doseči neko stanje v igri za posameznega igralca. V diplomskem delu poskusimo tako funkcijo za igranje igre Hex ustvariti avtomatsko z uporabo različnih modelov nadzorovanega strojnega učenja. Učne primere za strojno učenje pridobimo s številnimi odigranimi igrami, ki jih simulira MCTS. Ugotovimo, da je igralec, ki za izbiro potez uporablja algoritem minimaks z α-β in naučeno funkcijo, slabši od igralca, ki igra samo z MCTS. Odkrijemo pa, da igralec, ki združi prednosti obeh omenjenih igralcev, igra bolje od MCTS. Minimax algorithm is one of the most widely used algorithms for playing two-player games. It uses a heuristic function that estimates the benefits of reaching a given game state for both players. In this bachelor thesis we attempt to automatically construct that kind of a function for the game of Hex. Different models of supervised machine learning are trained on learning samples, generated by simulations of MCTS. As a result, the player that uses minimax with α-β and the learnt function performs worse than the player that uses pure MCTS. However, the player combining advantages of both players achieves better results than MCTS.

This paper deals with the trick-taking game of Klaverjas, in which two teams of two players aim to gather as many high valued cards for their team as possible. We propose an efficient encoding to enumerate possible configurations of the game, such that subsequently \(\alpha \beta \)-search can be employed to effectively determine whether a given hand of cards is winning. To avoid having to apply the exact approach to all possible game configurations, we introduce a partitioning of hands into \(981,\!541\) equivalence classes. In addition, we devise a machine learning approach that, based on a combination of simple features is able to predict with high accuracy whether a hand is winning. This approach essentially mimics humans, who typically decide whether or not to play a dealt hand based on various simple counts of high ranking cards in their hand. By comparing the results of the exact algorithm and the machine learning approach we are able to characterize precisely which instances are difficult to solve for an algorithm, but easy to decide for a human. Results on almost one million game instances show that the exact approach typically solves a game within minutes, whereas a relatively small number of instances require up to several days, traversing a space of several billion game states. Interestingly, it is precisely those instances that are always correctly classified by the machine learning approach. This suggests that a hybrid approach combining both machine learning and exact search may be the solution to a perfect real-time artificial Klaverjas agent.

The best reported methods for turn-based multi-player game playing AI algorithms include Max\(^n\), Paranoid and Best Reply Search. All of these methods make decisions by modelling the game by assuming that there is some predetermined play ordering for the players. While this is meaningful for ordered turn-based games, there are a host of scenarios where the players need not be constrained to make their moves in such a manner. Little research has been done for turn-based games of this kind such as financial games that involve buying and selling on the stock market in no specific order (For games with shared resources (e.g., financial games) or simultaneously-played move games, one could alternatively consider multi-player AI algorithms to be those that treat the game with each opponent as a separate game. This is currently open.). In this paper, we shall present and test a new algorithm for multi-player game playing on a game which does not require a fixed sequential play ordering. The game that we have used to demonstrate this is the multi-player Snake Game, also referred to as a “Light Bike” game which is a turn-based game requiring simultaneous moves at every turn. Our newly-proposed scheme, the Multi-Minimax, along with the Added Pruning method, performs better when compared to the similar AI strategies examined in this paper. Additionally, among all the algorithms that did not use the proposed pruning, Multi-Minimax performs the best. We can conclude that, at the least, under certain conditions in the area of multi-player game playing AI, similar results can be replicated with these newly proposed Added Pruning and Multi-Minimax methods. As far as we know, the results presented here are of a pioneering sort, and we are unaware of any comparable results.

The capacity and coverage needs of 5G NR (New Radio) networks are satisfied by deploying a high number of small cells in the coverage area of a macro cell. In 5G Dual Connectivity (DC), these small cells are represented as eNBs with 4G characteristics different from the macro cells which are the 5G NR gNBs. The mobile node (MN) can establish a connection with these cells in different technologies at the same time. To effectively manage this heterogeneity and density, the self-organizing networks can be used as a solution. The mobility load balancing (MLB) and mobility robustness optimization (MRO) are two different schemes in self-optimization to enable load balancing and handover management, respectively. These two functions affect the same parameters (e.g hysteresis, time-to-trigger, cell individual offset) from the opposite way. This conflict is further worsened in DC due to the heterogeneous ultra-dense architecture of 4G small cells at the 5G core. Accordingly, the frequent and ping-pong handovers with dropped and blocked calls are more observed because of this conflict. A key contribution of our work is timely detection of this MLB&MRO conflict through the alpha–beta pruning which is a game-theoretic approach to reduce these problems. This mechanism is based on the principle of pruning the unnecessary leaves on the tree. Thanks to this characteristic, we can overcome the ultra-density to reduce conflict detection time. To utilize the alpha–beta pruning, we consider the small cells as leaves on a tree with corresponding load values. To estimate these loads, we also utilize the G/G/1 queuing system. After finding the small cells which are probable for MLB&MRO conflict, we utilize the two-dimensional Markov chain to disable fluctuations causing this conflict. Results reveal that the proposed strategy reduces the call dropping and blocking probabilities 15% and 23% compared to the traditional MLB&MRO approach.

Most approaches to computerized chess involve some variation of brute force, lookup tables, and Alpha Beta pruning to reduce the width of search trees. Given today's extensive computational power, this is a reasonable approach to designing a program that will win games. Since this method is very different from (and much less efficient than) the way that humans play chess and other similar strategy games, it is desirable for those interested in artificial intelligence to investigate other approaches that rely less on brute force. Our solution was to develop an adaptive program that uses a genetic algorithm in combination with a neural network that can learn after each game it plays. The entire genetic algorithm/neural network component is part of the evaluation function used to rank each board. Given a board configuration, ten attributes are evaluated, each of which is used as the input to the Neural Network. The weights used in the neural network are optimized using the genetic algorithm. Each time the evaluation function is called, the neural network outputs the value for a given board configuration, which will then be used in a recursive search algorithm that uses Alpha-Beta pruning. The weights are adjusted at the end of the game based on its outcome. Sets of weights and game scores are broadcast over a network to enable fully distributed learning.

Game tree search is a classical problem in the field of game theory and artificial intelligence. Fast game tree search algorithm is critical for computer games asking for real-time responses. In this paper, we focus on how to leverage massive parallelism capabilities of GPU to accelerate the speed of game tree search algorithms and propose a concise and general parallel game tree search algorithm on GPU. The performance model of our algorithm is presented and analyzed theoretically. We implement the algorithm for two real computer games called Connect6 and Chess. We also use these two games to verify the effectiveness and efficiency of our algorithm. Experiments support our theoretical results and show good performance of our approach. Compared to classical CPU-based game tree search algorithms, our algorithm can achieve speedups of 89.95x for Connect6 and 11.43x for Chess, in case of no pruning. When pruning is considered, which means the practical performance of our algorithm, the speedup can reach about 10.58x for Connect6 and 7.26x for Chess. The insight of our work is that using GPU is a feasible way to improve the performance of game tree search algorithms.

An approach called generic job-level (JL) search was proposed to solve computer game applications by dispatching jobs to remote workers for parallel processing. This paper applies JL search to alpha-beta search, and proposes a JL alpha-beta search (JL-ABS) algorithm based on a best-first search version of MTD(f). The JL-ABS algorithm is demonstrated by using it in an opening book analysis for Chinese chess. The experimental results demonstrated that JL-ABS reached a speed-up of 10.69 when using 16 workers in the JL system.

The field of game playing is a particularly well-studied area within the context of AI, leading to the development of powerful techniques, such as the alpha-beta search, capable of achieving competitive game play against an intelligent opponent. It is well-known that tree pruning strategies, such as alpha-beta, benefit strongly from proper move ordering, i.e., by searching the best element first. A wide range of techniques have been developed over the years to achieve good move ordering, and improved tree pruning, in the field, in general and in particular, in the alpha-beta search, have been extensively studied. Inspired by the formerly unrelated field of Adaptive Data Structures (ADSs), we had previously introduced the History-ADS technique, which employs an adaptive list to achieve effective and dynamic move ordering, in a domain independent fashion. Our previous results confirmed that it performs well in a very wide range of cases, and in varied types of board games. However, our previous work did not compare the performance of the History-ADS heuristic to any established move ordering strategy. In an attempt to address this problem, we present here a comparison to two well-known, acclaimed strategies, which operate on a similar philosophy to the History-ADS, namely, the History Heuristic, and the Killer Moves technique. We also introduce, in this work, a mechanism by which these established move ordering strategies can be approximated, or directly implemented, in terms of ADSs. We confirm that, in a wide range of two-player and multi-player games, at various points in the game's progression, the History-ADS performs at least as well as these strategies, and, in fact, outperforms them in the majority of cases.