Shogi en informatique

Le développement d'un logiciel de shogi capable de battre les meilleurs joueurs japonais est un problème de l'informatique qui a été atteint dans les années 2010. Moins connu que le problème de la conception de forts programmes de go, il est néanmoins nettement plus difficile de programmer un bon logiciel de shogi que de programmer un logiciel d'échecs ; de fait les premiers succès des programmes de shogi face à des professionnels du plus haut niveau ont eu lieu près de 20 ans après le match entre Garry Kasparov et Deep Blue.

Logiciel de shogi

Le premier match officiel entre un programme et un joueur professionnel, Akira Watanabe, a eu lieu en 2007 et a été remporté par le joueur humain^[1]. La première victoire d'un programme informatique contre un professionnel, en l'occurrence la joueuse professionnelle Ichiyo Shimizu, date de 2010^[2]. Le programme le plus performant était elmo (en) jusqu'en 2017 avant d'être largement battu par AlphaZero^[3].

Complexité

La complexité (en) du shogi est très élevée par rapport à celle de la plupart des autres jeux. Le shogi a en effet la particularité de réutiliser les pièces capturées. Ainsi à chaque coup, il y a plus de possibilités qu'aux échecs. L'ordinateur doit ainsi examiner plus de positions afin de tenir compte des parachutages. Parmi les variantes régionales des échecs, c'est donc au shogi qu'il y a le plus de parties possibles.

Jeu	Taille du plateau	Nombre de pièces	Nombre de pièces différentes	Nombre de positions légales	Nombre de parties possibles	Durée moyenne d'une partie (en nombre de coups)
Échecs[a]	64	32	6	1047	10123	40[4]
Xiangqi	90	32	7	1048	10150	95
Shogi	81	40	8	1071	10226	140[5]
Go[6]	361	Jusqu'à 361	1	10171	10360	150

Championnat du monde des programmes de shogi

La Computer Shogi Association (CSA) organise chaque année depuis 1990 un championnat du monde des programmes de shogi^[7]. La cadence est de 25 minutes par joueur. En 1990, seuls 6 programmes ont participé ; en 2001 55 programmes différents ont pris part à la compétition. En 2009 quatre programmes (GPS Shogi, Otsuki Shogi, Monju et KCC Shogi) qui n'avaient jamais remporté de tournoi CSA ont battu trois des meilleurs programmes de l'année précédente (Bonanza, Gekisashi et YSS)^[8]. Il est à noter que des expériences ont montré que les programmes Bonanza, GPS Shogi et YSS, qui ont tous été champions du monde, sont plus forts lorsqu'ils jouent en consultation avec choix du coup majoritaire que lorsqu'ils jouent individuellement^[9].

Vainqueur des championnats du monde CSA des logiciels de shogi

	Année	Développeur	Programme	Nombre de victoires / nombre de parties jouées
1	1990	Nobuhiro Yoshimura	Eisei Meijin	5/5
2	1991	Kazurou Morita	Morita Shogi 3	7/8
3	1992	Log corp.	Kiwame	5/7
4	1993	Log corp.	Kiwame II	7/7
5	1994	Shinichirou Kanazawa	Kiwame 2.1	6/7
6	1996	Shinichirou Kanazawa	Kanazawa Shogi	7/7
7	1997	Hiroshi Yamashita	YSS 7.0	7/7
8	1998	Yasushi Tanase	IS Shogi	6/7
9	1999	Shinichirou Kanazawa	Kanazawa Shogi	6/7
10	2000	Yasushi Tanase	IS Shogi	5/7
11	2001	Yasushi Tanase	IS Shogi	9/9
12	2002	University of Tokyo	Gekisashi	6/7
13	2003	Yasushi Tanase	IS Shogi	6/7
14	2004	Hiroshi Yamashita	YSS 7.0	6/7
15	2005	Gekisashi Team	Gekisashi	7/7
16	2006	Kunihito Hoki	Bonanza	6/7
17	2007	Hiroshi Yamashita	YSS 7.0	6/7
18	2008	Gekisashi Team	Gekisashi	6/7
19	2009	GPS Team	GPS Shogi	6/7
20	2010[10]	Gekisashi Team	Gekisashi	6/7
21	2011[11]	Eikyu Ito	Bonkras	5/7
22	2012	GPS Team	GPS Shogi	6/7
23	2013	Kunihito Hoki	Bonanza	5/7
24	2014	Osaka City University Mathematical Engineering Laboratory	Apery	5/7
25	2015	Issei Yamamoto	Ponanza	7/7
26	2016	Issei Yamamoto	Ponanza	7/7
27	2017	Makoto Takizawa	elmo (en)	7/7
28	2018	Barrel house	Hefeweizen	6/7
29	2019	Motohiro Isozaki	YaneuraOu	5/6[12]

