Akihiro Kishimoto is a research staff member at IBM Research – Ireland working on a range of projects in artificial intelligence, parallel and distributed computing and search. His interest in these technical fields grew from his passion for board games. And while a student at the University of Tokyo, he and three of his fellow classmates designed ISshogi, a program to play the incredibly complex (and ancient) Japanese board game, Shogi. ISshogi won the World Computer Shogi Championships four times from 1997-2005.
While studying AI at the University of Alberta, Akihiro was a member of the GAMES group (Game-playing, Analytical methods, Minimax search and Empirical Studies) in the Department of Computing Science, and worked with Jonathan Schaeffer and others to solve Checkers. And they did. Using search algorithms and an end-game database. It’s all explained in their Science article Checkers is Solved, which was later named a Breakthrough of the Year in 2007. He also worked with Martin Müller on Graph History Interaction, Proof-number search and Computer Go.
Search plays a vital role in solving many computer science problems, from theorem-proving, to game-playing systems. Akihiro is now applying his understanding of search and AI in gaming to find chemical reaction pathways for chemists.
In his own words: Akihiro on drug discovery using artificial intelligence & gaming
When chemists design a new drug, they not only need to design a target molecule or compound, but they also need to look at the reaction pathways to synthesize that target molecule or compound. Providing an automated solution to reaction pathway discovery is not a trivial task, and has yet remained unsolved. So, instead has been done manually. It is a time-consuming, repetitive task that can result in sub-optimal solutions, or even failure in finding reaction pathways due to human error. This is why I am looking for a way to use artificial intelligence to help automate this process.
My colleagues and I see this challenge of drug discovery as an important way to help chemists discover reaction pathways and chemical reaction sequences for generating target chemical components. Artificial intelligence-driven discovery of chemical synthesis could have a wide-ranging impact across not only the pharmaceutical industry, but also food, chemical, and materials industries.
For my part, I am looking at how the AI algorithm, “Proof Number Search (PNS)”, can be used. PNS is designed to efficiently solve games. Over the past 20 years however, a family of PNS variants and a large number of technical improvements have evolved. For example, solving positions in two-player games with perfect information has been the major application of PNS variants.
If something is defined mathematically, we can solve it systematically.
The task of finding reaction pathways in chemistry corresponds functionally to game-winning strategies – and computers are more efficient at solving these kinds of problems than we are. This algorithmic approach focuses on the best combination of moves leading to a solution, and finds the most promising strategy or pathway – instead of examining all combinations, which as mentioned, when it comes to drugs, is manually done today.
As in gaming, the chemical reaction process has what are known as “reaction rules.” Take a two-player game where the target molecule is the first player, and precursor molecules are the second player. When the first player makes a move, it has to do so according to the reaction rules. Each move corresponds to each chemical reaction that is applicable to the target molecule. The winning conditions for the first player is proving that the target molecule can be synthesized. The second player’s move is proving that the precursor molecules can’t be synthesized, which prevents the first player from winning. The role of the “solver” algorithm is to systemically measure how promising the reaction rules are for creating a target molecule, and eliminate those that are not, in order to find the winning strategy for the right reaction pathway.
To test our algorithms, we use the benchmark published by Heifets and Jurisica at AAAI 2012. It consists of 19 chemical pathway instances from exams used in an organic chemistry course at MIT; one of which is the real drug molecule atorvastatin, better known as the bad cholesterol-lowering statin, Lipitor®. If something is defined mathematically, we can solve it systematically.
Our research objective is to significantly advance the discovery of new drugs. Using intelligent search algorithms, our approach can return several realistic solutions that chemists can choose from. But to scale this research will require access to large chemical or pharmaceutical reaction databases. So, we are exploring partnerships with chemical and pharmaceutical companies for this kind of access. And we also want to work with the domain experts and chemists to pursue more successful reaction pathways using artificial intelligence.
Much in the same way healthcare providers and medical researchers work with Watson-powered apps today, I hope drug makers will use an AI-powered assistant to quickly and accurately discover chemical pathways for life-saving drugs.
Further Reading on Proof Number Search
A. Kishimoto, M.H.M. Winands, M. Müller, and J-T. Saito (2012) Game-tree search using proof numbers: The first twenty years, ICGA, 35(3):131–156