Computer shogi
Encyclopedia
Computer shogi is a field of artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

 concerned with the creation of computer programs which can play shogi
Shogi
, also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan...

. The research and development of shogi software has been carried out mainly by freelance programmers, university research groups and private companies.

Game complexity

Shogi has the distinctive feature of reusing captured pieces. Therefore shogi has a higher branching factor
Branching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....

 than other chess variants. The computer has more positions to examine because each piece in hand can be dropped on many squares. This gives shogi the highest number of legal positions and the highest number of possible games of all the popular chess variants. The higher numbers for shogi mean it is harder to reach the highest levels of play. The number of legal positions and the number of possible games are 2 measures of shogi’s Game complexity
Game complexity
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.-Measures of game complexity:...

.
Game Board Size Legal Positions Possible Games Average Game Length
Chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

64 1047 10123 80
Xiangqi
Xiangqi
Xiangqi is a two-player Chinese board game in the same family as Western chess, chaturanga, shogi, Indian chess and janggi. The present-day form of Xiangqi originated in China and is therefore commonly called Chinese chess in English. Xiangqi is one of the most popular board games in China...

90 1048 10150 95
Shogi
Shogi
, also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan...

81 1071 10226 110

Computers versus humans

In the 1980s, due to the immaturity of the technology in such fields as programming, CPUs and memory
Memory
In psychology, memory is an organism's ability to store, retain, and recall information and experiences. Traditional studies of memory began in the fields of philosophy, including techniques of artificially enhancing memory....

, computer shogi programs took a long time to think, and often made moves for which there was no apparent justification. These programs had the level of an amateur of kyu rank.

In the first decade of the new millennium, computer shogi has taken large steps forward in software and hardware technology. In 2007 champion Yoshiharu Habu estimated the strength of the 2006 world computer shogi champion Bonanza. He wrote in the Nikkei Newspaper evening edition on March 26, 2007 about the match between Bonanza and the 2006 Ryuo Champion Watanabe. Yoshiharu Habu rated Bonanza’s game at the level of 2 dan shoreikai.

In particular, computers are most suited to brute-force calculation, and far outperform humans at the task of finding ways of checkmating from a given position, which involves many fewer possibilities. In games with time limits of 10 seconds from the first move, computers are becoming a tough challenge for even professional shogi players. With the past steady progress of shogi computers as a guide of the future, the prediction is even computers with a large handicap will be unbeatable in the future. Larry Kaufman
Larry Kaufman
Lawrence C. "Larry" Kaufman is a Grandmaster of chess. He is also a mathematics professor and currently lives in Potomac, Maryland. In 2008, as an International Master, Kaufman won the World Senior Championship which automatically earned him the Grandmaster title.A long time researcher in...

, one of the strongest western shogi players said in 2008, “In 10 years I predict a computer will be able to give lance handicap (kyo-ochi) to the Meijin”.

On 23 October 2005 at the 3rd International Shogi Forum the Japan Shogi Association allowed Toshiyuki Moriuchi, 2005 Meijin, to play computer shogi program YSS. Toshiyuki Moriuchi won the game playing 30 seconds per move with a Bishop handicap.

Bonanza Vs Watanabe

The Japan Shogi Association (JSA) gave reigning Ryuo Champion Watanabe permission to compete against the reigning World Computer Shogi Champion Bonanza on 21 March 2007. Daiwa Securities sponsored the match. Hoki Kunihito wrote Bonanza. The computer was an Intel Xeon 2.66 GHz 8 core with 8 gigabytes of memory and 160-gigabyte hard drive. The game was played with 2 hours each and 1 minute byo-yomi per move after that. Those conditions favor Watanabe because longer time limits mean there are fewer mistakes from time pressure. Longer playing time also means human players can make long-term plans beyond the computer’s calculating horizon
Horizon effect
The horizon effect is a problem in artificial intelligence where, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of it, typically a few ply down the game tree...

. The 2 players were not at the same playing level. Watanabe was 2006 Ryuo Champion and Bonanza was at the level of 2 dan shoreikai. Bonanza was a little stronger than before due to program improvements and a faster computer. Watanabe prepared for a weaker Bonanza as Watanabe studied old Bonanza game records.

