Table of Contents

BROADENING OUR SCOPE

After two and a half years of functioning as Editor-in-Chief of the ICGA Journal on behalf of the ICCA, the situation is now back to normal. It is my pleasure to offer you the first issue of the ICGA Journal published under the aegis of the ICGA. Below our President David Levy introduces the ICGA to you, together with its aims and activities. Therefore this Editorial will be brief. Nevertheless, I would like to single out two important issues, next to the official establishing of the ICGA, namely the solution of Awari (by John Romein and Henri Bal, see pp. 162-165) and the range of very successful tournaments held within the framework of the Seventh Computer Olympiad (pp. 169-192).

With two challenging matches in the foreseeable future, Kramnik – Deep Fritz, and Kasparov – Deep Junior, the conclusion is inevitable: computer-chess researchers have reached the pinnacle of human performances. So, the time is ripe to broaden our scope officially from ICCA to ICGA. Yet, for chess, a prevailing question remains: when will a computer-chess program play at a superhuman level? As you may understand the ICGA Journal keeps you informed on the first signs of such a development as well as on the ELO rating achieved by such programs.

Finally, with much delight I would like to draw your attention to our new website www.icga.org constructed by Jeroen Donkers. There you can find a variety of descriptions of Olympic games, reports on matches, and links to other interesting sites. The managing editorship is performed by various skilled and qualified website editors.

Jaap van den Herik

ICCA BECOMES ICGA

The year 2002 marks the 25th anniversary of the founding of the ICCA. During those 25 years we have witnessed remarkable progress in our original field of interest, computer chess. At the 2nd World Computer-Chess Championship in Toronto in 1977 Monty Newborn, who was ICCA President from 1983 to 1986, made what was, at that time, a highly controversial prediction:

"In the past Grandmasters came to our computer tournaments to laugh. Today they come to watch. Soon they will come to learn."

Within little more than a decade after the end of Monty's term of office as President his prediction was no longer controversial. The strongest chess program of the day, Deep Thought, had already defeated Grandmasters in tournament play and had finished joint first in a tournament ahead of former World Chess Champion Mikhail Tal. Since then the standard of play of the leading chess programs has progressed so much that nowadays many of them can defeat most Grandmasters at fast time controls and the top few sometimes win games at "classic" time controls against World-Championship calibre players, as both Kasparov and Kramnik can testify.

It is clear that the ICCA played a major role in the steady and inexorable march of progress in the playing strength of chess programs. Our tournaments, both the World Microcomputer Chess Championships and the (unrestricted) World Computer-Chess Championships, as well as other events (such as the ACM tournaments) organized very largely by ICCA Board members, provided chess programmers with a forum in which they could exchange ideas and, more importantly, where the competitive incentive stimulated them to work on improving their programs. The persistent programmers returned year after year, hoping each time that the changes they had made since the previous tournament would enable their program to improve on its previous performance. Thus we have witnessed a very steady improvement, year by year. It can only be a matter of a few years before even the human World Chess Champion has absolutely no chance in a match against our own World Champion and its leading colleagues.

While chess programs were becoming ever stronger, the scope and interest of the ICCA and our ICCA Journal expanded to include other strategy games. The Advances in Computer Chess conference was taken over by the ICCA and then became Advances in Computer Games. Your President donated the Computer Olympiad to the ICCA in order to ensure its continuance. And now, in 2002, we have formally changed the name of the association to International Computer Games Association (ICGA) (see p. 194). The ICCA Journal was already renamed into ICGA Journal, following a decision of the Paderborn Triennial Meeting in 1999.

The ICGA is the global organisation promoting the use of computers in "game" situations. It contributes to the experience of game- and computer-game playing in the widest sense, and in the fields of education, entertainment and academic research in Artificial Intelligence. Our aims, broadly, are as follows.

1. To promote the demonstration of Artificial Intelligence via the domain of computer games.
2. To foster the community of those interested in the theory and practice of computer gaming.
3. To promote competition in games that include computer involvement.
4. To add value, through education and entertainment, to the human experience of game-playing.

In the future, we are sure, the ICGA will be recognized as having contributed widely to the human experience of game- and computer-game playing, as the ICCA did for chess in years past. The ICGA will also become world-wide known for the contribution of its members to the applicable techniques within Computer Science and Artificial Intelligence.

