Thesis Abstract and Dissertation Abstracts
Ordering Functions for Game Playing
Abstract Category: I.T.
Course / Degree: B. Sc. I.T. (Hons.)
Institution / University: University of Malta, Malta
Published in: 2003
The notion that computers could be used to play intelligent games has been around for some time, commencing with Shannon's initial attempts on games such as chess. initial attempts on games such as chess. Almost everyone nowadays is familiar with ‘Deep Blue’, the computer that beat the (at the time) unbeaten chess champion, Kasparov. But how does a computer decide, in a game such as chess, which moves are better than others?
Calculating all the possible moves in a game is almost always impossible to do (consider calculating all lines of possible moves from the starting position of a chess game), hence, some intelligent way of determining the best moves is required, and this project tackles an aspect of this problem to make the computer player more intelligent when selecting what move to make.
This project attempts to apply a refinement on currently existing and established game-playing techniques. This refinement will ultimately yield the same results as before, only it will yield them faster. This implies that in the same amount of time, more and better moves can be found than before, hence improving the performance of game-playing programs.
The concept that ordering functions could be used to improve intelligent game playing algorithms is an extension on a project developed by Kristian Guillaumier . This project can be considered to be an attempt to work upon that previous project in obtaining valid ordering functions through the usage of genetic algorithms.
In turn-based games such as Mancala, the main problem is having to search through an enormous game tree of possible moves to find the best move to do in a limited amount of time. Even for a relatively simple game like Mancala, the game tree becomes enormous (each game situation opens up into generally another 6 situations), hence, the depth at which one can search makes the selection of the move not a precise one. Often, paths in the game tree are searched for nothing, simply because they are found in the game tree before the other, better paths. Hence, if the better paths are placed or ordered first in the game tree, searching of lesser paths would not occur since a better move has already been found.
Using an evaluation function for the above task would be extremely expensive and too slow to be practical, hence some method which is not as precise as the evaluation function, but still offers a good enough ordering is required, and that is exactly the job of the ordering function. To assign an estimated score to different game situations without being too expensive resource-wise, hence ordering them appropriately in the game tree in a best-first method.
Thesis Keywords/Search Tags:
Ordering Functions Game Playing Game Trees Evaluation Function Minimax Algorithm Alpha-Beta Pruning Genetic Algorithm
This Thesis Abstract may be cited as follows:
Ordering Functions Game Playing Game Trees Evaluation Function Minimax Algorithm Alpha-Beta Pruning Genetic Algorithm
Submission Details: Thesis Abstract submitted by David Captur from Malta on 28-Jul-2004 13:41.
Abstract has been viewed 3106 times (since 7 Mar 2010).
David Captur Contact Details: Email: David@Captur.net
Disclaimer
Great care has been taken to ensure that this information is correct, however ThesisAbstracts.com cannot accept responsibility for the contents of this Thesis abstract titled "Ordering Functions for Game Playing". This abstract has been submitted by David Captur on 28-Jul-2004 13:41. You may report a problem using the contact form.
© Copyright 2003 - 2024 of ThesisAbstracts.com and respective owners.