This game, with a an ancestry that goes back at least to Roman times is known by a number of different names in England - Nine Mens Morris or Morelles or or Merrills or Merels or Mill or just plain Morris.
There seem to be two forms of the ancient game of Three Mens Morris; one with diagonals and one without. The diagonals form is effectively the same game as Tic-Tac-Toe or Noughts and Crosses today. It seems surprising that the Romans could be bothered to chisel out a board for such a trivial and relatively uninteresting game and there is a theory that these boards were not board games at all but targets for a game of skill involving coins or stones being tossed in an effort to get them to finish within the etched lines.
According to Thomas Hyde (1908), the Chinese also played the game c. 500BC.
A couple of centuries on, Ovid mentions the game in "Ars Amatoria". Roman boards were usually made of wood or tone although the rich occasionally had boards made of more exotic materials (Trimalchio had one of turpentine-tree and Martial speaks of an ivory board).
The game was widely played in England in AD1300 and visitors to the cathedrals of Norwich, Canterbury, Gloucester, Salisbury and Westminster Abbey can see boards cut into the cloister seats by monks.
Mill boards have been found in Ceylon which were carved during the reign of Mahadithika Maha-Naga (9-21AD). European boards have been found in such places as the first city of Troy, within a Bronze age burial site in Ireland and at the Acropolis in Athens. The game reached its peak popularity in Europe during the Fourteenth Century.
As an old English game, it used to be played with black and white pebbles on a board marked out with a trowel dug into village greens as well as in Taverns on boards marked with chalk on a table. Shakespeare mentioned it in "A Midsummer Night's Dream" Act 2, Scene 1 - "The Nine Mens Morris is filled up with mud" which is what must have happened to the boards marked in the village green when it rained!
Three and Nine Mens Morris boards have been found cut into the temple at Kurna, Egypt (~1440 BC) causing many media articles to blithely claim that the game goes back to the ancient Egyptians. "Graffiti boards" like these cause much confusion for those wishing to establish provenance because they are usually impossible to date. Often someone asserts that the boards were carved around the same time as the temple but normally it's impossible to prove that they weren't carved just 40 years ago and so their existence generally prove nothing.
There is a version of Nine Mens Morris known as Morabaraba or Umlabalaba, which is still popular and played to competitive level in Botswana and South Africa.
It is played on a board with diagonals but the rules are virtually identical to Nine Mens Morris aside from that.
Masters Traditional Games has a range of nice wooden Nine Mens Morris games.
Masters Traditional Games publishes Nine Mens Morris rules, too.
Merrills research from Kansas