Matchs entre humains et ordinateurs

Dans les années 1980, en raison des faibles capacités des mémoires et des processeurs, les programmes de shogi jouaient lentement et avaient un niveau faible. Un domaine particulier pour lequel les logiciels de shogi ont un avantage sur les joueurs humains est celui de la résolution de tsume shogis, qui se prêtent beaucoup mieux à une approche par force brute ; de fait un jeu de tsume shogi faisait partie dès 1983 du catalogue de la SG-1000.

Le niveau des programmes a grandement augmenté au cours de la première décennie des années 2000. Le 23 octobre 2005 lors du 3^e International Shogi Forum, la fédération japonaise de shogi autorise Toshiyuki Moriuchi à affronter le logiciel YSS avec une cadence de 30 secondes par coup et un handicap (en) d'un fou^[13].

En 2007, Yoshiharu Habu a estimé la force du logiciel Bonanza qui avait remporté le championnat du monde des logiciels l'année précédente ; dans un article du Nihon Keizai Shimbun du 26 mars 2007 concernant le match entre Akira Watanabe et Bonanza, Habu a estimé Bonanza au rang de deuxième dan. En 1996 le même Habu avait annoncé qu'un ordinateur pourrait le battre en 2015^[14]. En 2011, le développeur de Bonkras affirmait que les meilleurs programmes de shogi étaient aussi fort qu'un professionnel de niveau intermédiaire^[15].

Restrictions

Le 18 septembre 2005, le joueur professionnel 5^e dan Takanori Hashimoto joua une partie contre le programme Tacos, développé au sein du Collège doctoral de sciences et techniques de Hokuriku. Tacos prit l'avantage durant l'ouverture et le milieu de partie mais ne sut pas percer la défense d'Hashimoto, qui finit par l'emporter^[16]. Le 14 octobre 2005, la fédération japonaise interdit aux joueurs professionnels d'affronter des logiciels de shogi, afin de préserver la dignité des professionnels^[17]. Cette interdiction est ensuite maintenue sous la présidence de Kunio Yonenaga de 2008 à 2012.

Match d'exhibition homme-machine du CSA (2003–2009)

Les programmes vainqueurs du championnat CSA obtiennent le droit de se mesurer à de forts joueurs humains ; ces matchs se sont tenus de 2003 à 2009^[18].

Année	Programme	Joueur humain	Handicap	Cadence	Byo yomi	Vainqueur
2003	IS Shogi	Katsumata (5e dan professionnel)	2 pièces	25 min	Aucun	Ordinateur
2004	YSS	Katsumata (5e dan professionnel)	Tour	25 min	Aucun	Ordinateur
2005	Gekisashi	Katsumata (5e dan professionnel)	Fou	25 min	Aucun	Ordinateur
2006	Bonanza	Yukio Kato (Meijin amateur Asahi)	Aucun	15 min	30 s	Humain
2007	YSS	Yukio Kato (Meijin amateur Asahi)	Aucun	15 min	30 s	Humain
2008	Tanase Shogi	Yukio Kato (Meijin amateur Asahi)	Aucun	15 min	30 s	Ordinateur
2008	Gekisashi	Toru Shimizugami (Meijin amateur)	Aucun	15 min	30 s	Ordinateur
2009	GPS Shogi	–	Aucun	1 heure	1 min	Annulé

Match entre Akara et Shimizu

En 2010, le programme Akara l'emporte face à la joueuse professionnel Ichiyo Shimizu après que la fédération japonaise a donné son aval pour la confrontation. Akara agrégeait les coups proposés par les quatre logiciels Gekisashi, GPS Shogi, Bonanza et YSS ; le coup effectivement joué étant le coup proposé majoritairement (et celui de Gekisashi en cas d'égalité).

Shimizu joua le premier coup de la partie et perdit en 86 coups le 11 octobre 2010 au terme d'un peu plus de 6 heures de jeu suivi en direct par 750 personnes (la cadence étant de 3 heures par joueur suivies d'un byo yomi d'une minute par coup)^[19]. Cependant le jeu de Shimizu a été critiqué et il a été dit que le niveau d'Akara était encore à ce stade inférieur à celui des meilleurs professionnels masculins^[20].

Bonanza et Akara contre deux amateurs forts (2011)

Le 24 juillet 2011 eut lieu un match par équipe de deux entre les programmes Akara et Bonanza d'une part, et d'autre part les amateurs Kosaku (qui à l'époque passait l'examen pour devenir professionnel) et Shinoda (qui avait remporté le Ryuo amateur en 1999). Les amateurs jouaient en consultation et ont perdu le match sur le score de 0 victoires à 2^{[21], [22],[23]}

