AI

So, we’ve finished and submitted the project that was done for the course in Artificial Intelligence. It was nice experience in Java, Project management, Team work, but a very little in the AI itself.

So it’s simple: checkers game. Simple minimax algorithm that works for minutes, and faster version of the algorithm with a-b pruning.

Work behind included GUI, rules implementation, heuristic functions, client-server architecture (Yes, it can be played by network, too :) and more. The most interesting of all is heuristic function. In combination with the algorithm it could be best described as “see on the situation, and tell me if it’s good”. In general, the function gave an estimation for every game state, board position. We went from simple to complicated heuristics. First one was just greedy and took in count only number of pieces on the board. When enhancing it, we’ve added references to pieces positions, absolute and relative, king’s runs, defending the specific places or more valuable pieces. I even followed this checkers strategy guide. Actually, I was trying to give the program instructions to perform as human player. And it behaved this way, and even more. Because of depth of algorithm(well, most of the people can’t foresee ten moves forward) it built us traps, won a lot of times and lost only couple of times.

But in the final testing, when we run heuristics functions to play one with another, we’ve seen unexpected result: the most complicated, almost human-thinking function could get only draw with the most simple one with same depth of thinking. So, with unlimited computation power, or, if P=NP proved, the game of checkers can become unbeatable versus computer opponent.