Game on: How chess computers became logistics masterminds

August 21, 2015, 6:56 PM UTC
4th Asian Indoor & Martial Arts Games: Day 3
INCHEON, SOUTH KOREA - JULY 01: A player competes in the Chess, Men's Classical round 2 during day three of the 4th Asian Indoor & Martial Arts Games at Yonsei International Campus on July 1, 2013 in Incheon, South Korea. (Photo by Chung Sung-Jun/Getty Images)
Photograph by Chung Sung-Jun — Getty Images

When Victor Allis helped found the software firm Quintiq in 1997, not many people shared his belief that artificial intelligence could plan a company’s production and distribution better than humans. Twenty years later, Quintiq is a global company with nearly 1,000 employeesand it’s just one part of the $10 billion, fast-growing supply-chain optimization sector.

That’s because the mix of raw materials, factories, markets, and shipping routes that get products to your doorstep has become so complex that it’s outpacing humans’ ability to see the big picture. Software like Quintiq’s has become an essential, if rarely-seen, part of our globalized economy, helping big enterprises like Wal-Mart shed as much as 15% of their production and fulfillment costs by putting everything in exactly the right place, at the right time.

But Allis didn’t grow up dreaming of trucks and factories. That just turned out to be the most powerful application of his lifelong passion for games and puzzlesor, more precisely, for computers smart enough to solve them.

His approach to games might, to an average human, seem a bit dry. In high school, Allis competed in international math competitions, “because I felt mathematical puzzles were fun.” In college, he created computer programs to play games for him —because, really, who has the time? And as a Master’s student, he took fun-ruining to the next level when he proved that Connect Four can be won 100% of the time if the first player follows a strict procedural strategy.

Cue plastic game pieces clattering into trashcans worldwide.

After earning his PhD in artificial intelligence, Allis made a brief stop in academia, ready to spend his life exploring games. But within two years, he’d jumped into the private sector to tackle bigger problems.

“Very quickly,” says Allis, “I told them, if you want to use artificial intelligence in business, you should use it to do planning.”

Researchers have used games like chess and checkers as a testing ground for artificial intelligence for more than half a century, exploring two general approaches. One tries to teach computers to reason like humans. The other is search-based, giving computers parameters and goals, but relying on their ability to simulate a vast number of scenarios, then choose the best.

For the most part, computers are better at thinking by brute force. When IBM’s Deep Blue defeated chess grandmaster Gary Casparov in 1997, the computer didn’t have any great insight into strategy. But it could look much farther into the future, much faster, creating ‘decision trees’ outlining every possible outcome of every possible move.

There are obvious parallels with logistics. Company assets are like game pieces, and must be moved according to a complex set of real-world ‘rules,’ encompassing everything from material costs to labor laws to speed limits. In the planning game, you ‘win’ by operating as efficiently as possible.

But companies and logistics networks are even more complex than games. Even something as minor as a truck’s route from a distribution center to a dozen stores must take into account many times more variables than a chess opening. Add in the factories that produce the products, the mines that supply the factories, and the trains and ships that connect them, and a company’s supply chain can have as many possible configurations as there are atoms in the universe.

Humans, with their imprecise but flexible brains, tackle the problem with generalizations, common sense, and educated guesses. In planning, that might mean rules of thumb like always starting a truck’s daily route by sending it northeast. But planners can’t always back these habits up analytically, which makes them useless for computers.

“You don’t hear very good underlying reasons,” Allis says. “We call this ‘bad knowledge’.”

Instead, just like modern chess programs, planning algorithms simulate possible scenarios and measure them for cost, speed, or other metrics. Establishing those metrics is likely to remain a human task for the foreseeable future. A computer can’t decide, say, whether certain customers should get priority over others, any more than Deep Blue was able to deduce on its own that capturing the king is the goal of a chess game.

But even today, many planning problems are so complex they can’t be solved by raw computation. Allis’ Connect Four solution was accomplished using shortcuts to narrow down the trillions of possible positions on even that game’s simple board, and similar methods now help Quintiq make planning decisions.

In the 1980s, for instance, chess programmers hampered by limited computing power realized they could get faster results by simulating just the first few moves of a large number of options, then diving deeper into the ones that looked most promising. A logistics network changes constantlynew shipments come in, trucks break downand fully evaluating every possible way to adjust is computationally impossible. So planning algorithms, like chess programs, simulate limited versions of possible structures before diving deeper into a few of the best. The method is known as iterative deepening.

A final lesson from games may be the most counterintuitive. The most challenging game for an AI isn’t chess, but the even more complex Go20 years after Deep Blue, Go AIs still can’t defeat top-level human players. But advances are being made by relying on randomnesswhat is called, in one of computer science’s rare eloquent naming conventions, the Monte Carlo technique.

The same random-iteration idea is now being used in planning. Working from an initial plan, shipments are randomly pulled out, reshuffled, and tested to find hidden efficiencies.

The benefit comes from defying conventional thinking. “If you were to use deterministic methods,” explains Allis, “You miss all kinds of turns and choices that just looked bad for a moment, but ended up being really good.”

Which means that a computer isn’t just faster and more precise than a human plannerit’s more innovative.

Sign up for Data Sheet, Fortune’s daily newsletter about the business of technology.

Read More

Artificial IntelligenceCryptocurrencyMetaverseCybersecurityTech Forward