Bonanza moved first and played fourth file rook anaguma as Watanabe expected. Watanabe thought some of Bonanza’s moves were inferior. However, Watanabe deeply analyzed these moves thinking that maybe the computer saw something that Watanabe did not
see. Watanabe commented after the game that he could have lost if Bonanza had played defensive moves before entering the endgame. But the computer choose to attack immediately instead of taking its time (and using its impressive endgame strategies) which cost it the match. Bonanza resigned after move 112. Hidetchi reviews this game.

After Bonanza’s loss Watanabe commented on computers in his blog, “I thought they still had quite a way to go, but now we have to recognize that they’ve reached the point where they are getting to be a match for professionals.” Ryuo champion Akira Watanabe clarifies his position on computers playing shogi. Yomiuri Shimbun newspaper quoted Akira Watanabe on June 27, 2008. Watanabe said "I think I'll be able to defeat shogi software for the next 10 years". Another indication Bonanza was far below the level of professional Watanabe came 2 months after the match at the May 2007 World Computer Shogi Championship. Bonanza lost to the 2007 World Computer Shogi Champion YSS. Then YSS lost to amateur Kato Yukio in a 15-minute game.

Akara vs Shimizu

The Computer program Akara defeated the women’s Osho champion Shimizu Ichiyo. Akara contained 4 computer engines, Gekisashi, GPS Shogi, Bonanza and YSS. Akara ran on a network of 169 computers. The 4 engines voted on the best moves. Akara selects the move with the most votes. If there is a tie vote then Akara selects Gekisashi’s move. Researchers at the University of Tokyo
University of Tokyo
, abbreviated as , is a major research university located in Tokyo, Japan. The University has 10 faculties with a total of around 30,000 students, 2,100 of whom are foreign. Its five campuses are in Hongō, Komaba, Kashiwa, Shirokane and Nakano. It is considered to be the most prestigious university...

 and the University of Electro-Communications
University of Electro-Communications
The is a national university in the city of Chōfu, Tokyo, Japan. It specialises in the disciplines of computer science, the physical sciences, engineering and technology. It was founded in 1918 .-Graduate schools:*Graduate School of Electro-Communications...

 developed Akara.

Shimizu moved first and resigned in 86 moves after 6 hours and 3 minutes. Shimizu said she was trying to play her best as if she was facing a human player. She played at the University of Tokyo on 11 October 2010. The allotted thinking time per player is 3 hours and 60 seconds byoyomi
Byoyomi
is an extended time control in two-player games, specifically Shogi and Go. The word is borrowed from Japanese; the term literally means "counting the seconds," or more generally, "countdown."...

. 750 fans attended the event. This is the third time since 2005 that the Japan Shogi Association granted permission to a professional to play a computer, and the first victory against a female professional. However, a computer has never defeated a male professional under standard time controls. Hidetchi reviews this game.

Akara aggressively pursued Shimizu from the start of the game. Akara played with a ranging rook strategy and offered an exchange of bishops. Shimizu made a questionable move partway though the game, and Akara went on to win. Ryuo champion, Akira Watanabe, criticized Shimizu’s game. On 19 November 2010, the Daily Yomiuri quoted Watanabe. Watanabe said, "Ms. Shimizu had plenty of chances to win".

Annual CSA tournament exhibition games

The winners of CSA tournaments played exhibition games with strong players. These exhibition games started in 2003.
YearProgramHumanHandicapTimeByoyomiWinner
2003 IS Shogi Pro 5 Dan Katsumata 2 Piece Handicap 25 Min None Computer
2004 YSS Pro 5 Dan Katsumata Rook 25 Min None Computer
2005 Gekisashi Pro 5 Dan Katsumata Bishop 25 Min None Computer
2006 Bonanza Yukio Kato None 15 Min 30 Sec Human
2007 YSS Yukio Kato None 15 Min 30 Sec Human
2008 Tanase Shogi Yukio Kato None 15 Min 30 Sec Computer
2008 Gekisashi Shimizugami Toru None 15 Min 30 Sec Computer
2009 GPS Shogi Amateur champion None 1 hour 1 min Canceled

In each succeeding year, the human competition was stronger to match the stronger programs. Kato Yukio was the Asahi Amateur Meijin champion. Shimizugami Toru was the Amateur Meijin champion. At present, top Shogi programs are currently at a level of lower to middle class professional players.

