Desarrollo de un motor de ajedrez: Algoritmos y heurísticas para la reducción del espacio de búsqueda

Abstract

El objetivo de este trabajo fue desarrollar un motor de ajedrez, denominado Buhochess, el cual sirviera como una base para el estudio e implementación de algunos de los métodos de búsqueda más importantes en juegos deterministas de suma cero. Si bien, para la implementación del motor de ajedrez Buhochess fue necesario implementar los tres módulos que contiene todo motor de ajedrez, el trabajo se centra principalmente en el desarrollo y análisis de los métodos de búsquedas. Entre las metas definidas para alcanzar el objetivo general se cuentan el desarrollo de un motor de ajedrez, desarrollado desde cero, en el cual se implementaran todos los métodos y algoritmos que utiliza un motor de ajedrez moderno. Otra de las metas fue el estudio, análisis e implementación de los principales algoritmos de búsqueda para juegos deterministas de suma cero. Otra meta del trabajo fue el estudio e implementación de algoritmos de búsqueda avanzados y de heurísticas que permitieran realizar una búsqueda con una profundidad de, al menos, 10, dentro de las restricciones de tiempo reglamentarias. El desarrollo no se consideró completo hasta que el motor fue capaz de jugar una partida completa de ajedrez a un nivel «decente» contra un jugador humano con todas las reglas del mismo, asi como cualquier restricción de tiempo. El término «decente» es subjetivo, por lo que se consideró que el motor Buhochess no se consideraría terminado hasta que nunca perdiera al jugar contra un jugador humano de nivel intermedio. Esto se verificó al oponer a Buhochess con los jugadores pertenecientes al club de ajedrez de la Unison. Igualmente, se consideró su nivel de juego como «decente», al ser capaz de vencer sistemáticamente a otros motores de ajedrez con un poder de juego medio, como el Big Bang Chess de Apple Inc.