Skip to content

An AI for a modified Reversi version. The AI works with a game server that manages the game (https://github.com/marcluque/Reversi-Server)

License

Notifications You must be signed in to change notification settings

marcluque/Reversi-AI

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Reversi-AI

BCH compliance Build Status

SonarCloud
Quality Gate Status Coverage Code Smells Bugs Vulnerabilities Reliability Rating Security Rating Maintainability Rating Duplicated Lines (%) Lines of Code

License

This piece of software implements artificial intelligence that is based on informed search MiniMax algorithms and their extensions. The game played is Reversi. However, this version of Reversi is tweaked to be harder and not playable for humans. This poses a greater challenge for AI. The exact rules of the tweaked Reversi game are explained in the Game section. The AI communicates with a game master that is a server. The communication is done according to the protocol defined in the Protocol section.

Rules

The tweaked version of Reversi comprises several rules that make the game more difficult. These rules are defined in the following. Afterward, the protocol for the communication of the client and server is explained.

Game

Protocol

Algorithms

This version of Reversi allows for two or more players. A 2-player game allows for the commonly known MiniMax algorithm that assumes two players (Min and Max). However, an n-player scenario is more difficult than that. More players allow for more intricate situations than just one opponent. Just consider the idea of a coalition that your opponents could form.
The 2-Player Algorithms section below presents MiniMax and its extensions.
The Multi-Player Algorithms section presents various algorithms for multiplayer scenarios.

2-Player Algorithms

The 2-player algorithms use the classical scenario for the MiniMax algorithm and its extensions. The following algorithms are implemented in the Reversi-AI with the help of the book Artificial Intelligence: A Modern Approach.

MiniMax

An algorithm that performs an informed search. The search tries to find a path or move in a state space that minimizes the losing chances for itself and maximizes them for the opponent. It is important to note that this algorithm explores the whole state space.

Alpha-Beta

An extension of the MiniMax algorithm tries to reduce the searched state space by neglecting "uninteresting" paths. If at some point it is already clear that an explored path is more promising than an unexplored path, it is pruned.

Iterative Deepening

Iterative Deepening is a technique that may be applied regardless of the type of informed search. It is best described by thinking of an iterative exploration of the state space. The depth for the search is increased with each iteration, such that each iteration increases the search depth by 1. This also means that every iteration the search has to start from the root of the tree.

Move Sorting (aka Move Ordering)

The best case for Alpha-Beta search is the case where the best move is explored first. All other moves with worse scores may then be pruned. This can be achieved by sorting the nodes that will be explored.

Aspiration Windows

When using Iterative Deepening, the search space may be reduced by using so-called aspiration windows for the alpha and beta values. The values are usually retrieved from the previous iteration of the search. However, when picking a too narrow window, the best move might be missed.

Multi-Player Algorithms

The following algorithms try several approaches for multiplayer situations. The implementations do not rely on a book, like the standard MiniMax and its extensions. Instead, the algorithms are implemented with the help of their respective papers, all the papers are linked in their respective sections.

Max^N

The implementation is taken from the following paper An Algorithmic Solution Of N-Person Games. Note that the book Artificial Intelligence: A Modern Approach also provides an explanation of the idea for Max^N.

Paranoid Search

The implementation is taken from the following paper On Pruning Techniques for Multi-Player Games.

Best-Reply Search (aka BRS)

The implementation is taken from the following paper Best-Reply Search for Multi-Player Games.

Opponent-Pruning Paranoid Search (aka OPPS)

The implementation is taken from the following paper Opponent-Pruning Paranoid Search.

Heuristics

Server

This client is used to play Reversi with the server as a game master. The client communicates with the server by using the above-mentioned protocol. The game is played according to the above-defined rules.

Running it

License

Licensed under the BSD 2-Clause License - see the LICENSE file for details.