Computers Bonanza and Akara beat Amateurs Kosaku and Shinoda

On July 24 2011, there was a two game amateur versus computer match. Two computer Shogi programs beat a team of two amateurs. One amateur, Mr. Kosaku, was a Shoreikai three Dan player. The other amateur, Mr. Shinoda, was the 1999 Amateur Ryuo. The allotted time for the amateurs was main time 1 hour and then 3 minutes per move. The allotted time for the computer was main time 25 minutes and then 10 seconds per move.
Game Computer Sente (first) Gote (second) Moves Computer Time Amateur Time Hardware Winner
1 Bonanza Kosaku & Shinoda Bonanza 93 24 min 41 sec 2 hours 2 min 17 processors, 132 cores, 300 GB Bonanza
2 Akara Akara Kosaku & Shinoda 150 25 min 54 sec 1 hour 42 min Intel Xeon W3680 with 6 cores Akara

Programmer tools

  • Shogidokoro is a graphical user interface (GUI) that calls a program to play shogi and displays the moves on a board. Shogidokoro was created in 2007. Shogidokoro uses the Universal Shogi Interface (USI). The USI is an open communication protocol that Shogi programs use to communicate with a user interface. USI was designed by Norwegian computer chess programmer Tord Romstad in 2007. Tord Romstad based USI on Universal Chess Interface
    Universal Chess Interface
    The Universal Chess Interface is an open communication protocol that enables a chess program's engine to communicate with its user interface....

     (UCI). UCI was designed by computer chess programmer Stefan Meyer-Kahlen
    Stefan Meyer-Kahlen
    Stefan Meyer-Kahlen is a German programmer of the computer chess program Shredder. , his program had won 12 titles as World Computer Chess Champion. Four of the titles were blitz championships, and one was a Chess960 championship. Shredder 10 has a rating of 2824 on the November 3, 2007 SSDF...

     in 2000. Shogidokoro can automatically run a tournament between 2 programs. This helps programmers to write shogi programs faster because they can skip writing the user interface part. It is also useful for testing changes to a program. Shogidokoro can be used to play Shogi by adding a Shogi engine to shogidokoro. Some engines that will run under shogidokoro are Blunder, GPS Shogi, Laramie, Lightning, ponanza, Spear, Ssp and TJshogi. Bonanza can also run with an adapter (u2b).

  • WinBoard/XBoard and BCMShogi are other GUIs that support Shogi. This support was added to WinBoard in 2007 by H.G. Muller. WinBoard uses its own protocol (Chess Engine Communication Protocol
    Chess Engine Communication Protocol
    The Chess Engine Communication Protocol is an open communication protocol that enables a chess engine to communicate with its user interface....

    ) to communicate with engines, but can connect to USI engines through the UCI2WB adapter. Engines that can natively support WinBoard protocol are Shokidoki, TJshogi, GNU Shogi and Bonanza. Unlike Shogidokoro, WinBoard is open source, and also available under Linux as XBoard. BCMShogi is a graphical user interface for the USI protocol and the WinBoard shogi protocol.

  • Floodgate is a computer shogi server for computers to compete and receive ratings. Programs running under Shogidokoro can connect to Floodgate. The GPS team created Floodgate. Floodgate started operating continuously in 2008. The most active players have played 4,000 games. From 2008 to 2010, 167 players played 28,000 games on Floodgate. Humans are welcome to play on Floodgate.
{| class="wikitable"

|+Floodgate Annual Highest Rating
|-
! Date!!Program!!Rating
|-
|May 23, 2011||Bonanza_expt||align="right" |3054
|}
  • The annual computer vs computer world shogi championship is organized by the Computer Shogi Association (CSA) of Japan. The computers play automated games through a server. Each program has 25 minutes to complete a game. The first championship was in 1990 with 6 programs. In 2001, it grew to 55 programs. The championship is broadcast on the Internet. At the 19th annual CSA tournament, 4 programs (GPS Shogi, Otsuki Shogi, Monju and KCC Shogi) that had never won a CSA tournament defeated 3 of the previous year’s strongest programs (Bonanza, Gekisashi and YSS). The top three winners of the 2010 CSA tournament are Gekisashi, Shueso and GPS Shogi.

