|   Angewandte Mathematik   |   Fakultät für Mathematik und Informatik   |   Friedrich-Schiller-Universität Jena   |

3-Hirn  -  New Ways in Go with Computers

Ingo Althöfer

Some Notes on my Seminary, given at the
European Go Congress in Berlin-Strausberg
on Thursday, 10 August, 2000

The Definition of "3-Hirn"

In "3-Hirn" two different computer programs are asked to make their proposals for solving a given problem. Then a human expert has the final choice between these two alternatives. If both programs propose the same solution this one has to be executed. The human is not allowed to overvote the machines. (He or she is "only a tie-breaker" in case of differing computer proposals.) The term "Hirn" is from German language and means something like brain or mind. "3-Hirn" shall indicate that 2 computers and 1 human form a problem solving team (3 = 2 + 1).

3-Hirn in Chess

In 1985 I started 3-Hirn with a seminal experiment in the game of chess. In chess the 3-Hirn consists of two different chess computers or chess programs and one human chess player. The computers are started and make their move proposals. Then the human player has the final choice amongst these candidate moves. 3-Hirn plays chess against other persons or chess computers.

Originally I wanted to write a computer program whose input are the move proposals of two "normal" (different) chess programs and whose task is to select one of these candidate moves for execution. The 3-Hirn experiment with a human controller was intended solely to demonstrate that an omnipotent controller program might be able to improve the chess performance of "traditional" programs. However, the success of 3-Hirn in this experiment was so convincing that I performed further 3-Hirn experiments with me as the human controller. (In the meantime automatic coordinators have been programmed for instance by Mathias Feist for Fritz and other chess programs running under "Chessbase" -  and by my Ph.D. student Stefan Meyer-Kahlen based on his world champion program "Shredder".)

The following list shows the performances of several 3-Hirn teams with changing computers and programs. In all these teams I was the controller. Since 1985 my chess rating has always been between Elo 1950 and 1850.

Year    Strength of the computer programs    Strength of 3-Hirn

1985                           1500                                      1700
1987                           1800                                      2100
1989                           2050                                      2250

1992/93                      2250                                      2500
1995                           2350                                      2540

1996*                         2350*                                    2550*

1997**                       2550**                                  2750**

*  In 1996 not 3-Hirn itself was used, but a variant called "Double-Fritz with Boss". "Double-Fritz" means the chess program "Fritz 4" in its 2-best mode. In this mode Fritz does not only compute its best move but also its second best proposal. The Boss was me and had the final choice among the two Fritz proposals.

**  In 1997 I combined the concepts of "3-Hirn" and "Double-Fritz with Boss" to create a "List-3-Hirn". In List-3-Hirn two different chess programs compute their k best moves each (say k=2 or k=3, depending on the situation). Then a human player has the final choice from these two lists of candidate moves.

As a rule of thumb for man-machine teams with two chess programs of approximately equal strength and me as the human boss I learned:

Strength of the man-machine-team
=     strength of the programs
+ 200 Elo points improvement
+/- 50 Elo points deviation.

This estimate should hold also for 3-Hirn teams with other human controllers of average club strength instead of me. The strength of 3-Hirn is a result of synergy: Tactical power of the computers and human long-range planning supplement very well. Furthermore the human may bring in his or her psychological skills, and he is more or less able to avoid positions which are not well understood by the computers.

The 3-Hirn Approach in General

In 1997 List-3-Hirn achieved a 5:3 against Germany's number 1 Grandmaster Arthur Yusupov. This win was in a match under tournament conditions in "Shuffle Chess". After this milestone event top human players (even from the top ten in the world) were no longer willing to fight against my man-machine teams. So I had time to try the 3-Hirn approach in other fields of decision making.

To repeat (and slightly generalize) the principle of 3-Hirn: (One or several) computer programs produce a clear handful of candidate solutions, and then a human expert has the final choice amongst these alternatives. A more abstract name for 3-Hirn would be "Multiple Choice System for Decision Support" to indicate that the human is in a choice situation.

Recently and currently, experiments with the 3-Hirn were and are underway in the following areas:

-  traffic planning (vehicle routing, organisation of air flights, railway planning)

-  difficult problems in discrete operations research (for instance in production planning and scheduling)

-  computer-aided medicine (for instance cardio-diagnosis with the help of automatic electro-cardiogram analysers)

-  computational biology (alignment problems, protein structure prediction)

