Jun 28, 2017 | Updated: 09:10 PM EDT

Microsoft Develops Algorithm to "Divide and Conquer" Ms. Pac-Man

Jun 17, 2017 02:25 PM EDT

Pac-Man
(Photo : Jemal Countess/Getty Images)

Researchers at Microsoft developed an artificial intelligence (AI) algorithm that can achieve the maximum score on Ms. Pac-Man, 999,999, four times greater than the highest human score.

After recovering from your wave of relief at the news that we've solved the Ms. Pac-Man problem, you might wonder why our greatest minds were spending their days chasing that particular goal. As it turns out, this accomplishment is significant because the "divide-and-conquer" method used can be applied to teach AI agents to complete other complex tasks.

Like Us on Facebook

The system, according to Microsoft's blog, was developed by a Maluuba, a deep learning startup company which was acquired by Microsoft earlier in the year. The divide-and-conquer method assigns individual AI agents different tasks but also allows them to work together collaboratively through a "top manager." A method called reinforcement learning was also programmed, whereby agents receive positive or negative responses for each task or action they complete, such as rewards (or getting eaten by a ghost, in the case of Ms. Pac-Man).

More specifically, the algorithm involves dividing the large problem of mastering the Ms. Pac-Man game into small pieces and accounting for every possibility of which direction the agents can move, depending if they are collecting pellets and fruit, or avoiding ghosts. "This idea of having them work on different pieces to achieve a common goal is very interesting," said Doina Precup, an associate professor of computer science at McGill University.

The algorithm, called "Hybrid Reward Architecture", uses more than 150 agents and also employed a manager agent, which took all suggestions from the individual agents and used them to decide where to move Ms. Pac-Man. A research manager at Maluuba and also the lead author of a paper on algorithm, submitted this week to Cornell University, said the best results were achieved when "each agent acted very egotistically...while the top agent decided how to use the information from each agent to make the best move for everyone," according to Microsoft's blog.

Potential applications include helping a company's sales team make predictions about which customers to target depending on factors such as which clients are up for contract renewal, which contracts are most valuable to the company, and if the customer is available at a particular day or time. The agents would represent each client similar to the agents in Ms. Pac-Man, and this process would allow sales executives (people) to focus all of their time on making sales and only targeting customers with the most potential.

 

 

 

©2017 ScienceTimes.com All rights reserved. Do not reproduce without permission. The window to the world of science times.