How to teach Deep Blue to play poker and deliver groceries

Jan 09, 2014 by Graham Kendall, The Conversation
Beating computers is hard, and it’s going to get harder. Credit: George Widman/AP

Deep Blue gained world-wide attention in 1997 when it defeated the then chess world champion Garry Kasparov. But playing chess was all that Deep Blue could do. Ask it to play another game, even a simpler one, such as checkers, and Deep Blue would not even know how to play at beginner level. The same is also true of many other programs that can beat humans. Computers that can play poker cannot play bridge.

This type of tailored software development is also apparent in systems that we rely on every day. A system that produces nurse rosters may not be able to cope with producing shift patterns for a factory, even though they are both personnel scheduling systems. Programs that plan delivery routes of an online supermarket cannot usually be used to schedule appointments for servicing home appliances, even though they are both examples of a Vehicle Routing Problem.

In recent years there has been a growing interest in a field called hyper-heuristics, which aims to develop more general computer systems. The idea is to build systems that are not tailored for just one type of problem, but which can be reused for a wide range of problems.

The figure below shows a typical hyper-heuristic framework. Let's assume that this framework is being used to tackle a nurse rostering problem, where we have to assign nurses to work a certain number of shifts over a certain time period, say a week.

If we start with a possible shift pattern (perhaps from the previous week), we can do certain things to improve it. For example, we could move a nurse from one shift to another, we could swap two nurses or we could remove all nurses from a certain shift (say the Wednesday evening shift) and replace them with nurses that do not meet their contractual arrangements, just to give a few examples. These changes to the shift pattern are usually called heuristics.

How to teach Deep Blue to play poker and deliver groceries
Royal Flush Credit: Images of Money

The important thing is that we have a number of these low-level heuristics that we can use to improve the current roster. All these heuristics are placed in the bottom of the framework. We now choose one of these heuristics and execute it (for instance, swap one nurse with another). We repeat the process of choosing and executing a heuristic over and over again, in the hope that we will gradually get a better roster. The quality of the roster is measured by the evaluation function, which checks the outcome.

The key to this approach is to decide in which order to execute the low-level heuristics. This is where the top part of the framework comes into play. The hyper-heuristic looks at the state of the system and decides which heuristic to execute. This is repeated until we decide to stop (maybe after a certain period of time, or after we have executed the low-level heuristics a certain number of times).

What makes a hyper-heuristic different, from other heuristic-selecting algorithms, is the "domain barrier". This stops the higher level hyper-heuristic knowing anything about the problem it is trying to solve. The hyper-heuristic only has access to data that is common to any problem. This includes how long each low-level heuristic took to execute, the track record of each low-level heuristic (how well it has performed), how pairs of low-level heuristics work with each other, to give just a few examples.

How to teach Deep Blue to play poker and deliver groceries
Hyper-heuristic framework Credit: Kendall

The benefit of the domain barrier is that we can replace the low-level heuristics, and the evaluation function, with another type of problem. As the hyper-heuristic has no knowledge of the problem being tackled we would hope that we can use the same higher level algorithm to tackle this new problem. And, indeed, this has been shown to be the case in a large number of scientific problems.

The challenge in hyper-heuristics lies in developing a robust high-level strategy that is able to adapt to as many different problems as possible. We are still some way off having a hyper-heuristic that is able to produce nurse rosters, plan deliveries and play poker, but, given the pace of progress in this field, we hope to achieve this goal in the not-too-distant future.

Explore further: German supercomputer is a world champion in saving engergy

add to favorites email to friend print save as pdf

Related Stories

When the brain decides

Jul 18, 2011

Every day we have to make decisions that involve evaluating or choosing between options, often without much information to go on. So how we do it? How do we prevent analysis paralysis?

Malware bites

Aug 15, 2013

Antivirus software running on your computer has one big weak point - if a new virus is released before the antivirus provider knows about it or before the next scheduled antivirus software update, your system can be infected. ...

Computer solution to delivery problem

Oct 18, 2007

With the gift-giving season almost upon us and increasing concerns about the environmental effects of all those deliveries and pickups, it is timely that researchers should turn their attention to the so-called Traveling ...

Specialization builds trust among web users

Nov 05, 2010

(PhysOrg.com) -- If you name it, they will use it, according to a team of international researchers who investigated how people perceive the trustworthiness of online technology. In an experiment, participants said they trusted ...

Recommended for you

GoGlove wearable aims to control life's soundtracks

44 minutes ago

Technology creatives are seeing the key attraction in wearables as being in solutions that save the user from fumbling around with the phone to make app adjustments or changes, or from repeatedly taking it ...

Amazon cuts Fire phone price to ignite sales

1 hour ago

Amazon on Wednesday slashed the price of Fire mobile phones that stalled after launch early this year, becoming a drag on the US online retail titan's bottom line.

Thanksgiving travel woes? There's an app for that

1 hour ago

Traveling by plane, train or automobile can be a headache. Mixing in Thanksgiving can make it a throbbing migraine. Technology provides some pain relief in the form of apps to let you know which roads are ...

US agency threatens to act against air bag maker

2 hours ago

A dispute between U.S. safety regulators and air bag maker Takata Corp. escalated Wednesday when the government threatened fines and legal action if the company fails to admit that driver's side air bag inflators ...

Netflix sues Yahoo CIO for alleged kickbacks

2 hours ago

Netflix is suing a former company vice president who is now chief information officer at Yahoo, accusing him of receiving money from vendors he hired to work with the video streaming company.

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.