From: Pauli Misikangas CS HELSINKI FI> Date: 15 sep 2000 Subject: Re: Computer's rating On Thu, 14 Sep 2000, Larry Kaufman wrote: > At 04:08 PM 9/14/00 +0100, you wrote: > > >> So the question is: if one of today's best shogi programs were > >> modified as necessary to run on an old IBM xt machine, how > >> well would it play? My own guess would be 10 kyu or even worse, but I've > >> only worked on chess software, not shogi software so I'm not fully > >qualified to say. > >> Shogi programmers reading this, please give us your opinions > >> on this question. > > > >I claim no expertise but this is a hardware question which seems to me to be > >a concern about speed rather than the 'thought' processes of the program > >itself. > > Speed is not the only issue; the limitations of DOS and the size of > memory in the pc back then may also be critical factors for shogi, though > again only a shogi programmer can tell us. As a shogi programmer (I'm the author of "Shocky", the program that came 8th in the last computer shogi championship), I don't think that the size of the memory would be the critical factor for shogi programs. In fact, I would claim that today's top shogi programs require less memory than the best chess programs. This is mainly because top shogi programs are not based on brute-force search as most of the chess programs. Brute-force chess programs search hundreds of thousands of moves per second and store search results for analyzed positions into a huge transposition table (so that if the same position is reached again, one can use the result from the previous search). Since the nodes-per-second rate is very high, also the transposition table needs to be very large (tens of megabytes) in order to be useful. On the other hand, most shogi programs are so called "slow-searchers", and use a lot of time to decide which moves should be searched further. Since the branching factor of shogi is significantly higher in shogi (about 80) than is chess (about 35), searching all moves is simply not possible (with today's hardware). So, we are forced to do "selective search", i.e. take a risk and ignore some moves, to be able to search the most interesting moves deeply enough. In that sense, we could say that today's shogi programs are in the same situation as chess programs were 15 years ago - the hardware is too slow for brute-force and one must use some "intelligent" heuristics. Thus, even with a fast Pentium-III, a typical shogi program searches only 10000-50000 moves per second, and some top programs even less! This means that a shogi program needs a much smaller transposition table than a chess program. If running in a 1000 times slower machine, the node rate would be 10-50 moves/s, and a few kilobytes would be enough for the transposition table (if using reasonable time limits for the search). In addition, having huge opening book libraries is not so important issue in computer shogi than in chess. In fact, the champion program of year 1997 (YSS 7) did not use opening book at all! Also, endgame databases used in computer chess to know the game result when only a few pieces are left are not used in computer shogi in obvious reasons. As a summary, I don't see any reason why a shogi program would need much memory. Of course, I can speak only for myself - I don't know if other shogi programmers have other needs for large memory. But at least Shocky should be able to run in DOS with slight modifications, I think. In fact, the first version of my program was a DOS program. But now to the original question "how well would a top shogi program play in IBM XT?". Because of the selective search used in shogi programs, I think that with a little bit tuning they might play surprisingly well. The usual strategy in shogi programs is to search all moves in the root and increase the level of pruning (skip more moves) when on the deeper levels of the search tree. So, if one would use the heuristics now used near the leaf nodes right from the root, the program would do highly selective (and risky) search. This way, the program might be able to search the important move sequences deeply enough to play reasonably well. But would it still be enough to reach the 10kyu level? I don't know. :-) Pauli Misikangas ------------------------------------------------------------------ Pauli ? +358 9 5652154 (home), +358 9 19144271 (work) Misikangas \\|// Pauli.Misikangas cs Helsinki FI (o o) http://www.cs.helsinki.fi/Pauli.Misikangas ----------oo0-(_)-0oo---------------------------------------------