Partie	Programme	Sente	Gote	Nombre de coups	Temps de reflexion du programme	Temps de réflexion des joueurs	Hardware	Vainqueur
1	Bonanza	Kosaku & Shinoda	Bonanza	93	24 min 41 s	2 heures 2 min	17 processeurs, 132 cœurs, 300 GB	Bonanza
2	Akara	Akara	Kosaku & Shinoda	150	25 min 54 s	1 heures 42 min	Intel Xeon W3680 6 cœurs	Akara

Bonkras contre Yonenaga

Le 21 décembre 2011 eut lieu un match entre le programme Bonkras et le Meijin 1993 Kunio Yonenaga après que celui-ci a pris sa retraite. La cadence était de 15 minutes par joueur, suivies d'un byo yomi d'une minute par coup ; la partie dura un peu plus d'une heure et Yonenaga abandonna après 85 coups. Le premier coup de Yonenaga fut un coup de roi, coup inhabituel typique d'une stratégie anti-ordinateur (en) visant à sortir le logiciel de son catalogue de joseki. Le 14 janvier 2012, Bonkras battit de nouveau Yonenaga lors du premier Denou-sen. La cadence était cette fois de 3 heures par joueur suivies d'un byo yomi d'une minute par coup. Bonkras l'emporte après 4 heures et 29 minutes^[24],[25]

Denou-sen 2013

Le Denou-sen est un match entre 5 hommes et 5 machines, sponsorisé par Niconico. Les parties sont retransmises en live^[26]. Les programmes sélectionnés sont les précédents vainqueurs du championnat du monde des ordinateurs.

Parties

Date	Sente	Gote	Nombre de coups	Temps de réflexion (joueur humain)	Temps de réflexion (machine)	Vainqueur
23 mars	Kōru Abe (en)	Shueso	113	3 heures, 1 minute	3 heures, 15 minutes	Humain
30 mars	Ponanza	Shin'ichi Satō (en)	141	3 heures, 59 minutes	3 heures, 31 minutes	Ordinateur
6 avril	Kōhei Funae (en)	Tsutsukana	184	3 heures, 59 minutes	3 heures, 27 minutes	Ordinateur
13 avril	Puella Alpha	Yasuaki Tsukada	230	3 heures, 29 minutes	2 heures, 19 minutes	Nulle
20 avril	Hiroyuki Miura	GPS Shogi[27]	102	3 heures, 59 minutes	2 heures, 7 minutes	Ordinateur

Denou-sen 2014

Un match entre 5 humains et 5 machines a été organisé entre le 15 mars et le 12 avril 2014^[28],[29].

Parties^[30]

Date	Sente	Gote	Nombre de coups	Temps de réflexion (joueur humain)	Temps de réflexion (machine)	Vainqueur
15 mars	Tatsuya Sugai	Shueso	98[31]	4 heures, 39 minute	4 heures, 1 minute	Ordinateur
22 mars	Yaneuraou	Shinya Satō	95[32]	5 heures, 0 minutes	3 heures, 27 minutes	Ordinateur
29 mars	Masayuki Toyoshima	YSS	83[33]	2 heures, 8 minutes	3 heures, 15 minutes	Humain
5 avril	Tsutsukana	Taku Morishita	135[34]	4 heures, 48 minutes	3 heures, 56 minutes	Ordinateur
12 avril	Nobuyuki Yashiki	Ponanza	130[35]	5 heures, 0 minutes	4 heures, 51 minutes	Ordinateur

Match entre Elmo et AlphaZero

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Computer shogi » (voir la liste des auteurs).

Parties

Humains contre ordinateurs

• (en) [vidéo] « Bonanza - Watanabe (premier match officiel professionnel contre machine, 21 mars 2007) », sur YouTube
• (en) [vidéo] « Shimizu contre le logiciel Akara (11 octobre 2010) », sur YouTube.

Ordinateurs contre ordinateurs

• (ja) [vidéo] « Elmo - AlphaZero n°14, sélectionnée par Yoshiharu Habu », sur YouTube
• (ja) [vidéo] « Elmo - AlphaZero n°18, sélectionnée par Yoshiharu Habu », sur YouTube
• (ja) [vidéo] « Elmo - AlphaZero n°32, sélectionnée par Yoshiharu Habu », sur YouTube
• (ja) [vidéo] « Elmo - AlphaZero n°52, sélectionnée par Yoshiharu Habu », sur YouTube
• (ja) [vidéo] « Elmo - AlphaZero n°81, sélectionnée par Yoshiharu Habu », sur YouTube

Notes

1. Pour plus de détails, voir l'article Nombre de Shannon.

Références

