Search

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.

Equilibria computation is of great importance to many areas such as economics, control theory, and recently computer science. We focus on the computation of Nash equilibria in two-player general-sum normal form games, also called bimatrix games. One efficient method to compute these equilibria is based on enumerating the vertices of the best response polyhedrons of the two players and checking the equilibrium conditions for every pair of vertices. We design and implement a parallel algorithm for computing Nash equilibria in bimatrix games based on vertex enumeration. We analyze the performance of the proposed algorithm by performing extensive experiments on a grid computing system.