And of course I brought 3-Hirn to other games of skill: Backgammon, Othello (=Reversi), FreeCell (a one-person puzzle), and Go. In some games the potential of 3-Hirn is not easy to measure: In Backgammon thousands of matches would be necessary because of the influence of the dice; in Othello the best computer programs alone are (too) much stronger than the top human players. 3-Hirn in FreeCell led to a remarkable jump in performance; and in Go ...

3-Hirn  ...  in Go

Among all commercial Go programs only Many Faces of Go is really fit for 3-Hirn. All the other programs lack by a very simple technical reason: GoProfessional (alias Go4++), Goliath, HandTalk, FunGo, WuLu and GnuGo do not allow the user to take back single moves, but only pairs of moves. (Remember: When you select the move of program Y in 3-Hirn you have to take back the single move proposal of computer X and substitute it in X by Y's move.)

There is one sideway to overcome these missing single take backs: Start the program in "human vs. human" mode and use the "hint feature" to get the program's move proposal. This is not possible in Goliath and WuLu as both even do not have hint features. GoProfessional has a hint button but its hint proposals are of lower quality than its moves in normal playing mode.

Luckily, at least HandTalk has a proper hint feature. So, in most of my 3-Hirn games I used Many Faces of Go and HandTalk.

The program TurboGo has a multi-best mode. In this mode it shows its evaluations for all moves under examination. Instead of simply taking the move with the highest score the user may identify the two highest scores and then select among these moves (this is exactly what I did in "Double-Fritz with Boss" in chess). A problem is that often the two highest-scorers lie in the same part of the board and have similar weaknesses.

Observation: Currently, each Go program makes at least one terrible blunder in each of its games.

Having this in mind, today's best strategy in 3-Hirn Go needs only a few rules of thumb:

Recognize and avoid these terrible blunder moves.

Play simple (at least against human players)  -  do not look for the "game theoretically" best move.

Do not bother when your favorite move is not among among the candidates computed by the programs.

Probably, in twenty years this concentration on desaster-avoidance and desaster-management may be superseded by more symbiotic strategies.

In my 3-Hirn games I do not only use the move proposals of the programs but also their territory estimates and their estimates on the life/death status of groups. This helps to see how correctly the program evaluates the current board position and where its weaknesses in this current evaluation lie.

I am a beginner in Go. Besides 3-Hirn I have played only a handful of games by myself. Experienced players (for instance Peter Hagemann, 1-kyu from Detmold) believe that my strength is around 17 kyu. In 3-Hirn mode I have played several handicap games against low Dans (Achim Flammenkamp, Guntram Scheithauer, Thomas Rolle, Raymond-Georg Snatzke). On 19x19 board they gave me between 4 and 6 stones, and 3-Hirn lost all of these games except one. In three non-handicap games against an 8 kyu (Karsten Graf) 3-Hirn achieved two wins and lost once. Almost all persons involved got the impression that 3-Hirn is clearly superior to Go programs in normal playing mode.

On 9x9 board Guido Tautorat (4-dan) played two games against 3-Hirn where the move selection was not done by a single human but by a team with Peter Woitke (5 kyu), Thomas Rolle (2-dan) and myself. (So it was more a 5-Hirn than a 3-Hirn.) Peter Woitke is the programmer of GoAhead (European Computer Go Champion 2000), and GoAhead was used in the "Hirn-team". Guido took the white stones, the komi was set to -8. (So White had to win by 9 points ...) In the first game GoAhead was supplemented by HandTalk, and Guido Tautorat won by 8 points. In the second game GoAhead and Many Faces of Go were used, and White won by "only" 6 points. Guido Tautorat was rather impressed by the performance of the man-machine combinations.

During the European Go Congress 2000 in Strausberg an exhibition game on 9x9 was played: White was Saijo Masataka, a professional 8-Dan player from Nagoya in Japan. Black was *-Hirn, a variant of 3-Hirn: The move proposals of GoAhead and Many Faces of Go were taken, and the auditory (with almost 50 players ranging from 5-dan to 20-kyu)  had to vote which of the computer moves to make. It was a simple majority voting where each participant had the same weight, independently of his or her Go strength. Saijo gave two stones handicap and - no surprise - won the game convincingly.

The moves of this game are given below. The moves in brackets are those which did not get the majority. Black handicap stones were put on c3 and g7.
W1 f3   B2 d7 (MF g6)   W3 c5   B4 d5 (MF b1)   W5 d6   B6 c6 (MF e6)   W7 e6   B8 e7 (GA b5)   W9 c7   B10 b6 (proposed by both programs)   W11 f6   B12 f7 (GA b5)   W13 b5   B14 b7 (both)   W15 d4   B16 h5 (GA d3)   W17 g4   B18 d3 (MF h3)   W19 c4   B20 b3 (GA e4)   W21 e2   B22 b4 (GA e4)   W23 a5   B24 b1 (GA e4)   W25 d2   B26 e4 (MF a2)   W27 e5   B28 e3 (both)   W29 g5   B30 h6 (both)   W31 h4   B32 resign (both programs had proposed to play j4).

Saijo Masataka, 8-pro, giving explanations for his move W25 d2 in the game against *-Hirn

4 Types of 3-Hirn Games

(a)  3-Hirn   versus   opponent (human or program)

(b)  3-Hirn with human I   versus   3-Hirn with human II  (same programs for both sides)

(c)  "3-Hirn good"   versus   "3-Hirn bad"  (same programs and same human for both sides).

(d)  3-Hirn   versus   3-Hirn, where the intention is not to play as strong as possible but to generate "beautiful games"

(a) is the standard mode of play.  (b) and (c) may be interesting especially for beginners, who want to learn the game of Go by playing in 3-Hirn mode. The meaning of (c) is that the human wants to produce a game where a predefined side (either Black or White) wins as clearly as possible. One example goal for (d) might be to generate a game where Black gets all four corners and White the center.

Modular Programs  -  and some other Wishes to the Go Programmers

My hope is that the programmers of Go will design their future commercial products in a more "3-Hirn friendly" fashion. Especially I would like to see:

Engine Concepts (like ChessBase in chess)
Several Go programs can run - alone or simultaneously - under one frame. The frame has to be programmed only once; and its interfaces have to be made public. In my eyes "Many Faces of Go" would be an interesting starting point for such a frame.

Programs should have a Multi-Best Mode
Not only the best move is computed but all candidate moves are shown together with their evaluations. TurboGo 4.1 already has a multi-best mode.

Meta Engines
These are programs which select among the move proposals of normal Go programs or engines.

Better Autoplay Features
They may simplify (intensive) testing sessions.

Programs with "Open Parameters"
These parameters may be set and modified by the user. Most top chess programs like Rebel, Shredder, Nimzo have such open parameters  -  and power users have tuned the programs with very interesting sets of parameters.

Anytime Algorithms
An anytime algorithm is started and computes ... computes ... computes ... until it is stopped. In the meantime it shows what it has found out already - and a human expert in front of the screen may inspect these "intermediate results" and select among them in an appropriate moment. (In fact this was the way in which I used the chess programs in 3-Hirn.) Currently none of the Go programs at all has such an anytime algorithm.

In general, programmers in Go and other games of skill can learn (and should copy) a lot from the computer chess community and her decades of experience.

Two Open Questions in 3-Hirn Go

What is the optimum human strength for controlling programs like "Many Faces of Go" and "HandTalk" in a 3-Hirn?
Go programmers might be good controllers, as well as Team-Go players who are used to play in teams with much weaker partners.

Is it in Go possible for a beginner to efficiently learn the game only from controlling in 3-Hirn teams?
I mayself try to do so.

Concluding Remarks

*  My shortterm plans in Go are twofold: I want to collect more experiences with 3-Hirn, and I want to convince the authors of Go programs to make their brain childs more "3-Hirn friendly".

*  One of my intermediate plans in Go is to bring 3-Hirn on dan level as soon as possible.

*  An article on the 3-Hirn approach will appear in one of the next issues of the "Deutsche Go-Zeitung".

*  At Jena University I am a professor in the Institute of Applied Mathematics. Computer-Go and the 3-Hirn approach belong to my fields of research, and it is possible to write Ph.D. theses on these subjects in my group. Interested graduates with solid background and a diploma in mathematics, computer science, theoretical physics or other relevant fields may contact me via althofer@mipool.uni-jena.de  .

References

I. Althöfer. Das Dreihirn  -  Entscheidungsteilung im Schach. Computerschach&Spiele 6/85 (Dezember 1985), pp. 20-22.

I. Althöfer. 13 Jahre 3-Hirn  -   Meine Schach-Experimente mit Mensch-Maschinen-Kombinationen. Book, published by the author, Jena, 1998, ISBN 3-00-003100-6.

**** I. Althöfer. Decision support systems with multiple choice structure. In ....

M. Müller. Computer Go: A research agenda. ICCA Journal 22 (1999), pp. 104-112.