In 2011, Bonkras won the CSA tournament with 5 wins out of 7 games. Bonkras ran on a computer with 3 processors containing 16 cores and 6 gigabytes of memory. Bonanza won second place on a computer with 17 processors containing 132 cores and 300 gigabytes of memory. Shueso won third place. The 2010 CSA winner, Gekisashi, won fourth place. Ponanza won fifth place. GPS Shogi won 6th place on a computer with 263 processors containing 832 cores and 1486 gigabytes of memory.

Computer shogi programs

Components of computer shogi programs:
  • Opening book
    Opening book
    Chess opening book refers either to a book on chess openings, or to a database of chess openings used by chess programs.-Literature:Opening books, which discuss chess openings, are by far the most common type of literature on Chess play...

    : An opening book of moves puts the program in a good position and saves time. The problem is professionals do not always follow an opening sequence as in chess but make different moves to create good formation of pieces.
  • Search algorithm
    Search algorithm
    In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...

    : The Search algorithm that looks ahead more deeply in a sequence of moves allows the program to better evaluate a move. The search is harder in shogi than in chess because of the larger number of possible moves. A program will stop searching when it reaches a stable position. The problem is many positions are unstable because of the drop move.
  • Endgame : The endgame starts when the king is attacked and ends when the game is won. In chess there are fewer pieces which leads to perfect play by endgame databases. In shogi pieces can be dropped so there are no endgame databases. A Tsumeshogi
    Tsumeshogi
    or tsume is the Japanese term for a shogi problem in which the goal is to checkmate the opponent's King. Tsume problems present a situation that might occur in a shogi game, and the solver must find out how to achieve checkmate. It is similar to a chess problem.-Rules:Tsume problems have set...

     solver is used to quickly find mating moves.


Computer shogi programs that have played at the annual World Computer Shogi Championships:
  • Bonanza won first place the first time it was entered in the championships in 2006. Programmer Kunihito Hoki was living in Canada.
  • YSS won in 1997, 2004 and 2007. YSS won 2nd place in 1999, 2000, 2003, 2006 and 3rd place in 1994. Programmer is Hiroshi Yamashita. YSS entered the first time in the 1991 tournament.
  • IS Shogi won in 1998, 2000, 2001 and 2003. Yasushi Tanase was part of the Tokyo University team that wrote IS Shogi.
  • Tanase shogi won 2nd place in 2007 and 2008 also written by Yasushi Tanase.
  • Gekisashi won 2002, 2005, 2008 and 2010. The Gekisashi team is led by Yoshimasa Tsuruoka.
  • KCC Shogi came in second place in 2005 and is from North Korea.
  • Shogi Kakinoki won 2nd place in 1990, 1992, 1993 and 1996 and written by Yoshikazu Kakinoki.
  • Kiwame won in 1992, 1993 and 1994 and written by Shinichirou Kanazawa.
  • Shogi Kanazawa won in 1996 and in 1999 also written by Shinichirou Kanazawa.
  • Morita Shogi
    Morita Shogi 64
    is a Japanese virtual board game for the Nintendo 64. It was released only in Japan in 1998. It is the sequel to Saikyō Habu Shōgi, a launch game for the Nintendo 64....

    won in 1991 and written by Kazurou Morita.
  • Shotest
    Shotest Shogi
    Shotest Shogi is a shogi AI engine made by Jeff Rollason made into a video game for the PC and Xbox Live Arcade developed by AI Factory and Rubicon Development. It is based on the Japanese version of chess Shogi, and provides a 3D environment designed to recreate a traditional Japanese room...

    won 3rd place in 1998, 1999 and written by British programmer Jeff Rollason.
  • Spear a free program written by Reijer Grimbergen has won 9th place of 24 in the 2009 upper division contest.
  • GPS Shogi is free software written by students of the University of Tokyo and won in 2009.


