Evolution works - also on the computer

A chess algorithm developed by Professor Moshe Ziper and PhD student Ami Hauptman from the Department of Computer Science at Ben Gurion University, not by way of normal programming but by a method that imitates evolution, won second place and a prize of $3,000 at a scientific conference for evolutionary software held in London

Avi Blizovsky
About two weeks ago, a scientific conference was held in London in which computer science researchers from all over the world engaged in the field known as "evolutionary computing" participated. As part of this conference, the HUMIES Awards competition is held, which ranks the best software developed using a method that mimics evolution in nature, by only one criterion - do they consistently beat humans in the field in which it specializes. In second place and with a cash prize of $3,000, the work of Prof. Moshe Ziper and PhD student Ami Hauptman from the Department of Computer Science at Ben Gurion University of the Negev which bore the title: "Evolutionary development of a search system for the checkmate problem in N moves in chess."

In a conversation with Prof. Moshe Ziper, he explains that the field of evolutionary algorithms, which the conference deals with every year, was born like many fields in computer science in the 650s and 2004s, but even in the XNUMXs it was an underground field. "Today it is a flourishing field, these conferences are growing year by year - this year XNUMX researchers participated, a number that is considered a high number of participants in conferences dealing with computer science, and since XNUMX the organizers of the conference started a competition designed to encourage the development of evolutionary algorithms. "

What is an evolutionary algorithm?Prof. Zipper: "The field of evolutionary algorithms draws its inspiration from evolution in nature. It is true that the fields of biology and computer science are getting closer, but this is happening in the direction of using databases to analyze the human genome - a field known as bioinformatics. We operate in the opposite direction, applying a biological principle to computer science. There are other fields in computer science that draw their ideas from nature, for example neural networks, but we operate on a more basic principle: evolution in nature has found solutions and complex things that I, as a computer scientist, cannot plan, the brain, a neural network, a heart or a muscle. In nature it is not about planning, because evolution is an unintended process. We simplify the evolutionary process, Darwin, when he wrote his book On the Origin of Species in 1859, did not know how heredity passed from generation to generation, but he saw the result of these processes and treated them as a given. (In retrospect, it turned out that all these phenomena - Mendel's genetics, Watson and Crick's DNA details and the analysis of the human genome only proved the correctness of the theory of evolution and in fact the intuition of A.B. Darwin)

How does evolutionary software work?
In order for an evolutionary system to develop and produce successful individuals, we require four basic components that are the backbone of the system:
• A population of individuals
• Ability to reproduce, which involves heredity (organisms reproduce by asexual or sexual reproduction and leave some of the traits to their offspring).
• Finite resources
• Competition.
Evolution takes place, among other things, due to the fact that there is not enough room for everyone and all creatures of the same species compete for finite resources: food, territory, air, mates... Little by little, those who are more suitable are the ones who will survive, will produce more offspring. The individuals become more adapted to their environment due to genomic changes. As a computer science person, I understand that there is an interesting process that at its abstract level I can take the four conditions, apply them to the computer and run them as an algorithm. And instead of living beings, its products will be programs more adapted to do what is assigned to them"

Why actually do this?
Why should I perform such a process on a computer? Because the evolutionary process in nature knows how to produce structures suitable for their environment. If we implement the process on the computer, we will get a new and interesting planning tool. Thousands of works have already been written in the field, and all of them are proof that if we apply the four conditions we will arrive at interesting software architectures, in an evolution that produces nice solutions to difficult problems from the style, for example, of planning a time system with constraints - there cannot be a room occupied by two lecturers, a lecturer cannot be in it Temporarily in two places. This is a very complicated system to solve with normal programming methods.

How did you develop a system that solves a chess problem, and why chess?
In recent years I have been playing games a lot because even though games are seen as something light, it is a serious field that incorporates artificial intelligence. Games have many sides and abilities that humans use and which if we succeed in imparting to computers, they will bubble up into other areas of more "serious" applications and studies that are of interest to both researchers and industry. There are many types of games - interactive games, board games, characters, puzzles. The oldest are board games like checkers, chess, Chinese chess, Go, backgammon and more. Hauptmann comes from a background in psychology, and we know a lot about the way high-level chess players play. Since Deep Blue - an IBM supercomputer designed at the level of hardware and software for the game of chess - defeated Garry Kasparov 10 years ago, chess software has evolved and today there are software capable of defeating many artists, when installed on a laptop.
These programs use a game tree. The computer says here is the state of the board right now what the opponent can do. During the first there are 40 options and during the second already 1,600. If you go through all the options the tree grows quickly and explodes.. A flesh and blood player rules out most of these options in advance. One of the functions of any good chess software is the mechanism for reducing these possibilities. For example, to ignore options that lead to a certain loss. The better the chess software, the more it knows how to cut.

"We could not of course allocate resources to complete computer programs, so we chose one algorithm - one that checks whether we will reach checkmate within a given number of moves, an algorithm that any chess software that does not have such a strong module fails. We applied the four conditions of natural evolution to this algorithm. We started in the zero generation from an initial population of a thousand chess programs that were terrible and would lose to a 4-year-old boy, but still there was a difference between them - there were a few that were a little less bad. The programs are written so that their code can be mixed and get new software - better or worse. And in each generation we chose the best programs and only allowed them to have offspring. In addition to the genetic mixing of the software in the transition from generation to generation, we also allowed for random mutations. The next condition - competition and finite resources - was realized by limiting the number of programs in each generation to a thousand.
The last condition is the existence of competition. In order to actually decide what good software is - the one that is suitable for its environment, we let them compete with a chess software at the level of a grand master, known as CRAFTY. This software is one of the seven best chess software in the world and its advantage for us is that it is written in open source and its code can be explored. "
One more comment added by Prof. Zipper is that there were no tournaments of games between the thousand programs and the external software written by humans, it was simply not practical, and instead, the two developed a ranking function that compares the programs to themselves and between them and CRAFTY.
According to Zipper, the result of the evolutionary development has yielded algorithms that know how to predict mat with better efficiency, speed and accuracy than Crafty. Since Crafty was written by humans, the system met the definition

It turns out we are better. The evolutionarily developed software knows how to predict mat faster and more accurately than Crafty, which was programmed by a human, it met the criteria of Human Competitive.

The conditions of the competition were that the research in question was published in the scientific literature that includes peer review, and it was indeed published at a conference held a few months earlier, when a committee of judges selected the works that advanced to the finals, and their authors were required to defend them. The judges were the ones who ranked the different works and the work that won first place was about the evolutionary development of cochlear implants and according to Zipper, the competition between the two works was close. Other works dealt with the development of algorithms for cancer diagnosis and many other applications.

And what's next?
Zipper, who has been researching the field of evolutionary algorithms for over a decade, was mainly involved in the fields of games such as poker, backgammon, war games using tanks and more. But now he seeks to repay a debt to biology that provided the evolutionary principle, and with it to solve problems in bioinformatics such as predicting repetitive motifs in RNA. He does this through his colleague in the department, Dr. Danny Barash, who specializes in bioinformatics.
"We developed an algorithm in the evolutionary way that seeks to discover what is common between humans and mice, this is an important field because many of the experiments on new drugs are first performed on mice. We developed an algorithm and submitted an article describing it to one of the leading magazines in the field. We started from biology, implemented the algorithms on the computer and returned to biology.

For the scientific article, on the Ben Gurion University website

To the competition site