The headquarters of the ICGA is in Maastricht. In July we signed an agreement with the Universiteit Maastricht under which the university's support for the ICGA will continue for 10 years and, in return, the ICGA agrees that our journal will be based at the university's Computer Science Department , nowadays called IKAT, throughout that period.The ongoing activities of the ICGA include:

1. Production of the ICGA Journal four times per year.
2. A continual programme of competitive events in several games, including world computer championships in various games.
3. The organisation of Computer Olympiads, hopefully on an annual basis, embracing tournaments and exhibitions in a number of games.
4. The promotion of bionic games including man vs. machine events and man+machine events such as "Advanced Chess".
5. The expansion of our web site www.icga.org to include sections on each of the games within our area of interest.

The scope of our games domain now includes not only discrete, 2-person, board games of no chance and perfect information, but also games that are non-discrete, games that involve chance, partial information or negotiation, as well as management games and games such as snooker and soccer that have a strategy element. In fact any "game" in the widest sense of the word, provided always that some strategy is required to play the game well. We intend to explore all of these games and more, to introduce them in our journal, on our web site and at our conferences, and to organize tournaments for them (albeit in some cases simulation tournaments).

Long live the ICGA!

David Levy
President of the ICGA

The Computer Science Department of the Universiteit Maastricht has assembled its activities in the Institute for Knowledge and Agent Technology (IKAT). Henceforth we should use the name IKAT as the home base for the ICGA headquarters and for the ICGA Journal.

VERIFICATION OF ENDGAME DATABASES

Tsan-sheng Hsu and Ping-Yi Liu¹,

ABSTRACT

This article studies the verification of endgame databases using algorithms with limited memory space. To verify a constructed endgame database, the value of each position is checked for consistency against the values of the successor positions. Hence, a trivial implementation of this algorithm needs to access the database content randomly. A graph-theoretical technique called vertex-partitioning is proposed to divide an endgame database into several partitions. The positions in a partition have the good property that their successor positions are all in a relatively small proportion of the created partitions. Therefore, only a small portion of the database needs to be loaded into the main memory at one time while verifying all positions in a partition. Performance results in verifying Chinese chess endgame databases using this method are given. Our technique is a generalization of previous approaches used in saving memory during the construction of endgame databases. The technique can be exploited, too, in other similar games, such as Western chess. Moreover, the technique can be applied to save the amount of memory used in the initialization phase of retrograde analysis when constructing endgame databases.

GAME-TREE SEARCH ALGORITHMBASED ON REALIZATION PROBABILITY

Yoshimasa Tsuruoka¹, Daisaku Yokoyama², and Takashi Chikayama³

ABSTRACT

In games like chess, the node-expansion strategy significantly affects the performance of a game-playing program. In this article we propose a new game-tree search algorithm that uses the realization probabilities of nodes for deciding upon the range of the search. The realization probability of a node represents the probability that the moves leading to the node will actually be played. Our algorithm expands nodes as long as the realization probability of a node is greater than the threshold. Therefore, it spends little computational resource on unrealistic moves, resulting in a more effective search. We have implemented this algorithm in a Shogi-playing program. Experimental results show that the proposed algorithm achieves state-of-the-art performance on a standard test suite for computer Shogi. Moreover, its performance gain is equivalent to a speed-up of more than two.

VERIFIED NULL-MOVE PRUNING

Omid David Tabibi¹ and Nathan S. Netanyahu²,

ABSTRACT

In this article we review standard null-move pruning and introduce our extended version of it, which we call verified null-move pruning. In verified null-move pruning, whenever the shallow null-move search indicates a fail-high, instead of cutting off the search from the current node, the search is continued with reduced depth.

Our experiments with verified null-move pruning show that on average, it constructs a smaller search tree with greater tactical strength in comparison to standard null-move pruning. Moreover, unlike standard null-move pruning, which fails badly in zugzwang positions, verified null-move pruning manages to detect most zugzwangs and in such cases conducts a re-search to obtain the correct result. In addition, verified null-move pruning is very easy to implement, and any standard null-move pruning program can use verified null-move pruning by modifying only a few lines of code.

NOTES

AWARI IS SOLVED