Computer Shogi programs that play in video game systems:
  • Habu Meijin no Omoshiro Shōgi
    Habu Meijin no Omoshiro Shōgi
    is a video game, developed by Access and published by Tomy Corporation, which was released exclusively in Japan in 1995.This game is endorsed/supervised by Yoshiharu Habu.- External links :* at superfamicom.org* at super-famicom.jp - See also :...

    plays on the Super Famicom.
  • Clubhouse Games
    Clubhouse Games
    Clubhouse Games, known in Europe as 42 All-Time Classics and in Japan as , is a compilation video game consisting of card, board, and parlor games developed by Agenda and published by Nintendo for the Nintendo DS handheld video game console...

    includes Shogi plays on the Nintendo DS
    Nintendo DS
    The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...

    .
  • Shotest Shogi
    Shotest Shogi
    Shotest Shogi is a shogi AI engine made by Jeff Rollason made into a video game for the PC and Xbox Live Arcade developed by AI Factory and Rubicon Development. It is based on the Japanese version of chess Shogi, and provides a 3D environment designed to recreate a traditional Japanese room...

    plays on the Xbox
    Xbox
    The Xbox is a sixth-generation video game console manufactured by Microsoft. It was released on November 15, 2001 in North America, February 22, 2002 in Japan, and March 14, 2002 in Australia and Europe and is the predecessor to the Xbox 360. It was Microsoft's first foray into the gaming console...

    .
  • List of shogi video games.


GNU Shogi
GNU Shogi
GNU Shogi is a free software program by the Free Software Foundation that plays Shogi. Although the program is ASCII based, most often it is used in conjunction with XShogi, much as XBoard is used for GNU Chess. Source code is available....

 is a free software program by the Free Software Foundation that plays Shogi.

Restrictions

On 18 September 2005 a Japan Shogi Association professional 5 dan played shogi against a computer. The game was played at the 29th Hokkoku Osho-Cup Shogi Tournament in Komatsu, Japan. The Matsue National College of technology developed the computer program Tacos. Tacos played first and chose the static rook line in the opening. Professional Hashimoto followed the opening line while changing his bishop with the bishop of Tacos. Tacos had a good development with some advantages in the opening and middle game even until move 80. Many amateur players expected Tacos to win. However, professional Hashimoto defended and Tacos played strange moves. Tacos lost.

On 14 October 2005, the Japan Shogi Association banned professional shogi players from competing against a computer. The Japan Shogi Association said the rule is to preserve the dignity of its professionals, and to make the most of computer shogi as a potential business opportunity. The ban prevents the rating of computers relative to professional players. Since 2005, the Japan Shogi Association has permitted three games between professionals and a computer.

Milestones

  • 2005, At the Amateur Ryo tournament, program Gekisashi defeated Eiji Ogawa in a 40 minute game of the first knock out round.
  • 2005, Program Gekisashi defeated amateur 6-dan Shinoda Masato in a 40 minute exhibition game.
  • 2007, Highest rating for a computer on Shogi Club 24 is 2744 for YSS.
  • 2008 May, computer program Tanase Shogi beat Asahi Amateur Meijin title holder Kato Yukio. 75 moves played in 15 minute exhibition game.
  • 2008 May, computer program Gekisashi beat Amateur Meijin Shimizugami Toru. 100 moves played in 15 minute exhibition game.
  • 2008 November, Gekisashi beat Amateur Meijin Shimizugami in a 1 hour game with 1 minute byoyomi
    Byoyomi
    is an extended time control in two-player games, specifically Shogi and Go. The word is borrowed from Japanese; the term literally means "counting the seconds," or more generally, "countdown."...

    .
  • 2010 October, first time a computer beat a Shogi champion. Akara beat the women’s Osho champion Shimizu in 6 hours and 3 minutes.
  • 2011 May, Highest rated player on Shogi Club 24 is computer program Ponanza, rated 3211.
  • 2011 December, Highest rated player on Shogi Club 24 is computer program Bonkras, rated 3314 after 962 games.

See also

  • Shogi
    Shogi
    , also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan...

  • Shogi variant
    Shogi variant
    Many variants of shogi have been developed over the centuries, ranging from some of the largest chess-type games ever played to some of the smallest...

  • Computer Chess
    Computer chess
    Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...

  • Computer Othello
    Computer Othello
    is a reversi-based video arcade game developed and published by Nintendo. It is one of their earliest video arcade games along with Block Fever and after they did release a dedicated console called Color TV Game 6 and a variety of electromechanical arcade games earlier in the 1970s. It was...

  • Computer Go
    Computer Go
    Computer Go is the field of artificial intelligence dedicated to creating a computer program that plays Go, a traditional board game.-Performance:...

  • Computer International Draughts
  • Computer English Draughts

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK