Introduction

Sankofa is the bird that looks back into the past in order to understand the future. Sankofa is an application for the analysis of Oware games.

Sankofa's goal is to enable players to recognize and to learn from their mistakes and to try alternative strategies.

The application is a stateless Web server. The user interface is presented as a Web page at http://localhost:10000 (user-configurable). An execution trace is displayed at the command line.

Functionalitiy:

• Sankofa is an analysis tool and not an automated opponent
• play moves on both sides and see their evaluations
• hover the cursor over GUI elements for hints
• access and display any previous position or any position from the proposed continuation
• use the GUI to create any legal position (add or take stones from the houses)

Build and Run

• you need Golang to build this application
• initialize and build: go mod init sankofa && go mod tidy && go install ./...
• optional: run ~/go/bin/retrograde to build a small end-game database
• run: ~/go/bin/sankofa
• open http://localhost:10000 in a Web browser with CSS and SVG capabilities
• sankofa -h or retrograde -h for help

Rules of the Oware game

We did our best to implement the abapa Oware rule set, as follows:

• The first player to capture 25 seeds instantly wins the game.
• Starved positions where no feeding (forced move) is possible end the game.
• A repeated position (the first cycle) ends the game.
• When the game ends, each player takes the seeds on her side of the board.
• Grand slams are allowed, but do not capture anything.

Algorithm

Sankofa provides a MiniMax evaluation of Oware positions featuring:

• negamax
• fail-soft α—β pruning
• transposition table (previous iteration) used for killer-move ordering
• quiescent search
• database with retrograde analysis or heuristic used for the α—β leaves
• iterative deepener
• parallel aspiration on discrete quartiles

Retrograde builds an end-game database:

• the database is built incrementally, level for level, starting with the empty board.
• strongly connected components (cycles) in lower layers discovered using Tarjan's algorithm.
• uses the simplified Awari rules which lead to slightly inaccurate Oware position evaluations
• does not filter out the unreachable positions but processes them like the rest
• iterates through a level until no new positions are evaluated. There still might be old positions that need revisiting: those are ignored.
• unreachable nodes not pruned but scored at a minimum performance cost.
• we recommend to evalute strongly connected components and the end-game up to level 12. A partial database of end-games is often enough.
• the complete databse (1.1TB) up to level 48 requires a very long processing time.

Legal

• Copyright ©2019 Carlo Monte
• License: MIT