Mastering Ouril with Neo4j

On a recent holiday to Cape Verde, I became obsessed with the local game Ouril.

Ouril is a strategy game originating in Africa (also known as Oware, Wari, Ayò amongst others) where the goal is to sew seeds counter-clockwise around a board of twelve holes 6 of each belonging to one of the two players. At the end of each move, if the last whole and any adjacent holes on the opposing players half of the board affected during a move have two or three seeds, these are then captured by that player. The aim of the game is to capture more seeds than your opponent.

One thing that struck me about the game is how easy it would be to replicate the gameplay in Neo4j.

 

Setting up the board

The Board
At the start of the game, each of the 12 holes contain 4 seeds.  As the seeds inside each of these holes are sewn counter-clockwise, I have linked each hole in ascending order with the final bucket linking back to the hole at position: 1.

// 1. Create the board
CREATE
(b1:Bucket:P1Bucket {position: 1})-[:SEWS_TO]->
(b2:Bucket:P1Bucket {position: 2})-[:SEWS_TO]->
(b3:Bucket:P1Bucket {position: 3})-[:SEWS_TO]->
(b4:Bucket:P1Bucket {position: 4})-[:SEWS_TO]->
(b5:Bucket:P1Bucket {position: 5})-[:SEWS_TO]->
(b6:Bucket:P1Bucket {position: 6})-[:SEWS_TO]->
(b7:Bucket:P2Bucket {position: 7})-[:SEWS_TO]->
(b8:Bucket:P2Bucket {position: 8})-[:SEWS_TO]->
(b9:Bucket:P2Bucket {position: 9})-[:SEWS_TO]->
(b10:Bucket:P2Bucket {position: 10})-[:SEWS_TO]->
(b11:Bucket:P2Bucket {position: 11})-[:SEWS_TO]->
(b12:Bucket:P2Bucket {position: 12})-[:SEWS_TO]->(b1)
RETURN *

Each hole starts with 4 seeds.  We should also create two players at this stage, give them a name and reset the number of seeds.

// 2. Reset the board
MATCH (h:Hole) set h.seeds = 4

MERGE (p1:Player {number: 1}) SET p1:NextPlayer, p1.name = 'Adam', p1.seeds = 0
MERGE (p2:Player {number: 2}) SET p2.name = 'Lauren', p2.seeds = 0

Now we have our board set up, it is time to play the first move.

Playing the First Move

When playing a move, a player will take all of the seeds from one of their holes and sew them into the adjacent holes.  Due to the SEWS_TO relationship, we can do this with a single Cypher query.

As we will end up to reusing this query, we can parameterise it so we only have to reset the parameter before making the same move.

:param position:2

Then we can make a move.

// 4. Play a move
MATCH (target:Hole {position: {position} })
with target.seeds as seeds, target
SET target.seeds = 0
with target, seeds
MATCH path = (target)-[:SEWS_TO*12]->(:Hole)

WITH seeds, nodes(path) as holes

UNWIND range(1, seeds) as index
WITH index, holes[index] as hole
SET hole.seeds = hole.seeds + 1

WITH head(collect(hole)) AS last
SET last:LastHole

When the move is played, the target Hole should first be emptied.  Then the query uses the RANGE function to create an array of numbers between 1 and the number of seeds currently inside the target hole.  These are then unwound using the UNWIND function to identify and increment each of the nodes within the path.  Finally, we take the last Hole node to be updated and give it a :LastHole label to use during the next step.

Capturing Seeds

Once a move has been played, all that is left is to collect up the captured seeds. ¬†If the last hole or any adjacent holes clockwise to the last hole have two or three seeds, these are captured and added to the player’s score. ¬†At the end of the game, the player with the most seeds wins. ¬†This query is slightly more complicated, but luckily Cypher can handle all of this for us.

First we need to find the last hole added to, and then find a path backwards using a variable length path.  By setting the lower bound to 0, this will include the starting node inside the path.  As there can only be a maximum of 6 holes, I have capped the path to 6 traversals.  Once we have the path, we need to ensure that the holes belong to the opponent and that there are two or three seeds in each.  We can do this using the all list predicate.

MATCH (first:LastHole)
WITH first, filter( label in labels(first) where label <> ‚ÄúLastHole‚ÄĚ) as labels
MATCH path = (first)<-[:SEWS_TO*0..6]-(last:Hole)
WHERE all( node in nodes(path) WHERE (node = first OR labels(node) = labels) AND node.seeds >= 2 AND node.seeds <= 3 )

Once we’ve found all paths, we need to take the path with single path the highest number of nodes. ¬†To find the total number of seeds captured in this round, we can use the REDUCE function to sum the number of seeds.

WITH labels, nodes(path) as holes, length(nodes(path)) as length, reduce(total = 0, n in nodes(path) | total + n.seeds) as captured
ORDER BY length DESC LIMIT 1

The captured seeds should then be added to the current players total.

MATCH (player:NextPlayer)
SET player.seeds = player.seeds + captured
REMOVE player:NextPlayer

The :NextPlayer label should then be removed from the current player and added to the other player ready for their turn.

WITH player, holes
MATCH (other:Player) WHERE other <> player
SET other:NextPlayer

Then we just need to remove the captured seeds from the holes.

WITH holes
UNWIND holes as hole
SET hole.seeds = 0

Here is the query in full:

// 5. Capture the seeds
//  Get the last hole
MATCH (first:LastHole)
// Get a list of the labels without the last hole
WITH first, filter( label in labels(first) where label <> ‚ÄúLastHole‚ÄĚ) as labels

// Get the last 6 adjacent holes
MATCH path = (first)<-[:SEWS_TO*0..6]-(last:Hole)

// Check that they have the same labels and have
WHERE all( node in nodes(path) WHERE (node = first OR labels(node) = labels) AND node.seeds >= 2 AND node.seeds <= 3 )

// Get the nodes within the path, number of nodes in the path and total captured seeds
WITH labels, nodes(path) as holes, length(nodes(path)) as length, reduce(total = 0, n in nodes(path) | total + n.seeds) as captured

// Only take the longest path
ORDER BY length DESC LIMIT 1

// Increment Captured and remove the NextPlayer label
MATCH (player:NextPlayer)
SET player.seeds = player.seeds + captured
REMOVE player:NextPlayer

// Set NextPlayer label on other player
WITH player, holes
MATCH (other:Player) WHERE other <> player
SET other:NextPlayer

// Remove the seeds from the Holes
WITH holes
UNWIND holes as hole
SET hole.seeds = 0

Transactions

As Neo4j is an ACID compliant database, we could batch these queries all up into a single transaction with any of the official drivers.  This would allow more advanced error checking and where applicable, the transaction could be rolled back if any player tried to break the rules.