Mancala

I’ve been working for a while on a simple handheld game machine. It made its official debut at The Farm this summer, so I thought I’d post it here and on the gallery.

Motivation

Last summer at our annual family gathering, I learned the African game Mancala from my wife’s cousin Danielle. Actually, there are many variations that go by that name, so I learned the one she plays. The basic game is described on Wikipedia, but I don’t see a quick link to the rules we’re using.

I had fun exploring strategies for the game, and ended up proposing three heuristics that I thought could play a pretty good game by themselves, applied mechanically. I wanted to automate them so I could play against them, but never got around to writing the program.

A while later, I pulled out a two-line by 16-character LCD display that I had bought on impulse, and felt like using it for something. And I also wanted to try using the PIC18F series of microcontrollers; I’d used the PIC16F series before, but the 18s are a step up in features and architecture and I wanted to explore them.

It seemed like a fast fun project, and I got the basic form factor up and running in a weekend, and some simple playable UI code in another evening.

As this was a productive learning experience and a sort of research project on handheld UI implementation, I’ll describe some of the interesting bits here. I’ve also posted some specific comments on the images in the gallery.

Product design

The overall product design (image) required these elements:

  • Fit comfortably in the hands
  • Use batteries efficiently
  • Display the game state clearly in varying light levels
  • Allow for selection of items from a list
  • Provide good visual and audible feedback.

By far, the power supply was the most demanding requirement, so I’ll start there.

Power supply

(see the schematic)

Most of the power used here is in the backlight for the LCD, which requires 5V and about 80 mA while running. (In this particular model, the backlight can’t be turned off.)

For simplicity, I first used a 9V battery with a 5V LDO linear voltage regulator. This was OK, but the battery discharged a bit faster than I liked, and it’s hard to find rechargeable 9V batteries and chargers. NiMH AAs are far more common, and have a higher energy density. And I had them around.

But, four AAs are fairly bulky, and two of them only provide 2-2.4 V. So, I replaced the LDO with a step-up switcher, based on the Microchip TC110 chip. Since this was probably going to be a one-off project, I chose the switcher controller largely on the basis of what would not require getting a PCB made. Almost all switcher chips are surface-mount, including the TC110, but due to its specific pinout, I could solder it to a piece of perf board in a usable way and plug it into a breadboard.

The power supply schematic is taken directly from the data sheet. It uses the “bootstrapped” mode of operation, which may be slightly less efficient but works conveniently with my perf board adapter.

I measured the efficiency of the supply at around 80% including the power switch, which is a substantial improvement over the linear regulator.

Power switch

I wanted a “soft” power switch with the following characteristics:

  • User control: Push on, push off
  • Microcontroller control: save state before turn-off, and automatically turn off after a set period of inactivity
  • Negligible current draw while off
  • Minimal power usage while on.
  • Cheap and small.

I ended up spending a lot of time on this, and I’m happy with the solution.

Q1, a PNP transistor, is the main switching element. I experimented with MOSFETs, but the minimum 2V input requirement just didn’t supply enough gate drive for the ones I could find easily (and that weren’t too expensive).

When S1, the power button, is pressed, it pulls Q1’s base down to ground, turning on the switch. The combination of R1 and R4 limit the gate current while providing enough to pass 200 mA, the target Ic through Q1 (derived experimentally).

Once the switcher has started up and the microcontroller (IC1) is running, it asserts its RA3 pin to turn on Q2, which continues to turn on Q1 even after the button is released.

IC1 can sense the state of S1 through its AN1 A/D converter. R1 and R4 form a divider that show 0.2 - 0.5 V when the button is pressed; when it’s released, R1 pulls it down to ground. So, an 8-bit A/D value over 9 indicates a pressed button, and it will be nearly 0 when it’s released.

When the button is pressed again to request turn-off, IC1 discovers the button press, saves game state, waits for the button to be released, and then de-asserts RA3 to turn off Q2, and then Q1.

The switch as a whole uses around 20-50 mW while running, which is acceptable. It uses up to 100 mW momentarily while the button is pressed.

Battery sensing

IC1 can sense the battery’s output voltage using the AN0 A/D channel, and comparing it to its own supply reference. R6 is simply for input protection.

I’ve tried to estimate the percentage of remaining battery life based on NiMH discharge curves from the Web, but it needs tuning to work well with the specific batteries I’m using. Since that seems like a lot of work that will be useless whenever I switch to a different type or set of batteries, I may just go back to showing the battery’s output voltage on a scale from 2 to 3V.

When IC1 senses that the battery output has fallen to 2V, it saves state and turns off, to prevent battery damage.

Support software

The software is written in BoostC, using a slightly hacked version of their LCD library code, plus some reusable modules for LCD-based UI and sound. The source code is posted below.

Game play

The heuristics the computer uses to play are very simple. They use these definitions:

  • Cups are numbered clockwise, starting with the cup nearest the owner’s store as #1.
  • A full cup has the same number of seeds in it as its cup number.
  • An overfull cup has more than its cup number.
  • A saturated cup has 7 more than its cup number (or more).

And the rules are:

  1. Play the lowest-numbered full or saturated cup, if available.
  2. Otherwise, play the lowest-numbered overfull cup, if available.
  3. Otherwise, play the highest-numbered nonempty cup.

The C code for this is:

// First pass: Full and saturated cups.
for (currentCup = 1; currentCup <= NUM_CUPS; currentCup++)
    if ((currentCups[currentCup] == currentCup) || (currentCups[currentCup] >= 7 + currentCup))
        return;

// Second pass: Overfull cups.
for (currentCup = 1; currentCup <= NUM_CUPS; currentCup++)
    if (currentCups[currentCup] > currentCup)
        return;

// Third pass: Move the highest nonempty cup.
for (currentCup = NUM_CUPS; currentCup <= NUM_CUPS; --currentCup)
    if (currentCups[currentCup])
        return;

The first player has a substantial advantage, so I can still reliably beat the computer (using these rules myself) if I go first. I have also beaten it when it goes first, but I have a hard time replicating that. Danielle beat it too, after a few days, but so far no one else has!

The addition of a game tree generator with at least several moves of lookahead would probably make an unbeatable game; combinatorial game theory also apparently works well with this class of game and would be an option.

Future fun

There are lots of improvements to be made:

  • Abstract out the Mancala-specific code to make a generic device/OS for running simple games.
  • Improve game play.
  • Support more Mancala variants.
  • Add undo, statistics, and save/restore of individual games.
  • Make a more permanent board (though the breadboard has held up well so far).
AttachmentSize
Source code46.62 KB

Comments

Nice...

can i have the source code pls??

thanks in advance

Sure.

I’ll get it together this weekend and post it here. Are you interested in building the project as is, or just the algorithms, or…?

Source code added

I’ve just added the source code above, as several people have asked for it. Enjoy.