1. Computing

Bots fighting Weekly playing Linkage

By

An ongoing challenge is a programming contest where you submit a computer program (called a Bot) and it fights against other bots each week. The better your bot is at winning, the higher it ranks on a ladder. This carries on for several months and you can submit an updated version or newer Bot at any time.

Note:Slight Change of format to input.txt on July 14th 2012

.

The board game that the next ongoing challenge to be based on is called Linkage and was created by Ethan Larson. You can see the rules and example play on IgGamecenter. and more details on BoardGameGeek.com.

Played on a 7 x7 board with the center square blocked out (it's unplayable), there are 24 dominoes that are 2 x 1 in size. Each domino is in one of four colors (Red, Blue, Green, Yellow) and there are six in each color making 24 in total.

The game has two players called More and Fewer. More always goes first. He/she plays any color domino anywhere on the board in any two contiguous empty spaces (except the center square) in a vertical or horizontal orientation.

Then it's Fewer's turn and that player does the same but also must not place the the domino so it's touching (horizontally or vertically) the last piece played by More.

The two examples below show the board after More has played his first piece M (Each is a different game). The x squares (and M, X) are the only places where Fewer can't place a domino.

  ABCDEFG
1 .......
2 .x.....
3 xMx....
4 xMxX...
5 .x.....
6 .......
7 .......

  ABCDEFG
1 .......
2 .......
3 .xx....
4 xMMX...
5 .xx....
6 .......
7 .......

Play continues with these same placement rules. No domino can be played on an existing domino or touching your opponent's last played domino until all 24 dominoes are played or there are no valid moves.

Skipping Turns

It's possible to have a position where the next player can't play the domino because he only available moves would touch the previous player's domino. In this case you can skip the move.

Then the number of distinct groups (a group is one or more dominoes of the same color that are touching horizontally or vertically) is counted. If there are less than 12 groups then Fewer wins. If there are 12 or more groups then More wins.

Running this as an Ongoing contest

I think the fairest way is for your Bot to play an opponent several games so both bots can play as More and Fewer. Each week that the contest is running your Bot will play 10 games against the Bot above you in the ladder and ten games against the Bot beneath you. Half of these games will be as the More player and half as Fewer,

Your rating will be a value = 100* Number of games won/ Number of games played so it will be a value between 0 and 100. I'll split this figure into More and Fewer.

Technical Details for bots

To keep this as simple as possible, every bot will be an exe. You submit the code and I'll compile it (no binaries please). My game runner program will manage each game and run your Bot.

Your Bot

This is a simple exe. When it runs it should check to see if there is an input parameter.

  1. If there is any input parameter it should output id information (below) on one line.
  2. If there is no input parameter, it should play a turn.

The id information is needed so the game runner ( a piece of software that plays all the games, and runs the Bots) can capture each Bot's details. Typically these details would include:

Bot Name, Bot Author (Country and age are optional), Date of creation and Bot Version.

For example.

Cplus. David Bolton, UK, 53, August 12,2012, V1.0

Call your bot what you like, but nothing rude please.

Playing a Turn

Here is what your bot must do:

  1. Read the file input.txt. This will be in the same location as your bot.
  2. Work out which domino to play and where.
  3. Output your move to the file order.txt in the same location as your Bot.

Input File Format

This consists of a single line with a char (M or F) then four digits followed by a 7 x 7 char grid, 8 lines in total.

The char is M or F showing it's the first player (also known as More) or the second player (aka Fewer). The four digits are the counts of the remaining dominos in the order RBGY (Red Blue Green Yellow). So F5632 is Fewer player to play with five red, six blue, three green and two yellow. Obviously once any domino count reaches zero, you can no longer play that color domino.

The 7 x 7 grid of chars is the board. The chars in this file are made up of these:

  • RBGY - Played domino characters.
  • X - Center square that is unplayable.
  • x - the unplayable squares around your opponent's last move.
  • . - an empty square.

The starting input.txt looks like this to the More Bot:

M6666
.......
.......
.......
...X...
.......
.......
.......

Your bot should work out it's order in 3 parts:

  1. Colour char of domino to play: RBGY
  2. Column and row of first coordinate of the square X1Y1.
  3. Column and row of second coordinate of the square X2Y2.

If it's impossible to place a domino, output the word Skip instead.

Remember the domino occupies two squares so X1Y1 and X2Y2 should be adjacent horizontally or vertically.

Each order is five characters long. CX1Y1X2Y2 where X is the column with letters A-G and Y is the row with chars 1-7. C is the color RGBY. So these are valid examples of orders:

YA1A2
GE4F4

The first one puts a Yellow domino at A1A2. The second a green one at E4F4. This assumes that those locations are empty of course.

After each game is over I'll have all the orders for each of the games appended into a text file that you can view/download post match.

Submission Rules

Please submit Bots as a project (if using Visual Studio/Express) or just as one or more files. I'll allocate a number and your Bot will use that number thereafter. I'll rename it to an imaginative name like bot19.c etc. If you could rename your files/project so it has that number it would be a great help!

Bots must take five seconds maximum to work out their move. Any longer and it's disqualified and loses all of its games that week.

You can use one temporary file for caching data between turns if you wish. It must be in the same folder as your exe.

I'll create skeleton bots in a few days and update this but you can start submitting bots now and as soon as I have two, the battles will commence.

To encourage innovation I will post a link to the source code (zipped up) of the top Bot, four weeks after it gets to the top of the ladder.

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. Projects
  5. Ongoing Challenges
  6. The Next Ongoing Challenge

©2014 About.com. All rights reserved.