Reflections On RiscIgo by Bruce Wilcox
Bruce Wilcox is a very strong amateur Go player, author of EzGo and a professional Go software engineer. The following is taken (with Mr. Wilcox's permission) from a mail thread in which he explains his development process in wonderful detail.
Table of contents | Table of diagrams B1 Dead? |
THE PROBLEM:
In late 1993, I was asked by a Japanese company to build a Go program with the following specifics:
- It had to play stronger by three stones than the current strongest copy of Goliath in Japan (which was on SuperNintendo).
- It had to play quickly (Goliath on the SNES was slow).
- It had to fit in 16K RAM and 162K ROM, with 32K of that ROM not available as code space and accessed only in bytes.
- It had to run on the ARM RISC Processor as a stand-alone go engine. They would provide the human interface on SNES, and connect via serial channel to the ARM chip.
- It had to be done in 6 months.
When I got the initial request, my first impulse was to laugh myself silly. What I had to start with was NEMESIS the Go Master, which was arguably 5 or more stones weaker than Goliath, and whose Go engine had previously been trying to stay within 256K ROM and 32K RAM to fit in our own Igo Dojo handheld Go machine. And only six months? Just another project scheduled by marketing. No wonder software is usually delivered late. But the offer was too good to turn down. If there was any chance at all, I had to try.
The first thing I did was see if I could justify it as possible. I mapped how I would spend the RAM budget (described later). I would need a radically different memory design, taking advantage of the 32 bit architecture of the ARM-60 chip. Then I tried to estimate ROM using NEMESIS as a basis. NEMESIS Go code used 162K of code + 15K for patterns + 11K for joseki. But the code was compiled under the Borland C compiler. When compiled for the ARM chip, it was about 15% bigger, or 187K. Since the goal was to fit code in 128K, this was 30% too big. While it was possible to imagine a program fitting in the ROM requirement, it would have to be a complete rewrite both for size, and because it needed to redo all data structures to fit in the RAM limit.
NEMESIS Go engine Code Allocation
Territory tactics 22 group moves 10 Tactics controller 15 link moves 10 Board assessment 13 response controller 9 String + move update 8 game phases moves 8 Group data 8 string moves 4 Go board/utility 6 moyo moves 4 Pattern matching 6 edge moves 3 String tactics 5 territory moves 3 Access data 5 access moves 3 Sector/perimeter data 5 contact fights 1 Link data 4 Joseki processing 4 Link tactics 2 Territory data 2 Edge data 2 Total size = 162K (growing to 187K under ARM60 compiler)
Next I considered the debugging environment. The ARM chip development package had a simulator under DOS that ran very slowly. Testing under it was next to impossible. Debugger boards with a built in ARM chip would be available in Japan, but only if I traveled there, and so were generally not available. And the source level debugger wasn't great. So I wouldn't be able to resort much to assembly code to save on size, since I'd never be able to debug it. Instead I would have to write in C as a DOS version, and switch to compiling my C program for the ARM chip at the last minute.
Finally, having argued plausibly that all of the above would work somehow, I had to decide how I was going to get 5 or more stones stronger at the same time and fit that also into the ROM budget. And keep the speed up with limited caching ability. And do it all in 6 months. Right!
I wrote a summary paper to the customer, explaining each of the above points on December 3, 1993. The first thing I wrote was: My analysis of this project says that it can probably be done, but that due to time constraints and the 128K code limit, there is a risk that the final product may only be slightly better than Goliath NES. These words turned out to be completely right, and the project would run to 12 months instead of 6 (they also weren't ready until 12 months had passed, as it turns out).
THE PLAN:
What was the ace up my sleeve? Without one, this project was sheer lunacy. NEMESIS in Version 4 had lots in common with David Fotland's program Many Faces of Go. Lots of special code for doing tactical analysis. In Version 5, I had experimented with replacing string tactics code with pattern matching. In a way, this experiment was a disaster. NEMESIS V5 was slower and weaker than Version 4 (although it had many useful other improvements). My pattern matcher was not incremental, and was way too slow. But, conceptually the pattern matching tactician was a lot stronger than the previous one. Or so I thought.
If there was to be an ace up my sleeve, it was a pattern matcher based on Fotland's, but even faster and better. I pinned my hopes on that. What would it buy me?
- If it was fast enough, I could substitute patterns for code. Since an average pattern would be just over 16 bytes, one pattern equaled 4 ARM instructions. I expected I could save on code space using patterns, and they could fill up the 32K of non-code ROM.
- Using patterns would increase reliability, since they couldn't cause the program to crash or do anything malign other than match or fail to match.
- With an embedded pattern editor, I could see a mistake, fix it and continue in the same game. It would speed the fix-it loop by making the program interpretive instead of compiled. Writing patterns is much faster than writing code.
- I could afford any number of special case situations, described by patterns.
RESULTS:
When 6 months were up, I had a go-playing program that could fit on the ARM chip, play fast, and wasn't as strong as Goliath yet, though it was stronger than NEMESIS. In 6 more months, it was somewhat stronger than Goliath. It had played 250 games against a rated 10-kyu and gone from taking 9 handicap stones down to taking Black. Since strength deteriorates against a human as the human gains experience in the foibles of the program, this seemed like a pretty good sign. It took 12,000 lines of go engine source (excluding .h and tools), had 3000 patterns and 30 joseki.
While the program was not as strong as hoped, and not done as quickly as hoped, it was stronger than Goliath, fast, and proved that the pattern based system was a viable starting point for further development.
SIDE PROBLEMS ALONG THE WAY:
During first integration, their serial communications code didn't work right. Non-trivial debugging since they didn't speak much English, nor I much Japanese. Eventually it was solved by slowing down communications. Originally I was to send the entire go board image each turn. But that flooded the communications channel. So instead I had to spend 361 bytes of RAM tracking what had already been sent to them. 361 bytes may seem small, but remember I'm trying to stay within 16K RAM.
Once integration was accomplished, I tried to have the program play a game against itself on the ARM, to see if it played exactly the same as it did under DOS. It did, almost. After a hundred moves all the same, it varied for a few moves before returning to the same moves. After much debugging, I discovered that the ARM version, playing through their interface, used a 5 pt komi, whereas the DOS version defaulted to no komi. And at the point the game departed, one side was close to the boundary of "winning big". With komi, it went over that threshold and started playing more conservatively than its DOS counterpart.
Another problem was the mysterious freezing of the program on the ARM chip, whereas it ran perfectly under DOS. Eventually I discovered the compiler did not consider (((char*) ptr) + 1 + 2) to be the same as (((char*) ptr) + 3). It generated bad addressing code in the former case, so I revised my macros to work around the problem.
Despite these difficulties, the port from DOS to ARM went relatively smoothly.
The most onerous difficulty was created by supplying an extra feature. Like Goliath and NEMESIS, RiscIgo could show you a shaded map of what it considered to be under each player's control throughout the game. This display is useful for weaker players, but allowed the customer to see into the program. And like the other programs, and like any kyu player, it made mistakes in its assessment. This lead to the customer wanting to change how the program thinks. This has it good and bad parts, and while sometimes it helps to make the program stronger, sometimes it generates friction between customer and programmer. A few examples are in order. First, consider an empty 19x19 board and Black plays the first move. To RiscIgo, territory is defined as those points surrounded by one player's stones and linkages and the edge, and not touching any enemy living stones. So after the first move, Black "owns" the whole board as territory. Of course this territory is easy to invade and never lasts. So I patched it to suppress such behavior on the 19x19 board. But when Black plays the center point on 9x9, he still owns the whole board. What surprised the customer was when White invades at a 3-3 point, Black's center stone was considered dead.
Well, to RiscIgo, the Black stone was not in contact with any edge, had little running room, and could see no living friendly group. So it was presumed dead (not that it wouldn't play to try to save it). This didn't sit well with the customer's project manager. I argued that the program was not necessarily wrong, and offered to prove it. I asked him to make his stone live, while I played to kill it. He died. The point here being that many situations are up for grabs, and the program's heuristics for assessment were based on a 19x19 board. But the customer could see them, and thus want them changed. It was a serious problem in customer relations. In all fairness, however, the main problem was that the program wasn't 3 stones or more stronger than Goliath. This was just a symptom they could pick on.
RiscIgo Code Allocation in Kbytes
String tactics 9 group moves 10 Go board/Utility 7 response controller 8 Board assessment 7 link moves 5 Pattern matching 5 semeai moves 4 Tactics controller 4 contact fights 4 String+move data 4 edge moves 3 Territory data 4 territory moves 2 Sector/ Perimeter data 3 moyo moves 2 Link data 3 game phase moves 1 Edge data 2 ko moves 1 Access data 2 string moves 1 Joseki processing 2 access moves .5 Link tactics 1 ----------------------- Group/chain data 1 41.5 Eye tactics .2 --------------------------- SNES interface 7 54.2 Various constants 1.5 Patterns 56 Joseki .5 ------------------------------ Total ~162K
NEMESIS / RiscIgo DIFFERENCES:
Much of what NEMESIS did with code, RiscIgo does with patterns.
There was no room for RiscIgo to keep lists of anything around. So whereas NEMESIS kept strings with lists of stones, liberties, etc., RiscIgo only kept a bit map indicating which points were members of strings, groups, territories, etc., and created a particular data structure as needed by rescanning contiguous points.
The biggest code area in NEMESIS was territory tactics. RiscIgo had no such lookahead ability since I had neither time nor space to write it. However, RiscIgo used lots of pattern knowledge to substitute for some tactics.
The biggest move generator areas in NEMESIS were groups and linkages. The same is true of RiscIgo, reflecting the importance of these concepts in Go play. RiscIgo added additional code to handle semeais and ko.
I simplified and speeded up underlying primitives in strings, links, groups and territory.
NEMESIS had no global evaluation function to assess a board. I created one for RiscIgo that was fast enough to afford. As an additional feature, by tinkering mildly with the evaluation function, I could create a program with multiple personalities. The program had different styles of play the user could select (and which made for great graphics in the user interface).
RiscIgo RAM Allocation (Bytes)
- 4,096 control stack and local scratch data
- 1,441 Go board maps (361 intersections of 4 bytes each)
- Basic data (occ, str, link status, chain status)
- 7 string id bits
- 4 link bits (black & white x horizontal & vertical)
- 2 chain bits (black & white)
- 2 occ bits (black ,white , none = empty, both = off edge)
- 1 "been here" bit for scans
- above update automatically incrementally on regular moving
- below assessed data non-incrementally updated by assessment
- refreshes when returning to assessed turn level
- 4 weak link bits (horizontal & vertical x black & white)
- 2 group bits (black & white)
- 2 territory bits (black or white)
- 5 chain id bits
- 2 territory header bits (a unique territory starts here by color)
- 1 weak link updated bit
- Basic data (occ, str, link status, chain status)
- 1,444 Access map (361 points x 2 bytes x 2 colors)
- each color intersection is 2 bytes (updated incrementally)
- 9 bits stone nearest of color to here
- 7 bits distance (only 6 needed)
- each color intersection is 2 bytes (updated incrementally)
- 800 Move list history (400 move limit)
- each move is 16 bits
- 9 bits location
- 4 bits kill directions (needed to retract moves correctly)
- 1 bit ko flag (shows suicide or ko depending upon kill bits)
- 2 bits color of player moving (only 1 bit really needed)
- std game = 250-300 real moves + 100 lookahead moves
- replayability of retracted moves is responsibility of interface
- each move is 16 bits
- 724 copy of current turn top level assessment bits for fast refresh
- 722 Display marks board (for indicating numbers and letters on location)
- 362 Tactic board indicates tactical result cache
- if on occupied pt, is on string name describing string
- if on link pt is on sole unique link pt describing link
- updated at top level of real turn only
- 8 bit tactical value
- described why tactics stopped computation (too deep, ko, etc.)
- described result of tactic for starting player (win/lose)
- 361 tile board indicates tactic cache updating requirements
- updated by assessment
- 8 bit impact rectangle index specifying board part involved
- 254 String: contiguous stones of same color
- Theoretic max. 228. Practical max 127. Avg. max is 75.
- Updated incrementally
- unit size 2 bytes.
- 9 bits name (high pt on board 1...361)
- 2 bits unused
- 4 bits dame count (15 dame maximum)
- 1 bit "big" (stones > 1) flag
- 62 group enclosure data (2 bytes per group)
- 9 bit name of best runnable/enclosable stone of a group
- 4 bits define open running direction from stone
- 1 bit means is enclosed
- 1 bit means can be enclosed in 1 move
- 1 bit means within foe sector line
- 62 copy of group enclosure data
- 62 chains (collection of connected strings using pseudo-linkages)
- Practical max 31. In theory could be in the 30s, maybe 40s.
- Updated by assessment
- unit size 2 bytes
- 9 bits name (high point of chain)
- 3 bits safety assessment value
- 1 Might breakout bit
- 1 In semeai bit
- 1 Big group (6 or more stones)
- 1 Has many liberties
- 62 copy of chains data
- 42 - 21 edge boundary zones (two groups or 1 group + corner or 2 corners)
- Practical limit 20
- Unit size 2 bytes
- updated by assessment
- 9 bit 1st line base
- 2 bit direction code for along and onto board
- 5 bit distance of gap
- 42 copy of edge boundary zone data from current turn top level
- 31 group association
- 1 per chain
- updated by assessment
- names chain index of master chain for each chain
- (all chains in a group index to master, his is the id of the group)
- (groups are chains associated by capture of foe)
- 5 bits chain id
- 3 unused bits
- 31 copy of group association
The "copy of" data is used to reassert the top level global evaluation of a turn after running a lookahead sequence. Evaluation data is not incremental, and done only at some interesting terminal node.
(Note: sometimes I bring other Go programs I have written into the discussion of RiscIgo. POGO was my first program, written in LISP in the 1970's. NEMESIS was written by me in the 1980s, and I stopped working on it in 1992 and have nothing further to do with that program. Ego is my next generation program after RiscIgo, not yet released.
BASIC INCREMENTAL DATA STRUCTURES:
Basic data is updated incrementally (that is, the bits are always correct after each real or hypothetical move). Some of it can be suppressed during specific kinds of tactical lookahead. For strings, territory, groups and chains, the set of points involved in the unit is computed by scanning points and testing for the presence of the appropriate bit (the ones corresponding to occupation, chain status, or territory status) in the mask for that point.
Strings:
For strings, NEMESIS kept lists of stones, liberties and touching enemy stones, along with the counts of each. RiscIgo keeps just the liberty count, where to find the canonical start (the point of the string most north and east on the board) of the string, and whether the string is "big" (at least 2 stones) or not. Updating is incremental, and simple.
Links:
For every point changing occupancy RiscIgo checks related nearby points to see if the link bit needs changing. Special code is devoted to this purpose. Setting the link bit is thus incremental, but no data about the link is computed until assessment. In Ego, pattern matching has been sped up enough to duplicate the speed of the special code, so linkage detection is done strictly using patterns.
Chains:
A point is a black chain member (and similarly for white) if:
- black occupies it
- black has more touching adjacent stones than white
- if both have 2 touching stones, a black stone is north of the pt
- if both have 0-1 touching stones, black has more diagonal stones than white.
Setting the bit is done incrementally, but no data is acquired about the chain until an assessment is needed. Discussion of assessment deferred until later.
Access:
POGO, NEMESIS, and RiscIgo do not use influence. Influence, as it is traditionally implemented, computes the degree of control over a point. If a point has +10 influence, it means black controls it with some measure of 10. But whether this was achieved by distant far black stones and even more distant white stones, or by close black stones and somewhat close white stones is not discriminated by this measure. Access maintains the discrimination of how far away each player's stones are from a point. I incrementally keep track of access. An access map specifies for a point, what point of a color is nearest to this point, and how far away it is (how many moves would it take to join a solid string line between the two points assuming you are not allowed to cross enemy linkages). Whenever a move is played, it generates a list of points that change occupancy, and points that change link status. For friendly access, a wave from this stone propagates to adjacent points as long as the access distance from this stone is less than that already existing on the new point. This is referred to as "spinning". For foe access, access is "ripped" out and then respun. For example, if Black plays a point, then the access for White through that point is retrieved (the white base stone and distance). For all propagated adjacent points with higher access coming from the same white base stone, access is cleared. Each point which is not cleared, is added to a list to respin. Then each is respun once, generating a layer of newly spun points into the cleared zone. Each layer is respun until no new layers are generated.
Access is used to find, among other things,
- enclosure status (can a group access distant points or friends of another group?).
- sector lines bounding a group
- Territory (points which have no access from a living enemy stone).
- How to handle a moyo (e.g., to defend, find a deep point in the moyo, then retrieve the enemy access stone to that point and play a move to block that stone from moving toward the moyo).
- Define game phase based on worst access of either player
9+: early opening 8: mid opening 7: late opening
6 : early midgame 5: mid midgame 4: late midgame
3 : early endgame 2: mid endgame 1: late endgame
6. the closest stone to a point, if you want to crawl toward that point (moyo attack).
PATTERN MATCHING:
Pattern matching is used for almost everything in RiscIgo. It is used in lookeahead, global move generation, and most of group safety evaluation is done using patterns.
In NEMESIS pattern matches were done on request (no caching or incremental updating). Patterns were divided into types, e.g., good shape, linkage defense of a specific type of linkage, real eyes. To request a match you specified the type, and the points used to orient the match. The matcher returned a board point and a value as its answer. Usually the answer was a move suggestion and an associated value, but the value could also be descriptor bits (e.g., this move cannot be cut), or an index into a sequence database (i.e., play out this sequence).
Patterns were described as text, and converted into an internal binary decision tree. A simple pattern is the following: LENS 2 d3 c4 < d4 empty c3 empty c3 5 > < d4 white c3 empty c3 33 > ENDLENS This says that lens type 2 (diagonal connection defense) given the two endpoints of the diagonal connection, has two recognizable FIELDS (in <>). A field is a collection of points, which if occupied in specific ways, comprises a pattern. Fields were used in POGO, NEMESIS, RISCIGO and EGO.
If D4 is empty and C3 is empty, then return c3/5. If d4 is White and C3 is empty, return c3/33. Any number of points anywhere on the board could be contained in a field. The program to the set of all fields and built a decision tree out of it. In this example, C3-Empty would be at the root of the tree, with two leaves d4-empty and d4-white. The program walked the tree and performed the tests indicated (empty or white) during a pattern match.
The tests that could be specified included: WHITE, BLACK, EDGE, EMPTY, NOTWHITE, NOTBLACK, NOTEDGE, which were simple occupation tests. Optimizations to avoid naming lots of points included:
- BLACK8, EMPTY8, WHITE8 (center as designated and the 8 points around it empty)
- ANY1, ANY2, ANY3 (the 9x9 field named must be empty or off the board, except for the number of points named can and must be of the count named. E.g. Any2 means the 9x9 field must contain exactly 2 stones of any color. All remaining points must be empty or off the edge).
- ADJ0, ADJ1, ADJ2, (the center and immediately touching neighbors must be empty or off the board, except for the number of points named can and must be of the stone count named. E.g, ADJ2 means that 2 of the 5 points designate (the center and 4 touching points), must be occupied by stones).
- EMPTY25 (a 5x5 field named must all be empty or off board)
- MARK, NOTMARK (the designated center must or must not have a marker bit set on it. ) One might mark territory points for an eye pattern match, for example.)
- DAMEG1, DAMEG2, DAMEG3, DAMEL2, DAMEL3, DAMEL4, (liberties must match)
- LIVEWHITE, LIVEBLACK (stone must be of a living group)
- HYPOCONNECT (the original endpoints would survive an attempt to disconnect them if this move were played)
- HYPOKILL (the original endpoint would be killed if this move were played)
- FRIENDEDG (along the edge, a friendly stone is next)
- TEST (Perform a test against a global variable. Test can require ==, >, < of the value. Global variables include: game phase, time status, last motive, territory status.
- RSLT (answer is a move-value pair)
- NUMRSLT (answer is a number-value pair for sequences)
While the decision tree walk to match a pattern had been fine in NEMESIS 4.7, it was too slow to use during lookahead, as I discovered in NEMESIS 5. So for RiscIgo I returned to considering how Fotland had done it. According to his description in "Knowledge Representation in The Many Faces of Go (Feb 27, 1993)":
"Each pattern is 8x8, where each point is specified as black, white, empty, don't care, white or empty, black or empty, or black or white. Each pattern has a set of attributes with it that must also match. For example, 'the stone at (4,2) must be alive', or 'the stone at (2,5) must have at least 2 liberties'. Each pattern has a move tree attached that is used for full board lookahead. Internally a pattern is stored as three 8 byte arrays, one for black points, one for white, and one for empty. For example a black point in the pattern is indicated by setting the appropriate bit in the black array. Black or Empty is indicated by setting bits in both the black and empty arrays. Don't care is indicated by setting corresponding bits in all 3 arrays. Each pattern needs to be matched at each point on the board, in 8 orientations, and with colors reversed. Rather than rotate the patterns, I rotate the board before comparing. Color reversal is handled by reversing the black and white arrays. Once I have 3 arrays extracted from the board for a particular position, the pattern match is simple. Just bitwise AND the corresponding Black, white, and empty arrays; bitwise OR the three results, and if the result is all ones, then there is a match. After I find a matching pattern I check that the attributes specified by the pattern match..... use an 8 bit hash function to reduce the number of patterns examined .... the program spends about 1.5% of its time in pattern matching."
Fotland used pattern matching to find global move sequences to evaluate, so he kept matches incrementally up to date. While I intended to be able to locate global moves and sequences, I also intended to use it during tactical lookahead. MOST of RiscIgo's time is expected to be in pattern matching. So I altered his algorithm given the following considerations:
- Keeping the data cached didn't make sense. Most of pattern matching would be done during lookahead. Each move in lookahead, being close to the previous move, would invalidate all useful cache data. So keeping a cache would just take time and provide little benefit.
- I didn't want to have to enter all manner of sequences and partial sequences. If the matcher was fast enough, I could just match a move, then match on that move to get the next move and so on. This would find all explicit sequences that I had entered move by move, and find implicit ones generated by moves I had added without sequences in mind.
- Based on my previous programs, I wanted to match given a specific purpose. So I would match naming a set of focus points and a pattern class. This would cut the number of patterns matched to just those relevant for this purpose, and in just the relevant orientations and colors. I didn't need a hash code. I didn't do color reversal. I did only one color (the color of the focus stone is "friend" or if the focus is empty, the color of the player to move is "friend"). And I did only the orientations needed. A small knights move is defined by two endpoints, requiring a total of two orientation matches, one from each endpoint. For string tactics, I matched from a liberty of a string, but always oriented toward a stone of that string. This usually meant just 2 orientations.
- I could optimize Fotland's matcher by having bits in a pattern represent the absence of something instead of the presence of something. This allowed me to skip the OR stage of his matcher. And I explicit represented bits for the edge, so I could match a pattern without having to consider where it was placed.
For me, a pattern match uses a base board description extracted from the 5x5 or 7x7 field around a point. The point itself is excluded since its occupation status is already known. That conveniently means 24 points or 48 points (multiples of 8). If any corresponding bits between the base and a pattern match (survive the AND), the pattern FAILS to match. If all bits fail to correspond, up to 2 additional arbitrary tests of designated field points are performed. If those succeed, the pattern then MATCHES. The last pattern in a class is guaranteed to match, with value 0.
When the matcher is called, it is given a set of points and orientations to match using a pattern class. The best (or all) matches found for those points are returned. For example I might provide all boundary points of enemy territory in the endgame to match the "best endgame attack" class, and the program returns the suggestion(s) of the best places to play.
Patterns are checked in priority order, and only the highest absolute priority for a point is returned. Lower priority patterns are not checked, unless the pattern class requires all matches be checked and reported.
The center of a pattern always has a predefined occupancy status, and the points around it are usually treated as having some directional orientation up (e.g., toward foe stone, toward boundary link).
Because the pattern masks represent points that MUST NOT be occupied, corresponding bits in multiple masks are used to designate when the point MUST be of some value. Representable values are:
- Black = Not White & Not Empty & Not Edge
- White = Not Black & Not Empty & Not Edge
- Empty = Not Black & Not White & Not Edge
- Edge = Not Black & Not White & Not Empty.
- Don't Care = 0 in all fields (may be off board for all we care)
- Not black (white or empty)
- Not white (black or empty)
- Not empty (black or white or off board)
- Not edge (on board) = 0 in all fields and not edge bit
While Black, White, and Empty must have bits corresponding to the entire field, Edge (off the board) does not. Because an edge extends in a straight line, it is sufficient to check only points in a straight line from the focus spreading out in each of 4 directions. The entire 7x7 max region uses 12 bits to represent edge boundaries.
The board base description is built once for matching all appropriate patterns to some focus in some orientation. It must be rebuilt for each new focus and new orientation.
Given a board description in base1, base2 and base3, the actual match per pattern is just:
while (1){ pptr += WORDS_IN_PATTERN; // shift to next pattern; // perform 5x5 match 1st if (pptr[0] & base1) continue; if (pptr[1] & base2) continue; if (pptr[2] & base3) continue; // dynamically load 7x7 base extension description if 1st time // perform 7x7 remainder match if (pptr[3] & base4) continue; if (pptr[4] & base5) continue; if (pptr[5] & base6) continue; // now perform specific tests, and if pattern survives, store answer.. ... }
On a 32-bit oriented machine, in assembly language, this is very fast per pattern.
Possible test conditions are:
- dame < 2, dame < 3, dame < 4, dame > 1, dame > 2, dame > 3,
- edgeline = 1, edgeline != 1, not on plate of specific group,
- friend < 6 away, edge line > 3, not on territory point, foe can't safely play,
- friend territory, foe territory, foe > 5 away, eye cannot be collapsed,
- friend > 6 away, no foe neighbor in atari
Each pattern has a DONT-MATCH bit. If this bit is on, then when this pattern is matched, it means don't allow this point to be matched (by keeping it on a local list), and continue matching. This allows me to note situations where moves shouldn't match.
Additionally, I can structure collections of patterns into "Globs". A glob is a collection of patterns. If the first pattern in the glob matches, then it skips over remaining patterns in the glob and continues matching. Globs can also be joined together. The effect is if the first pattern matches, then skip the 2nd header and continue matching inside the rest of the glob. If the first header fails, the second is usually a pattern that matches all situations, and all remaining patterns in the glob are skipped. This allows me to set up a precondition board condition for matching patterns in a glob. If the precondition fails to match, then the patterns are ignored. This substitutes rapidly for a hash code. For example, there are 143 patterns for string attack in 7 globs. If the preconditions all failed, then it would take 14 patterns scanned to fail them all (each glob 1st header precondition fails, the 2nd header always matches and skips all the rest of the glob).
All patterns are entered using a GUI pattern editor. Given a type number, 54 patterns from it fit on a page. Click on one, and it magnifies and displays the full detail, ready for editing and testing, after which you can resume a game. An encoded pattern takes either 12 or 24 bytes (depending on field size and whether embedded tests are used).
There are about 100 pattern types as follows (some generate multiple classes based on linkage type or territory count): openDirection, press, run, enclose, semeai, friend eExtend, foe extend, LadderAttack, Contact attack, contact defend, diagonal contact, External eye, unstable territory boundary, revise planned move, fill a liberty, invade, self-atari reject, split territory into pieces, form links from, attack foe moyo, defend friend moyo, react without thought, big midgame edge moves, obvious follow-up sequence data for lookahead, attack a territory boundary, stop the wriggling of a dead group, desperate group trying to live, do I care about saving this stone, connect through enemy link (watari), is there a link here, Great Wall joseki, eye value for territories from 1-7 points, general eye value for unrecognized small territories, eye value for dead stones, is this link obviously secure, endgame attack, endgame defend, is this a weak contact fight situation, linkage attack move, move here requires updating these linkage points, link defense move, string just reduced to 2 liberties, tactical lookahead reflex moves, seki shapes,
The classes with the most patterns are:
- contact attack (162), string tactics attack (143),
- string tactics defense (139), react to foe move without thought (135),
- single skip link defense (135), obvious link defense sequences (114).
Average pattern size is 18 bytes for the 3,000 patterns in the database. In a sample game playing against itself on a 486 DX 2/50, Ego, using a somewhat faster pattern matcher, can play at a rate of 10 moves a minute. This involves 1410 calls to match a point in some orientation for some class per turn, checking 140 patterns per match. Some 44 million patterns were matched against the board during that game.
GLOBAL EVALUATION:
Global evaluation proceeds using the incremental basic data, without any tactical lookahead. Speed is essential, so tactics are not used. Pattern matching substitutes in most cases for tactics. Sometimes it's wrong.
- Clear all global assessment bits. These include chain id bits, group bits, territory header bits and weak link bits. The top 16 bits of a point's occupation data area assessment bits.
- Find the chains. This consists of a sweep over the board looking for contiguous collections of points with the same chain bit on.
- Find all interesting edge areas. Pairs of consecutive (but not necessary contiguous) edge links involving two distinct chains are interesting.
- Sweep the board and set the approriate territory bit for each point not reachable by the opponent (using reach map).
- Adjust territory. To avoid black claiming the whole board with the first move, if a territory point is "too far" from a friendly stone, the territory is ripped back to the nearest linkage boundaries.
- Find all territories. Find the contiguous points all having the same territory bit on. Choose one point from the territory and turn on the territory header for it. The friendly reach map for this point should have a base visible to the chain owning this territory. Some points which are territory are not reachable by the friend. An example is a dead enemy group with eyespace, where points of the eyespace are not visible via reach data to the killer.
- Assess the life status of chains. Pass one does an initial determination for all chains. Each chain is its own group. After this pass, for all chains that are not alive, a conflict assessor tries to decide who dies (including if semeai or seki is involved). This assessor iterates over the groups until no group changes status. As chains get declared dead, the enclosing chains are merged into groups running through the dead stones. Territories are recomputed for the groups that die, so that each pass has the correct territory data.
- Assess the game value, computing territory, potential territory, and bonuses for each side. Keep track of the distribution of reach values, to decide game phase. Potential territory are points where one side has reach < 5 and has closer reach than the other. Potential far from foe (reach > 9) is treated as territory. Potential not close to foe (reach > 4) is worth 4 times potential where foe is close. Bonuses come from weak groups which are not yet dead. Bonus is based on life status of group and size of group. Thus making a move which changes the life status of a group up or down a notch is worth a bonus. Bonus is also based on style of computer opponent selected. Influence and territory are combined eventually. If the game phase is early on, 8 potential = 1 territory. Later in the game, 16 potential = 1 territory. Player style choice affects these conversions.
INITIAL CHAIN SAFETY EVALUATION:
For each chain, its reach to the rest of the board is analyzed, in combination with pattern matching, resulting in a determination of ENCLOSED, ENCLOSABLE IN ONE MOVE, WITHIN SECTOR LINE, or OPEN. Each territory it controls is evaluated for the number of eyes it is worth using a variety of pattern matches. Some are on the territory points, and some are on the boundaries to determine their stability.
- A chain is ALIVE:
- two eyes.
- A chain is PRESENTLY_ALIVE:
- enough moyo (points with far reach from foe) and the separate potential for 2 eyes
- OPEN with enough possible eyes or edge expansions
- has enough big edge expansions (2 pt skips)
- has many possible eyes
- A chain is LIVABLE:
- has potential eyes and edge expansions >= 2
- has some eye and some moyo
- A chain is PRESENTLY STABLE:
- if it is outside of any sector line.
- A chain is SICKLY:
- has an eye and edge expansion room
- is not ENCLOSED and has some edge room
- just has moyo
- A chain is BAD:
- is just not ENCLOSED
- A chain is DEAD WITH AJI:
- just has some edge expansions
- has more than one possible eye
- A chain is DEAD otherwise.
But, if a chain seems dead, additional edge pattern analysis is then run, and if successful patterns are found, status is changed to SICKLY.
TACTICS
There is a general tactics controller, to provide the lookahead framework. Within that framework, depending upon the search type, it can call modules for string, link, eye, or "obvious" global sequences. Upon arrival at a new board position, all moves RiscIgo might play from here are generated in priority order. Before move generators for the specific search types are called, a generator "obvious reflex" generator is called. Whenever RiscIgo returns to a position, RiscIgo decides whether to reorder or ignore the suggestions, but RiscIgo never generates new moves. Except for the "obvious" global sequences, searches are simple succeed/fail and use no alpha-beta. Obvious sequence searches keep minimax values.
The results of success or failure of tactics are kept in a cache, but the actual move returned is discarded immediately (limited RAM, remember). So if RiscIgo decides that it wants to play a move based on a tactical lookahead, in general it must redo that lookahead a second time to get the answer. The cache keeps a number from 1-32, designating what board area fragment, if played in, would require the search to be redone. A search always fits within some fragment, even if that fragment is the entire board.
STRING TACTICS:
String tactics generates moves against a "virtual string". It takes the designated target string, and determines which other strings are pattern connected to it (provided there is time to keep them joined before getting captured). All liberties of the target complex are then pattern matched to:
- locate eyes (16 patterns)
- locate trick plays (16 sacrifice tesuji against the connections)
- locate ordinary plays (roughly 150 attack and 150 defend patterns)
The search is aware of snapbacks (so even if the string can be captured, if it can snap back to life again, it isn't captured yet). It will terminate on going too deep for the attacker, if it gets two eyes, if the attacker tries to continue a failing ladder, or the liberty count for the defender gets high enough. Additionally, if a target is being attacked as a counterattack from some original target, if the target complex gets more liberties than the original target, the counter attack is stopped. The patterns range from the very general (fill any liberty), to the more specific (fill liberties in this order), to the very specific (play a geta move or some clever tesuji or make a 2nd eye).
LINKAGE TACTICS:
Pattern matching determines the initial moves required to attempt to cut or connect the linkage. When those patterns cease, additional patterns mark the cutting strings to counter attack, and string tactics is called to try to kill or save them.
OBVIOUS SEQUENCE TACTICS:
Pattern matching is done on the most recent move, and the move before that, to determine the obvious responses to the recent move, and the follow-ups to the previous move that should be tried. When no more moves are generated or the depth limit is reached, a global evaluation is performed and the score returned. 16 lines of C.
EYE TACTICS:
Pattern matching the eye point determines all moves and results. It uses the same 65 patterns that global evaluation uses when judging the eye value of a single point territory. 10 lines of C.
LIFE AND DEATH TACTICS:
0 lines of C. (i.e., not done).
JOSEKI:
RiscIgo has several joseki databases, varying from half board to small corner. It matches without cacheing, by looking at the move sequence as played in a designated rectangle, and following the joseki tree for that rectangle (decoded and rotated into the correct place on the board). If a match is found in a bigger rectangle, then joseki processing for that area stops with the answer(s). Otherwise it switches to the next smaller rectangle and tries again. Due to space considerations, only 30 joseki are recognized. In addition, RiscIgo uses the pattern matcher to generate moves whenever it wants to play the Great Wall Opening. 7 patterns generate the wall itself, and 28 patterns handle follow-up attacks on corners to make use of the wall.
Enough for now. If you have comments or questions, feel free to partake.
Comments
TsuQ: I notice you mention having used 361 bytes to store what had been last sent. As a note on memory efficiency, you can store 5 ternary values in a single byte if memory is at a premium using a 1's, 3's, 9's 27's and 81's place which can each take the value of 0, 1 and 2 - fairly ideal for go positions.