John W. Romein¹ and Henri E. Bal²

Amsterdam, The Netherlands

1. THE RESULT

The main message of this note is that we solved awari. With perfect play, the game ends in a draw.

Awari (also known as wari, owari, awale, awele, and ayo) is an ancient and well-known mancala variant that originates from Africa, and is played worldwide now. The rules are given in the Appendix. Although the rules are simple, the game requires profound strategic insight to be played well.

We solved the game by searching the entire state space on a parallel computer with 144 processors. The state space contains 889.063.398.406 positions, and is searched using retrograde analysis. The analysis determined the best moves and exact outcomes for all reachable board positions, starting in the final positions, and searching backward to the initial position. No single computer has enough processing power and memory to search the state space, but even on a modern, parallel computer the problem was extremely challenging.

For each number of stones on the board, a separate database was computed that contains the eventual outcomes (after perfect play) of the n-stone positions. The hardest database was the 48-stone database, which contains over 200 billion positions, larger than any (endgame) database computed for whichever game so far. Others tried to solve the game by creating endgame databases of up to 40 stones and perform a forward search from the root, but were unsuccessful because the forward search did not hit the endgame databases fast enough. We therefore computed all databases of up to 48 stones (except the 47-stone database, since no 47-stone positions are reachable) by retrograde analysis.

Retrograde analysis requires much main memory, due to the random accesses of database entries during con-struction. The choice or design of the algorithm to create awari (endgame) databases is mainly determined by the amount of main memory available (Lincke, 2002), trading memory for additional computational effort and storing intermediate results on disk. Our system contains 144 Pentium III processors at 1.0 GHz, 72 GB of distributed main memory, a total disk space of 1.4 TB, and a Myrinet interconnect: a fast, switched net-work. One of the challenges was to handle the relative "small" amount of memory. The parallel retrograde search algorithm described by Bal and Allis (1995) is efficient, but would have required more than 350 GB of memory, much more than we had. Sequential memory-limited search algorithms for awari endgame databases exist (cf. Lincke and Marzetta, 2000), but solving awari entirely on a single machine would take decades, if not centuries, since these algorithms still require much more memory than a single computer provides. We developed an efficient parallel algorithm that partitions the work and the database entries over the machines, and uses the memories economically.

Another challenge was to handle the interprocessor communication efficiently. The random accesses of database entries result in many messages being sent between the processors. Our algorithm makes all communication asynchronous by migrating work instead of data, hiding network latency and keeping the processors busy. If processor A needs data from B for some computation, it does not ask B for the data (which requires waiting for a reply message), but sends the work to B (which is done asynchronously), and continues doing other work. The power of this idea was already demonstrated in forward search (Romein et al., 2002). Our algorithm balances and overlaps the use of all resources: processors, disks, memory, and network. Despite the high network bandwidth requirements (we exchanged 1.0 petabit (= 10 ¹⁵ bits) of data!), the algorithm is efficient: it required only 51 hours to solve the game. The details of the algorithm, statistics on the computed databases, and a summary of the measures to verify the databases are described separately (Romein and Bal, 2002).

The fact that awari is a draw makes it a fine game: it is neither an advantage, nor a disadvantage to begin the game. It was not a surprise that awari is a draw; however, there are quite some misconceptions about good openings (see also the next section). For example, it was expected that 1. F4 f4 would be the only non-losing opening, but 1. F4 b4 and 1. F4 e4 lead to draws as well. Other openings, believed to be draws, are now rejected since they lose.

We set up a webserver with a database that contains the computed results for all reachable awari positions. The database is 778 GB large. Via a Java applet, the best move(s) and eventual score for all positions can be looked up. The applet can also be used to play a game against the database. By default, we decreased the playing strength by allowing the computer to make (small) mistakes, so that the human can actually win a game. After all, being defeated by a program from which one cannot actually win, may not be satisfactory. The applet and more statistics can be accessed via awari.cs.vu.nl/.

Did we ruin a perfectly fine game? We do not think so. Connect-4 was solved as well, and people still play the game. The same holds for other solved games. At professional level, things may change. On the one hand, the database may help improving the understanding of the game. On the other hand, it is not unlikely that the game will be excluded from the Mind Sports Olympiad (even though they use slightly different rules).

