# How to get ants to solve a chess problem

##### Jan 30, 2014 by Graham Kendall, The Conversation

Take a set of chess pieces and throw them all away except for one knight. Place the knight on any one of the 64 squares of a chess board.

Can you make 63 legal moves so that you visit every square on the chess board exactly once? As a reminder, a knight can move two squares in a straight line, followed by a ninety degree turn and a move of one further square. It might seem like a hard task, but this set of moves, called the knight's tour, can be achieved in too many ways to count.

If you are able to make the 63 moves and end up on a square from which you can move back to the original square with the 64th legal move, then this is known as a closed tour. Other tours are called open tours.

Mathematicians have pondered how many closed tours exist, and they have come up with an astonishing number: more than 26 trillion. There are so many more open tours that we do not know the exact number.

Both Philip Hingston and I were so captivated by the knight's tour problem that we wanted to find a different way to solve it. We found that motivation in nature – specifically in .

Ants use a certain pattern, or algorithm, to forage for food. This algorithm can be used to tackle many types of problems including the Travelling Salesman Problem and Vehicle Routing Problems. Philip and Graham wondered if they could use the ant colony optimisation algorithm to solve the knight's tour problem.

Here's how that algorithm works: a computer program is used to simulate a population of ants. These ants are assigned the task to find a solution to a problem. As each ant goes about their task they lay a pheromone trail – a smelly substance that ants use to communicate with each other. In the simulated algorithm, the most successful ants (the ones that solve the problem better), lay more pheromone than those that perform poorly.

We repeat this procedure many times (perhaps millions of times). Through repetitions, the pheromone trails on good solutions increase and they decrease on the poorer solutions due to evaporation, which is also programmed in the simulation algorithm.

In the simulation to solve the knight's tour problem, the ants could only make legal knight moves and were restricted to stay within the confines of the chess board. If an ant successfully completes a tour then we reinforce that tour by depositing more pheromone on that tour, when compared to a tour that was not a full tour.

Ants which attempt to find later tours are more likely to follow higher levels of pheromone. This means that they are more likely to make the same moves as previously successful ants.

There is a balance to be struck. If the ants follow the successful ants too rigidly, then the algorithm will quickly converge to a single tour. If we encourage the ants too much, not to follow the of previous ants, then than they will just act randomly. So it is a case of tuning the algorithm's parameters to try and find a good balance.

Using this algorithm, we were able to find almost half a million tours. This was a significant improvement over previous work, which was based on a genetic algorithm. These algorithms emulate Charles Darwin's principle of natural evolution – survival of the fittest. Fitter members (those that perform well on the problem at hand) of a simulated population survive and weaker members die off.

It is not easy to say why the ant algorithm performed so well, when compared to the genetic . Perhaps it was down to tuning the algorithmic parameters, or perhaps ants really do like to play chess!

The knight's tour problem was being worked on as far back as 840 AD. Little did those problem-solvers know that ants, albeit simulated ones, would be tackling the same puzzle more than 1,000 years in the future.

Explore further: Field study shows group decision making not always the best

Source: The Conversation

## Related Stories

#### Field study shows group decision making not always the best

Aug 01, 2013

(Phys.org) —A combined team of researchers from Arizona State University and Uppsala University in Sweden has found that collective decision making by ants doesn't always result in selecting the best option ...

#### Robot ants successfully mimic real colony behavior

Mar 28, 2013

Scientists have successfully replicated the behaviour of a colony of ants on the move with the use of miniature robots, as reported in the journal PLOS Computational Biology.

#### Swimming ants don shades to save their eyesight

Dec 17, 2013

Australia's unusual swimming ants take their own 'sunglasses' when they go to the beach – to shield their sensitive eyes from bright sunlight.

#### A search engine for social networks based on the behavior of ants

Jun 04, 2012

Research at Carlos III University in Madrid is developing an algorithm, based on ants' behavior when they are searching for food, which accelerates the search for relationships among elements that are present ...

#### Houston, we have ants: Mimicking how ants adjust to microgravity in space could lead to better robots, scientist says

Jan 20, 2014

Professor Deborah Gordon recently sent hundreds of ants to the orbiting International Space Station. By studying how the ants adjust their behavior to cope with near-zero gravity conditions, scientists could ...