1. (en) [vidéo] « Bonanza - Watanabe (21 mars 2007, premier match officiel professionnel contre machine) », sur YouTube.
2. (en) [vidéo] « Shimizu contre le logiciel Akara (11 octobre 2010) », sur YouTube.
3. (en) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou et al., « Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm », 5 décembre 2017.
4. « statistiques d'échecs », sur chessgames.com (consulté le 15 août 2022)
5. Xiaohong Wan, Daisuke Takano, Takeshi Asamizuya; et al. (2012). "Developing intuition: Neural correlates of cognitive-skill learning in caudate nucleus". Journal of Neuroscience 28: 17492–17501.
6. Allis 1994 * Victor Allis, Searching for Solutions in Games and Artificial Intelligence, Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands, 1994, PDF (ISBN 90-90-07488-0, lire en ligne)
7. « Computer Shogi Association »
8. Reijer Grimbergen, « Upset at the 19th CSA Computer Shogi Championship »
9. (en) Takuya Obata, Takuya Sugiyama, Kunihito Hoki et Takeshi Ito, « Consultation Algorithm for Computer Shogi: Move Decisions by Majority », Computer Games,‎ 2011 (DOI 10.1007/978-3-642-17928-0_15, présentation en ligne).
10. « Winners of 2010 CSA tournament », Computer Shogi Association
11. « Winners of 2011 CSA tournament », Computer Shogi Association
12. « The 29th World Computer Shogi Championship », sur www2.computer-shogi.org (consulté le 7 mai 2021)
13. (ja) Junichi Takada, « Computer versus Human Shogi Games »
14. (en) Takenobu Takizawa et Reijer Grimbergen, Computers and games: Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Berlin, T. Anthony Marsland, 2001 (ISBN 3-540-43080-6, lire en ligne), p. 440 :

    « When asked in 1996 when he(Habu) thought a computer would beat him, his clear answer was “2015” »

15. Tomoko Otake, « Shogi showdown for supercomputer », Japan Times,‎ 2 novembre 2011 (lire en ligne, consulté le 23 novembre 2011).
16. « Hashimoto vs Tacos in 2005 », Japan Advanced Institute of Science and Technology
17. « Shogi pros warned not to play computers », The Japan Times,‎ 16 octobre 2005 (lire en ligne, consulté le 28 novembre 2011)
18. Reijer Grimbergen, « Report on the Annual Computer Shogi Championships »
19. « Shogi computer beats female champ Shimizu », The Mainichi Newspapers,‎ 12 octobre 2010 (lire en ligne)
20. « Will shogi software beat male pros? », The Daily Yomiuri,‎ 19 novembre 2010 (lire en ligne)
21. (ja) « The University of Electro-Communications », 3 août 2011
22. (ja) « Shogi programs crush Amateurs », The Asahi Shimbun,‎ 2 août 2011 (lire en ligne)
23. (ja) « Museum of Abstract Strategy Games », 3 août 2011
24. « Fujitsu's Shogi Software Tops Former Shogi Champion Kunio Yonenaga », Fujitsu, 16 janvier 2012 (consulté le 22 janvier 2012)
25. (en) Eikyu Ito, « Bonkras evaluated its game with Yonenaga in January 2012 » (consulté le 3 février 2012).
26. (ja) Niconico, « Shogi Electronic Kings Battle channel » (consulté le 17 février 2013)
27. « GPS Shogi » , sur Graduate School of Arts and Sciences, University of Tokyo
28. (ja) « ja:｢第3回将棋電王戦｣記者発表会の模様 - 'Daisankai Shōgi Denōsen' Kisha Happyōkai no Moyō » [« "3rd Denou-sen" Press Conference »], Japan Shogi Association,‎ 21 août 2013 (consulté le 31 décembre 2013)
29. (ja) « ja:｢第３回将棋電王戦｣出場棋士決定! - 'Daisankai Shōgi Denōsen' Shutsujō Kishi Kettei! » [« "3rd Denou-sen" Participating Shogi Professional Decided »], Japan Shogi Association,‎ 10 octobre 2013 (consulté le 18 décembre 2014)
30. (ja) « Den War », Niwango, Inc. (consulté le 31 décembre 2013)
31. (ja) « Game Sugai Tatsuya Shueso » (consulté le 16 mars 2014)
32. (ja) « Game Yaneuraou Sato Shinya » (consulté le 23 mars 2014)
33. (ja) « Game Toyoshima Masayuki YSS » (consulté le 31 mars 2014)
34. (ja) « Game Tsutsukana Morishita Taku » (consulté le 6 avril 2014)
35. (ja) « Game Yashiki Nobuyuki Ponanza » (consulté le 13 avril 2014)

• Portail de l'informatique théorique
• Portail des jeux