2. TOURNAMENT GAMES REANALYZED

With the perfect knowledge from our database, we can analyze the games played by world-champion-level programs. In the September issue of the ICGA Journal, Lincke and Van der Goot (2000) reported on the games played at the 2000 Computer Olympiad in London. Competitors were the programs SOFTWARI and MARVIN. It was expected that the programs would play nearly optimal, and therefore it was already surprising that three out of eight games actually had a winner. MARVIN won the tournament by 4.5–3.5.

Both programs used an opening book and complete endgame databases for up to 34 stones. Because of the endgame databases, the games were ended as soon as there were 34 or fewer stones on the board, since the programs can play the remainder of the game perfectly.

Below, we annotate the games from the tournament. The original text (Lincke and Van der Goot, 2000) is copied in a plain font; our annotations are displayed using bold, italic characters. Wrong moves (i.e., moves that lead to fewer captures than possible) are highlighted in inverse colours. The correct move(s) are appended in subscript, between brackets. The superscript numbers show the score for the first player from that moment on; a score of +4 means that the first player can win the game with 26–22 if no further mistakes are made. Subsequent wrong moves change the score again. For example, d1⁺¹_[a11,e9] means that the program played d1, while it should have played a11 or e9; the first player then has an advantage of 1 stone. For each program, the last move from the opening book is marked by a *.

Two games (3 and 4) were played perfectly, and quickly drawn in about ten moves. The remaining games became more interesting as they required more moves. In these games, the programs made more errors, even while in their opening books, and sometimes as soon as on the third move! In the final and decisive game, MARVIN did 13 wrong moves, but still won the game! In games 1, 5, and 7, both programs have been in a winning position; in games 2, 6, and 8, the program that was behind (repeatedly) drew level with the opponent. The winning chances changed mutually, but the competitors were not always aware of this.

Although the programs made more errors than expected, they did not play badly. MARVIN did the right move in 82% of the cases, and SOFTWARI in 87% of the cases. On average, MARVIN lost 0.27 points per move, and SOFTWARI 0.25 points (losing a point means: giving the opponent the opportunity to capture one stone more). At this rate, we estimate that the programs would lose with about 27–21 when playing against our database.

3. THE GAMESCORES ANNOTATED

Game 1: MARVIN–SOFTWARI [1–0]

1. F4 f4  2. B5 d5  3. B1 f1  4. F1 b5  5. D6×2 f1  6. F1 b1  7. C8 c9×2  8. D2 b1  9. F1 d2  10. B1 c1  11. C2 d1⁺¹_[a11,e9]  12. D1 e10  13. C1 c1  14. E12⁰_[A11] c1  15. C1 f4  16. C1^-2_[D5] e1  17. B3 f1⁰_[d3]  18. C1 d3  19. D8×4 d1  20. A15 c2  21. B2 f1  22. D3 d2??⁺²_[e3] [e3 is a draw]  23. A1 b4  24. E5×4 f2×2  25. C3 a17×3  [25–23]

Game 2: SOFTWARI–MARVIN [1–0]

1. F4 f4  2. B5 d5  3. B1 f1  4. E5 d1  5. C8 a8⁺²_[d1]  6. E1 c8  7. B2⁰_[A9] d3  8. C3 b8  9. C1 d1  10. B1 c1  11. C1 d1  12. A11 c1  13. D14×3 d3×2  14. F8 d1⁺¹_[c2]  15. C2 a1⁺²_[c2]  16. D1 e18×2*  17. D2 a1  18. C2 d1  19. D1⁺¹_[F1] e1  20. F1 a1  21. B5 f11  22. C2 a2⁺²_[b8]  23. E15 d2  24. B2 a2  25. D5* a1  26. E1 f2  27. B1 e3  28. F6×2⁰_[A7] a1??⁺¹_[e1] [a1 is a loss, e1 leads to a balanced position]  29. C3 e1  30. A7 a1  31. F2 a1  32. D2 d1⁺³_[b20]  33. C1 f1  34. F1 e1⁺⁴_[a1]  35. D1 c10⁺¹⁰_[f1×2]  36. F1×3 f2⁺¹²_[b20]  37. C1⁺¹⁰_[D1] e1  38. D2 f1⁺¹¹_[b20]  39. B4 b20  40. B2 c2  41. E9 a2  42. D4×3 d5  [29.5–18.5]