#### Next generation of algorithms inspired by problem-solving ants

Dec 10, 2010

(PhysOrg.com) -- An ant colony is the last place you'd expect to find a maths whiz, but University of Sydney researchers have shown that the humble ant is capable of solving difficult mathematical problems.

## Recommended for you

#### Quantenna promises 10-gigabit Wi-Fi by next year

3 hours ago

(Phys.org) —Quantenna Communications has announced that it has plans for releasing a chipset that will be capable of delivering 10Gbps WiFi to/from routers, bridges and computers by sometime next year. ...

#### Alibaba steals Yahoo's thunder ahead of IPO

4 hours ago

If Yahoo appears back in favor, it can thank Alibaba, the Chinese Web giant in which it holds a big stake and which is set for a public stock offering.

#### New US-Spanish firm says targets rich mobile ad market

4 hours ago

Spanish telecoms firm Telefonica and US investment giant Blackstone launched a mobile telephone advertising venture on Wednesday, challenging internet giants such as Google and Facebook in a multi-billion-dollar ...

#### Environmentally compatible organic solar cells

4 hours ago

Environmentally compatible production methods for organic solar cells from novel materials are in the focus of "MatHero". The new project coordinated by Karlsruhe Institute of Technology (KIT) aims at making ...

#### Twitter rules out Turkey office amid tax row

4 hours ago

Social networking company Twitter on Wednesday rejected demands from the Turkish government to open an office there, following accusations of tax evasion and a two-week ban on the service.

#### Researchers propose network-based evaluation tool to assess relief operations feasibility

5 hours ago

The United Nations Office for Disaster Risk Reduction reported that disasters have affected around 2.9 billion people worldwide from 2000-2012— killing more than a million, and damaging around 1.7 trillion ...

##### 11791
not rated yet Jan 31, 2014
what a waste of time and money

## More news stories

#### Quantenna promises 10-gigabit Wi-Fi by next year

(Phys.org) —Quantenna Communications has announced that it has plans for releasing a chipset that will be capable of delivering 10Gbps WiFi to/from routers, bridges and computers by sometime next year. ...

#### Floating nuclear plants could ride out tsunamis

When an earthquake and tsunami struck the Fukushima Daiichi nuclear plant complex in 2011, neither the quake nor the inundation caused the ensuing contamination. Rather, it was the aftereffects—specifically, ...

#### Unlocking secrets of new solar material

(Phys.org) —A new solar material that has the same crystal structure as a mineral first found in the Ural Mountains in 1839 is shooting up the efficiency charts faster than almost anything researchers have ...

#### Patent talk: Google sharpens contact lens vision

(Phys.org) —A report from Patent Bolt brings us one step closer to what Google may have in mind in developing smart contact lenses. According to the discussion Google is interested in the concept of contact ...

#### Students turn \$250 wheelchair into geo-positioning robot

Talk about your Craigslist finds! A team of student employees at The University of Alabama in Huntsville's Systems Management and Production Center (SMAP) combined inspiration with innovation to make a \$250 ...

#### Scientists capture ultrafast snapshots of light-driven superconductivity

A new study pins down a major factor behind the appearance of superconductivity—the ability to conduct electricity with 100 percent efficiency—in a promising copper-oxide material.

#### How kids' brain structures grow as memory develops

Our ability to store memories improves during childhood, associated with structural changes in the hippocampus and its connections with prefrontal and parietal cortices. New research from UC Davis is exploring ...

#### Eavesdropping on brain cell chatter: Novel tools learn how astrocytes listen in on neurons

Everything we do—all of our movements, thoughts and feelings – are the result of neurons talking with one another, and recent studies have suggested that some of the conversations might not be all that ...

#### Study shows air temperature influenced African glacial movements

Changes in air temperature, not precipitation, drove the expansion and contraction of glaciers in Africa's Rwenzori Mountains at the height of the last ice age, according to a Dartmouth-led study funded by the National Geographic ...

#### Significant baseline levels of arsenic found in Ohio soils are due to natural processes

Geologic and soil processes are to blame for significant baseline levels of arsenic in soil throughout Ohio, according to a study published recently in the Journal of Environmental Quality.