|
|
|
Game Artificial Intelligence | Machine Learning
Project 1: Game Artificial Intelligence
Overview
One of the most important aspects of a computer game is the intelligence of its opponents. The quality of an artificial intelligence is heavily dependent on the amount of available processing power. One of the most important algorithms of that area is A*. The A* algorithm finds the best path between the current location of a computer player and its destination. In current first-person shooters, A* accounts for approximately 70% of the total processing time.
This project might be interesting for you if you enjoy computer games and would like to know more about their inner mechanisms.
Details
The idea of A* is simple: On a map that has been discretized e.g. into squares, spread out from the origin until the destination field (with the best path to it) has been found. The movement cost to the next farther field F is simply the movement cost to the current field G plus the cost to move from G to F which depends on the terrain. A* constructs longer and longer paths in that fashion until the correct solution has been found.
First-person shooters like Half-Life 2 depend heavily on the A* algorithm.
For this course the algorithm is to be parallelized in two ways: On a coarse level, A* can be used to find the paths for different computer players at the same time. This parallelization is trivial because the paths are completely independent from each other, but it'll give you results quickly. The second step is a fine-granular parallelization where multiple CPUs compute a single path. The fine-granular parallelization will require some experimentation and is your chance to demonstrate your proficiency.
References
Project 2: Machine Learning
Overview
More and more computers are used to analyze large amounts of data. A common problem is to recognize a pattern known from previous analysis in new data. Examples are the recognition of a tumor on brain scan images or the analysis of personal data for marketing purposes. One of the most frequently used approaches for these kinds of problems are Support Vector Machines (SVMs). An SVM first learns what is a correct answer from known solutions and then tries to apply its knowledge to new data.
This project might be interesting for you if you enjoy math problems.
Details
An SVM considers all input data as p dimensional vectors. It tries to find a hyperplane of dimension p-1 which separates the data points such that the margins between the two classes are maximal. An new point can then easily be classified simply by checking on which side of the hyperplane it is located.
SVMs try to find hyperplanes with maximum margins to both classes.
For this course two algorithms should be parallelized: The classification algorithm (i.e. the plane lookup) is trivial to parallelize because each lookup is independent from all other data points. It is likely to hit memory bandwidth limitations soon. The other algorithm is the one used during the learning phase (i.e. the construction of the hyperplane) and is computationally more expensive. It is more difficult to parallelize because of dependencies but will allow you to show how well you can parallelize programs.
References