Game 3: MARVIN–SOFTWARI [1/2–1/2]

1. F4 f4  2. B5 c5  3. F1 d6  4. E5 d1  5. B2 c1  6. D8×3 d2*  7. E1 c1  8. C8 a10×4  9. A8×3* f2×3  10. A1 b10  11. F6×2  [24–24]

Game 4: SOFTWARI–MARVIN [1/2–1/2]

1. F4 f4  2. B5 c5  3. E5 b6×2  4. C6×3 b1  5. F3×2 e6×2  6. C1 b1  7. B1 f3×2  8. B1 a9  9. C2 c2  10. A10×3  [24–24]

Game 5: MARVIN–SOFTWARI [1/2–1/2]

1. F4 f4  2. E4 a6  3. A6^-1_[C5] b7  4. E1 a1  5. C7 b2⁰_[e6×2]  6. E1 a1⁺²_[d9]  7. D7⁰_[B7] b2  8. B7^-2_[E1] d11  9. C2 b2  10. F8*^-3_[E4] b1  11. D3 d2  12. A3 a5⁺¹_[c17×3]  13. C1 f6 × 2 14. B4 c18⁺²_[b1,d1]  15. F2×5 f2×3  16. A4⁰_[C4] e13×2  17. D8×3  [24–24]

Game 6: SOFTWARI–MARVIN [1/2–1/2]

1. F4 f4  2. E4 a6  3. C5 e5  4. E1 c7  5. A8^-2_[B7] c1^-1_[d7×2]   6. E1 e1  7. D9* c1  8. E1 a3  9. C3 f5×4*  10. B9×2 c2  11. E1 e1  12. A2 a1⁰_[b12]  13. C3 f1  14. A1 d13  15. E2×2 e2×2  16. C1 f3  17. C1 c1  18. B4 d1  19. A1 b14  20. F15 c4×3   21. E3×3  [24–24]

Game 7: MARVIN–SOFTWARI [1/2–1/2]

1. F4 f4  2. C5 c5  3. B6 b7×2  4. A7 b1  5. F3×3 f2×3   6. C1^-1_[A1] d7  7. A2 b1⁰_[a9]  8. C2 a9  9. C1 d1  10. B3 c2  11. A1 f2×2   12. C1 e10  13. A2 d1  14. F1×2* b2   15. D16 a2  16. A1 f2  17. F2 a1  18. A1 e2  19. A1 d2⁺²_[f1]   20. B7 a1  21. D1⁰_[F1] e1  22. C4 b7  23. D1 d1  24. B1 a1  25. A1 c7  26. F2 × 2  [24–24]

Game 8: SOFTWARI–MARVIN [0–1]

1. F4 f4  2. C5 c5  3. A6^-2_[B6,F1] d6^-1_[b6]  4. B8 c1  5. C3* b7*  6. E8?^-3_[C1] [C1 is better, after this move SOFTWARI was at least two stones down for the rest of the game. Actually, SOFTWARI drew level with MARVIN three times in the remainder of the game]  6. ... d4×2   7. D10 d1^-2_[a10×2]  8. E1 c3  9. C1 e12  10. C1 d2  11. B2 c1  12. C1 e1  13. E1 b3^-1_[d1]  14. D5×2 e1? [d2 is better. No! d2 loses one point]  15. A6 d2?⁰_[b1] [b1 is better]  16. D1?^-1_[F11] [after the last two bad moves of MARVIN, SOFTWARI had the chance to move into a balanced position with F11]  16. . . . e1⁰_[b1]  17. B1 b1  18. C2^-2_[F11] c1  19. F11 d2  20. A1 c1^-1_[e2]  21. D2 e2  22. F1^-2_[C1] d1⁰_[b1,f17×2]   23. C1 f17  24. D3^-3_[C2] e2  25. C2^-4_[F1] d1  26. F1 e1  27. A4 c1  28. D2 b2  29. C1^-5_[F1] d2  30. F1 e1  31. E12^-6_[B5] b1  32. B6 a21×3  33. A3 f7^-5_[d3,e3]  34. A1 d3^-3_[c5]  35. A1^-6_[C6] a1^-5_[f1]  36. C6 c6  37. D8×3 e6^-2_[b6]   38. A2 d2  39. d1^-6_[E4×2] f2^-5_[b6,e1]   40. A1^-6_[E5,F7] e1  41. F7 d1^-4_[b7]  42. A1 f2  43. A1 e2  44. A1 c2  45. E5×2  [22–26]

