Connect Four Game

Links:

The motive behind the coursework is to investigate and learn some adversarial search techniques used in the field of AI in solving games and puzzles. The techniques are then applied to the connect-four game [1].

The method used is mainly minimax search along with other minor strategies to complement the minimax for this game specifically.

The key results are, while search tree algorithms (for example minimax) may come in handy in smaller world games/puzzles, they are computationally expensive. Other algorithms try to overcome the shortcoming of the minimax, for example alpha-beta pruning, negamax [2] (negascout [3], [4] as a particular example) or SSS* [5]. But none of them can be used alone to develop a winning strategy for this game. Search tree algorithms are not magic and they definitely need other strategies to complement them. These complimentary strategies are game-specific and cannot be generalized to other games.

This project was built as a coursework for the ‘Artificial Intelligence’, 1st semester in MSc Artificial Intelligence at the University of Southampton.

Advertisements

Blocks World Puzzle

Links:

The report presents the work done to investigate search tree algorithms used to solve puzzles and games. Then the algorithms are applied to solve the Blocks-World puzzle [1].

The method used is building a search tree and exploring it to find the solution. The algorithms used are mixture of blind search and heuristic search. For the blind search, the algorithms used are depth-first, breadth-first and iterative deepening. Different ways of calculating the heuristic values are discussed but only one was used in the implementation.

The key results are, despite the game may look trivial at the first glance; blind search techniques were not able to find the solution in a reasonable time. On the other hand, involving heuristic estimates in the search tree resulted in notable outcomes. A solution for the puzzle was found. Nevertheless, the blind search algorithms were able to find the solution when reducing the puzzle conditions (reduce world size or the number of blocks to be moved).

This project was built as a coursework for the ‘Artificial Intelligence’, 1st semester in MSc Artificial Intelligence at the University of Southampton.

Scene Recognition

Links: github

The motive behind the project is to investigate techniques used in image recognition, specifically, for the problem domain of scene recognition.

The method used is building a prediction model using a training date set. We apply several feature extraction algorithms to get useful features from the training dataset, then applying classification algorithms to predict the class of the test dataset. A key to generalise the building model is subjecting it to validation. The training data-set was split into different portions used to train and validate the model.

The key result is, with simple feature extraction and classifications, prediction success rates were very limited, not higher than 20~25%. Applying more sophisticated algorithms yield in significantly higher prediction success rates to 60~65%.

The conclusion is the kind-ness of the problem space we are dealing with in the report, it is very challenging to get success ratios around 80~85%. Such ratios requires spatial feature extraction, adding additional complementary features and applying non-linear classification methods.

This project was built as a coursework for the ‘Computer Vision’, 1st semester in MSc Artificial Intelligence at the University of Southampton.

Post Traumatic Agent

The motive behind the report is to present the approach used to develop Post-Traumatic, an intelligent agent that competed in Trading Agent Competition (TAC) [1] at the University of Southampton.

The methods used are different according to the type of the auction the agent is competing in. For the hotel auction, we used 1st-order curve fitting to predict the highest price at the end of the auction window. Then we add a safety-margin to ensure the winning of the bid. For the flight auction, we used a varying n-order curve-fitting to predict the rise and decline of the prices over the remaining time. The order (n) varies according to the elapsed time of the auction. For the entertainment auction, we used an ever-increasing bid price and an ever-decreasing ask price. In spite of the simplicity of this strategy, we were able to secure some profit added to the total utility.

The key results are as the following. In predicting flight prices, the agent was able to make profit when comparing the buying-prices with the final closing prices. For the hotel auction, our strategy to compete fiercely on the hotel tickets succeeded in securing more than 82% of the allocations according to the client preferences. But the trade-off was more hurting than rewarding. The strategy led to significantly reducing the final utility, because of rapid increase in the prices at the end of the auction window.

This project was built as a coursework for the ‘Intelligent Agents’, 1st semester in MSc Artificial Intelligence at the University of Southampton.