4. REFERENCES

Allis, L. V., Meulen, M. van der, and Herik, H. J. van den (1991). Databases in Awari. Heuristic Programming in Artificial Intelligence 2: the Second Computer Olympiad(eds. D. N. L. Levy and D. F. Beal), pp. 73–86.

Ellis Horwood, Chichester, England. ISBN 0–13–382615–5.

Bal, H. E. and Allis, L. V. (1995). Parallel Retrograde Analysis on a Distributed System. Supercomputing ’95, San Diego, CA.

Lincke, T. R. (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D. thesis, ETH Zurich, Swiss.

Lincke, T. R. and Goot, R. van der (2000). Marvin Wins Awari Tournament. Journal of the International Computer Games Association, Vol. 23, No. 3, pp. 173–174.

Lincke, T. R. and Marzetta, A. (2000). Large Endgame Databases with Limited Memory Space. Journal of the International Computer Games Association, Vol. 23, No. 3, pp. 131–138.

Romein, J. W. and Bal, H. E. (2002). Solving the Game of Awari using Parallel Retrograde Analysis. Submitted for publication.

Romein, J. W., Bal, H. E., Schaeffer, J., and Plaat, A. (2002). A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459.

5. APPENDIX: RULES OF AWARI

Awari is played on a board that contains two rows of six pits, in which stones are kept. Each player owns one of the rows. The game starts with four stones in each pit. When a player is to move, he chooses one of his own nonempty pits, takes all stones from it, and sows them one by one, counterclockwise over the remaining pits, skipping the emptied pit if there are more than 11 stones. If the last stone ends in an opponent’s pit and contains two or three stones after sowing, they are captured; if the second last pit holds the same conditions, they are captured as well, and so on. The objective of the game is to capture more than 24 stones. The player must give the opponent a countermove, unless no such move is available. If a player cannot move, the remaining stones are captured by the opponent. A repeated position leads to an even division of the remaining stones, ending the game.

Unfortunately, the rules slightly differ from one country to another. For example, the "grand slam rule", which states what happens if all opponent’s pieces are captured in a single move (if allowed at all !) comes in many variants. We use the rules that are used by all computer scientists since the first publication on computer-aided play of awari (Allis, van der Meulen, and van den Herik, 1991).

AWARI IS SOLVED (in pdf format)

COMMENTS ON THE AWARI SOLUTION

Jeroen Donkers¹

Maastricht, The Netherlands

John Romein and Henri Bal (2002) unexpectedly solved the game of Awari in May 2002 using a distributed supercomputer with 72 nodes. This is a major achievement for computer science.

Having said this, I would like to discuss the set of rules that is used in this solution (cf. their Appendix). The first appearance of this specific set of rules for Awari, to the best of my knowledge, is in the technical report on LITHIDION by Allis, Van der Meulen, and Van den Herik (1990). These rules are based on Deledicq and Popova (1977). Other computer programs used the same rules in previous Computer Olympiads and in re-search on endgame databases. This set of rules, however, is not used in the traditional mancala versions. The names for the traditional Awari game include Awale, Kale, Oware, and Wari, depending on the language of the player (Murray, 1954; Russ, 2000). There are some slight differences in the interpretation of the rules, as in any game. The rules used by the Oware Society and the MSO can act as a reference.

The common rules of Awari and Wari are:

1. The game is played on a 2 x 6 board. Initially there are 4 stones in each hole.
2. A move is defined by taking all stones from one hole at the own side and sowing them in counter-clockwise direction. If allowed, capture takes place.
3. Capture can take place if the last stone ends in an opponent's hole that now has 2 or 3 stones in it. All stones in this hole, and all stones in previous opponent holes that also contain 2 or 3 stones are captured.
4. The game ends if one of the players cannot move: the opponent then captures all remaining stones.
5. When possible, a player has to select a move that leaves at least one stone to the opponent.
6. The winner is the player that captures the most stones.
   There is an extra rule in Awari that is not known in human play:
7. If a position is repeated three times, the game is a draw and the remaining stones are divided over the players, possibly resulting in a half stone.
   In Wari, there is a rule that one cannot capture all stones of the opponent in one move:
8. If you choose to perform a move which would take all stones from the opponent, you do not capture: all stones remain on the board.
   Russ (2000) gives yet another rule which is not used in Awari neither at MSO nor in the Oware Society:
9. If a player cannot move anymore, and the opponent has two or three stones left, then the game is over, but the player receives one of the opponent's stones.

To summarize, there are two questions for the current Awari solution since (1) rule 7 is introduced when computers started to play Awari; it is not known in human play, and (2) rule 8 is not applied in Awari; here we touch upon a difference between Awari and Wari. Both differences may question the game-theoretic value of the human game Awari. Romein and Bal (2002) are aware of the existence of these slightly different rules.

This observation does not in any way influence my appreciation for the achievement by Romein and Bal. I do not expect that these differences in the rules will change the game complexity very much, but it may affect the outcome. Maybe it is possible to re-compute the database with the traditional rules of Wari.

References

Allis, L.V., Meulen, M., van der, and Herik, H.J. van den (1990) Databases in Awari. Technical Report CS-90-5. Rijksuniversiteit Limburg. Maastricht, The Netherlands.

Deledicq, A. & A and Popova (1977). Wari et solo. Le jeu de calcul Africain. Paris: Cedic.

Murray, H.J.R. (1952). A history of board games other than chess. Oxford at the Clarendon Press, London.

Romein, J.W. and Bal, H.E. (2002). Awari is Solved. ICGA Journal, Vol. 25, No. 3, pp. 162-165.

Russ, L. (2000). The Complete Mancala Games Book. Marlow & Company, New York. ISBN 1-56924-683-1

Websites

The Awari Oracle at the Vrije Universiteit: awari.cs.vu.nl/

University of Alberta Awari page: www.cs.ualberta.ca/~awari

MSO homepage: www.msoworld.com/

Oware Society homepage: www.oware.clara.net/

SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM

David Levy²

London, UK

Tsuruoka et al. (2002) present a new approach to the use of fractional plies, previously employed in the SEX algorithm (Levy et al., 1989). While both techniques use search extensions that are determined by the move category, the fractional plies themselves are based on different concepts. Realization Probabilities are based on the relative frequencies with which each category of move is played in master games from positions in which at least one move exists for the category in question. The extensions employed in the SEX algorithm are based on how important each category is considered to be in a computerized search to determine the best root move.

The Realization Probabilities approach fails to take into account that although a particular move category may occur with a certain probability in master games, it may well be necessary for a computerized search process to consider certain categories of moves significantly more frequently (or significantly less frequently) than they are played in master chess. For example, whereas most strong chess programs examine all checks, the probabil-ity of a check being played in a master game position (in which at least one check is legal) is very much nearer to 0 than to 1. The reason checks are so important in the search tree is not because they are played relatively frequently in games but because of their potentially devastating effect. Tsuruoka et al.(2002) show that, for Shogi, the use of Realization Probabilities achieves a significant increase in speed. Having read the article I would like to make three suggestions for improvement.

1. It would be interesting to investigate whether their results could be improved upon by raising the transition probabilities for the most important move category(ies) in Shogi, corresponding to using a transition probabil-ity of 100 percent for checks in chess.
2. Another possible improvement would be to take more cogniscence of moves that fall into more than one category. Rather than use the highest probability of the categories, it might be appropriate to compute a com-bined probability Pcom from:
   Pcom = 1 – (1-PC1)(1-PC2)(1-PC3)…..
   where PCi is the transition probability for category i.
3. A further refinement would be to introduce the pseudo-category "all moves" for which a transition prob-ability is correlated to the difference between the static score for a given move and the static score for the high-est scoring move from the same position. Moves with relatively high static scores would then tend to be searched more deeply than those with lower static scores.

References

Levy, D.N.L., Broughton, D., and Taylor, M. (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1, pp. 10-21.

Tsuruoka, Y., Yokoyama, D., and Chikayama, T. (2002). Game-Tree Search Algorithm based on Realization Probability. ICGA Journal, Vol. 25, No. 2, pp. 145-152.

² 9, Springfield Avenue, London N10 3SU, England. Email: davidlevylondon@yahoo.com.

News, Information, Tournaments, and Reports

PRESIDENT'S REPORT

David Levy¹

London, UK

The period 1999-2002 has been a challenging one for the ICCA because of the difficulty of obtaining a satisfactory level of sponsorship for our organization and our events. This is partly due to the general economic climate but another important factor has been a decrease in public interest in computer chess since Kasparov lost to Deep Blue. The Association has also suffered a decline over this period in the number of members.

Despite these financial woes and the state of the accounts as explained in the Secretary-Treasurer's report (ICGA Journal, Vol. 25 No. 1), I am pleased to report that the Association is indeed solvent and that we are already assured of remaining so throughout 2003. This is due to an agreement recently signed with a sponsor for the right to host the 2003 World Computer-Chess Championship in Graz (November 22nd-30th) and a new agreement signed with the Universiteit Maastricht. I am very pleased to report that the agreement with the Universiteit Maastricht includes a 10-year period of support for our Journal, up to the end of 2012.

Furthermore, discussions have commenced with a potential host that has expressed an interest in the 2004 World Computer-Chess Championship and, possibly, the Computer Olympiad. It has been very largely from the hosting fees we have obtained for our World Championships that the Association has been able to survive for the past 16 years. All members are encouraged to seek sponsorship for our events and we normally offer a finders' fee to anyone who raises sponsorship money for the Association.

The year 2002 is the year in which the ICCA celebrates its 25th birthday. Our founding meeting took place in Toronto during the World Computer-Chess Championship of 1977, at which Mikhail Botvinnik was the guest of honour.

As a fitting celebration of this anniversary the Association has now formally changed its name to: International Computer Games Association. The title of our Journal has already been changed to reflect our new name, as have the "Advances in Computer Chess" conferences which are now called "Advances in Computer Games". These name changes reflect the broadening of our interest, to encompass all games for which the programming of playing engines requires techniques and methods from Artificial Intelligence.

In 1989 your President founded the Computer Olympiad. After a gap of eight years this event was revived in 2000, thanks to the suggestion of Jonathan Schaeffer and the untiring efforts of Jaap van den Herik and his team in Maastricht. This event was donated to the ICCA in 2000 and now forms part of our activities under our new name. The ICGA plans to bring into our orbit games such as robot soccer and economic games, which can be added to the list of tournaments for future Computer Olympiads as well as providing interesting papers for the technical section of our Journal.

The expansion of the Association's interests into games other than chess is expected to bring some tangible material benefits. Hopefully we will be able to attract many new members from the other games, as we are providing both competitive and publication forums for those interested in programming games other than chess. It is also to be hoped that the Computer Olympiad will grow in size as well as in stature within the AI community, thereby attracting new sponsors for our events.

One immediate improvement in our activities is the expansion of our web site. This may be reached using www.cs.unimaas.nl/icga/ or the more easily remembered www.icga.org. The web site will have a separate section devoted to each game and will hopefully benefit programmers and researchers in every game as they learn the techniques and algorithms used by their colleagues in other games as well as their own. We live in exciting times for enthusiasts of "our" computer games. The level of the strongest chess programs increases steadily each year, by an average of 30 Elo points or thereabouts. Contests between humans and computer programs are becoming more popular in many games. Artificial Intelligence techniques are in use in some of the most popular games played on PCs and game consoles, such as the FIFA soccer games produced by Electronic Arts. The future holds many exciting challenges and achievements for those working in this field.

I would like to thank the outgoing Vice-President, Monty Newborn, for filling that role for the past three years. I would also like to thank Don Beal whose role as Secretary-Treasurer continued into this period, and Hiroyuki Iida who took over from Don Beal and has now been re-elected to serve for the period 2002-2005.

Finally I should like to offer the sincere thanks of the Association to our esteemed Journal editor, Jaap van den Herik, and all of his team at the Universiteit Maastricht. Without them the Association would find it, at the very least, extremely difficult to survive. They have served us very well during the past three years, as in the previous sixteen, and they have indicated their desire to do so in the foreseeable future.