ক‫ع‬ͷ‫ع‬ේͷࢦ͠ख͔ΒҙਤΛಡΈऔΔۚࢠ ஌ద֓ཁίϯϐϡʔλ͸ਓؒͷ஌ೳΛӽ͑ΔͩΖ͏ক‫Ͱع‬ίϯϐϡʔλ͕ A ‫ڃ‬ീஈʹউͭ·Ͱʹ͔? ν Σ ε ɼক ‫ ع‬ɼғ ‫ Ͳ ͳ ޟ‬ͷ ࢥ ߟ ή ʔ Ϝ ʹࢸͬͨ [5] ‫ݪ‬ಈྗͱͯ͠͸ɼ‫ہ‬໘ͷྑ͠ѱ͠Λ‫ݶ‬ఆ͢Ε͹ଟ͘ͷਓ͕͜ͷ໰Λߠఆతʹߟ͑௚‫ײ‬తʹ൑அ͢Δ‫ܗ‬੎൑அྗͷվળ͕༗ྗͰ͋ΔΑ͏ʹͳ͍ͬͯΔɽ1997 ೥ʹνΣεͰ DeepΔɽख़ୡऀͷ‫ع‬ේ͔ΒϓϩάϥϜ͕‫ܗ‬੎൑அΛ

Blue [1] ͕উརΛ͓͞Ίͨࡍʹ͸ɼઌΛಡΉ୳ֶͿํ๏ʹ͍ͭͯɼ؆୯ʹ঺հ͍ͨ͠ɽࡧೳྗ͕༏Ε͍ͯΔͱཧղ͞Ε͕ͨɼ2013 ೥ʹ

1 ήʔϜͷઌΛಡΉࢥߟক ‫ع‬ɾν Σ ε ͳ Ͳ ͷ ࢥ ߟ ή ʔ Ϝ Λ ‫ ͢ ڀ ݚ‬ΔήʔϜϓϩάϥϛϯάͷ෼໺͸ɼ‫͍ڧ‬ϓϩάϥ͜ͱɼධՁؔ਺͸༧૝͞ΕΔ֤‫ہ‬໘ͷྑ͠ѱ͠Λ௚‫ײ‬తʹ൑அ͢Δ໾ׂΛ୲͏ɽϜΛ࡞Δ͜ͱ͸։ൃऀͷເͰ͋Δͱ͍͏͚ͩͰͳ͘ɼਓ޻஌ೳͷ੒ՌΛଌΔ୊ࡐͱͯ͠‫͔͘ݹ‬Β‫ߦ͕ڀݚ‬ΘΕ͖ͯͨɽήʔϜͷϧʔϧΛ‫ࢉܭ‬

先手根MaxAMin 47<67‫Ͱ্ػ‬ද‫͢ݱ‬Δ͜ͱ͸؆୯Ͱ͋Δʹ΋͔͔ΘΒͣɼ࣮ࡍʹউͭͨΊʹྑ͍ࢦ͠खΛબ͹ͤΔ͜

47

先手‫͢ݱ࠶Ͱ্ػࢉܭ‬Δ͜ͱʹͩ͜ΘΒͣʹɼ‫ࢉܭ‬‫ʹػ‬దͨ͠ࢥߟํ๏Λ௥‫͢ٻ‬Δ͜ͱͰ‫͍ڧ‬ϓϩά ϥ Ϝ ͕ ։ ൃ ͞ Ε ͨ ɽҎ Լ ʹ ঺ հ ͢ Δʮ ୳ ࡧ ʯ枝Max

67 67>6547

ͱ͸େมʹ೉͍ͨ͠ΊͰ͋Δɽক‫ʹع‬ઌߦͨ͠νΣεͷ‫Ͱڀݚ‬͸ɼਓؒͷϓϨΠϠͷߟ͑ํΛ

ゲB

後手

後手

葉

50

2470

25

47

1567

65

Aとと B どちらを指すと先手は得？
どちらを指すと先手は得？

ਤ 1. ήʔϜ໦ͱϛχϚοΫε୳ࡧͱʮධՁؔ਺ʯͷ૊Έ߹Θ͕ͤɼͦͷओྲྀͷ࿮ධՁؔ਺͸ɼೖྗ͞Εͨ‫ہ‬໘ʹରԠ͢Δ਺஋૊ΈͰ͋Δ 1 ɽ୳ࡧ͸ࣗ෼ͱ૬खͷࢦ͠खͷ૊(ධՁ஋ͱ‫ )Ϳݺ‬Λग़ྗ͠ɼධՁ஋͸ઌख (‫ޙ‬ख)Έ߹ΘͤΛߟ͑ͯະདྷΛγϛϡϨʔγϣϯ͢Δ͕উͪ΍͍͢΄Ͳਖ਼ (ෛ) ʹେ͖͍΋ͷͱ͢Δɽ

将棋の棋譜の指し手から意図を読み取る

119119ক ‫ ع‬ͷ ୯ ७ ͳ ྫ Ͱʮ ઌ ख ͷ ۨ ͷ ຕ ਺ − ‫ ޙ‬ख ͷ͘ͳΔ͜ͱ͕஌ΒΕ͍ͯΔɽҰํͰɼධՁؔ਺ۨͷຕ਺ʯͱ͍͏ධՁؔ਺͸ɼۨಘ͍ͯ͠ΔํͰ‫ہ‬໘ͷ෼ੳʹ࣌ؒΛ͔͚Δͱ୳ࡧ͸஗͘ͳ͕‫͏͍ͱ͍ڧ‬ήʔϜͷੑ࣭Λ൓өͨ͠΋ͷͰ͋Γɼ୳ࡧͰਂ͘ಡΊͳ͘ͳΔͱ͍͏τϨʔυΦΔɽ(ເ෺‫Ͱޠ‬͸͋Δ͕) ΋͠ධՁؔ਺͕‫׬‬શʹϑ͕͋ΔɽͦͷͨΊ͕ۨऔΒΕͦ͏͔ͳͲͷ֤ਖ਼͚͠Ε͹ɼҰखઌͷ‫ہ‬໘ͷධՁ஋͕࠷େͱͳධՁ߲໨ΛɼධՁؔ਺Ͱ൑அ͢Δ΂͖͔୳ࡧͰ

Δࢦख͕࠷ળखͱ෼͔Δɽ࣮ࡍʹ͸ɼ‫࣮ݱ‬ͷධΧόʔ͢΂͖͔ʹ͍ͭͯͷҰൠతͳࢦ਑͸஌ΒՁؔ਺͸‫ࠩޡ‬Λ‫ؚ‬ΉͷͰɼҰख͚ͩͰ͸ͳ͘૬Εͯͳ͍ɽखͷԠख΍ͦͷઌ΋‫ؚ‬ΊͯධՁ͢Δ΄͏͕ਖ਼֬୳ࡧͱධՁؔ਺Λ͜ͷΑ͏ʹ෼཭ͨ͠ͱ͢ΔͰ͋ΔɽͦͷͨΊʹਤ 1 ͷΑ͏ʹ‫ہ‬໘Λ௖఺ɼͱɼ୳ࡧʹ͓͍ͯ͸Ұఆ࣌ؒͰਂ͘ಡΉ͜ͱɼࢦ͠खΛลͱͨ͠άϥϑΛԾ૝తʹ࡞੒͢Δɽ΋͘͠͸ಉ͜͡ͱͰ͋Δ͕Ұఆͷ࣭ͷ݁ՌΛૣධՁ஋ͷ֓೦΋֦ு͠ɼ༿Ͱ͸ධՁؔ਺ͷग़ྗ͘ಘΔ͜ͱ͕໨ඪͱͳΔɽ෯ (≈ ‫ہ‬໘͋ͨΓͷΛͦͷ··༻͍Δ͕ɼ಺෦અ఺Ͱ͸ͦͷख൪ͷ߹๏खͷ਺) ͕ b Ͱਂ͕͞ d ͷҰ༷ͳήʔϜ໦ཱ৔Ͱ࠷ળͷࢠ‫ہ‬໘ͷධՁ஋ͱ࠶‫ؼ‬తʹఆٛ͢ΛԾఆ͢Δͱ bd ‫ݸ‬ͷ༿ͷ๚໰͕ඞཁͱͳΔ͕ɼΔ ɽͦ Ε ͸ ɼઌ ख ൪ Ͱ ͸ ࢠ ͷ ධ Ձ ஋ ͷ ࠷ େ ஋ ɼෆཁͳࢬͷ୳ࡧΛ࡟‫͢ݮ‬Δ͜ͱͰɼࢦ਺ͷఈ͋‫ޙ‬ख൪Ͱ͸࠷খ஋ΛͱΔͱ‫͖Ͱࢉܭ‬ΔͷͰɼϛΔ͍͸‫ݞ‬Λ‫ݮ‬Β͢͜ͱ͕Ͱ͖Δɽ௚‫ײ‬తʹ͸ɼχϚοΫε୳ࡧͱ‫ݺ‬͹ΕΔɽઌʹྫʹ‫ۨͨ͛ڍ‬͋Δ෦෼໦ʹ͍ͭͯઙ͘୳ࡧͯ͠΋ਂ͘୳ࡧ͠ͷຕ਺Λ਺͑ΔධՁؔ਺Ͱ͸ฏԺͳ‫ہ‬໘ͱࣗ෼ͯ΋ධՁ஋͕΄ͱΜͲมΘΒͳ͚Ε͹ɼͦͷ෦ͷ͕ۨऔΒΕͦ͏ͳ‫ہ‬໘Λ۠ผͰ͖ͳ͍͕ɼ୳෼Λਂ͘୳ࡧ͢Δඞཁ͸ͳ͍ͩΖ͏ɽ‫ݹ‬యతͳࡧͷաఔͰ૬ख͕ࣗ෼ͷۨΛऔͬͨ‫ޙ‬ͷ‫ہ‬໘Ͱαβ ࢬ‫מ‬͸ಉ݁͡ՌΛ bd/2 ఔ౓ͰಘΔ͕ɼ‫ݱ‬୅͸ͦͷ෼ධՁ͕Լ͕ΔͷͰɼ݁Ռͱ͕ͯۨ͠औͰ͸༷ʑͳࢬ‫מ‬Γ͕༻͍ΒΕ୳ࡧۭؒ͸͞ΒʹΒΕͦ͏ͳҰखલͷ‫ہ‬໘ͷධՁ஋΋௿͘ͳΔɽେ෯ʹ࡟‫͞ݮ‬Ε͍ͯΔ [4]ɽ·ͨ෼ࢄɾฒྻ‫ࢉܭ‬͜ͷΑ͏ͳཧ༝Ͱɼਂ͘୳ࡧ͢Ε͹ͦΕ͚ͩ‫ڧ‬΋༗ޮͰ͋Δ [5]ɽ2 ‫ع‬ේ͔ΒධՁؔ਺Λֶश͢ΔධՁؔ਺ΛͲͷΑ͏ʹ࡞੒͢Δ΂͖͔ʹ͍ͭͱ ‫ ظ‬଴ ͞ Ε ͯ ͍ Δ ɽν Σ ε Ͱ ΋ 1980 ೥ ୅ ࠒ ͔ͯ͸ɼൺֱత‫͕ڀݚ‬গͳ͘ɼෳ਺ͷήʔϜͰ࣮ΒࣅͨΑ͏ͳΞΠσΞ͕ࢄൃతʹࢼΈΒΕ͖ͯ੷ͷ͋Δํ๏͸ཱ֬͞Ε͍ͯͳ͍ɽධՁؔ਺͸ͨͳ͔Ͱɼ࣮ࡍʹ੒ՌΛ͋͛Δ·Ͱͷٕज़తࠔຊ࣭తʹήʔϜຖʹ࡞੒͢Δඞཁ͕͋ΔͨΊɼ೉ͳͲɼৄࡉ͸จ‫[ ݙ‬3] Λࢀর͞Ε͍ͨɽήʔϜͷੑ࣭࣍ୈͰద͢Δख๏͕ҟͳΓ͏Δɽ͜ͷख๏Ͱ͸ɼධՁؔ਺ͷྑ͞ʹ͍ͭͯɼ୳࠷ۙʹͳͬͯক‫عͰع‬ේͷࢦखΛ‫ͯ͠ͱࢣڭ‬ࡧͰબ͹ΕΔࢦख͕ϓϩ‫Ͳͳ࢜ع‬ख़ୡऀ͕બΜ਺ઍສͱ͍͏‫ن‬໛ͷύϥϝʔλΛࣗಈௐ੔͢ΔͩࢦखͱҰக͢Δ΄Ͳྑ͍ͱ͍͏ԾఆΛ͓͘ɽख๏͕։ൃ͞ΕɼଞͷήʔϜͰ΋༗ޮͰ͋Ζ͏ͦͷ͏͑Ͱɼख़ୡऀ͕બΜͩࢦखͷ‫ه‬࿥Ͱ͋Δ120120

東京大学大学院情報学環紀要情報学研究№89౦‫ژ‬େֶେֶӃ৘ใֶ‫ل؀‬ཁ ৘ใֶ‫ ڀݚ‬No. 89‫ع‬ේͱͷࠩҟΛද͢ҎԼͷࣜΛ࠷খԽ͢Δ: p∈P m∈MpT (s(p.dp , w ) − s(p.m, w )) .

͜͜Ͱɼw ͸ධՁؔ਺ͷύϥϝʔλΛද͢ϕΫʹ͍ͭͯ਺͑ͨ΋ͷͰ͋Δɽ͢ͳΘͪɼϓϩ‫ع‬࢜ͷࢦ͠खΑΓ (‫͘ߴ )ͯͬޡ‬ධՁͨ͠ࢦ͠खͷ਺Λେ·͔ʹද͢ɽͳ͓ɼ‫ޙ‬ख൪ͷ‫ہ‬໘Ͱ͸ූ߸Λม͑ͯରԠ͢Δɽτϧ (า 1 ຕͷՁ஋΍ɼઌख‫ ͕ۄ‬8 ീͰ͔ͭۚ͜ͷֶशͰඞਢͷ෦෼͸ɼ‫ع‬ේͷࢦ͠खͷ‫ہ‬

͕ 7 ീʹஔ͔Ε͍ͯΔՁ஋ͳͲ) Ͱɼ‫಺ހׅ‬ͷ໘Λͦͷ··ධՁؔ਺ͰධՁ͢ΔͷͰ͸ͳ͘ɼࠨଆ s(p.dp , w ) ͸‫ع‬ේͷ‫ہ‬໘ p Ͱࢦ͞Εͨࢦͦ͠ͷ‫ہ‬໘Λ୳ࡧͨ͠ධՁ஋Λ༻͍Δͱ͍͏఺Ͱ

ख dp Λύϥϝʔλ w ͷධՁؔ਺Λ࢖ͬͯ୳ࡧ͋Δɽ͜ͷ୳ࡧ͕ਂ͍΄Ͳɼ‫ع‬ේͷࢦ͠खͷҙͯ͠ಘͨධՁɼӈଆͷ s(p.m, w ) ͸ಉ͡‫ہ‬໘ p Ͱਤͷਪఆ͕ΑΓਖ਼֬ʹͳΔ͕ɼ໿ 5 ສͷ‫ع‬ේΛࢦ͞Εͳ͔ͬͨࢦ͠खͷҰͭ m ʹର͢Δಉ༷ॲཧ͢Δඞཁ͕͋Δֶश࣌ؒͷ౎߹͔Β‫ݱ‬ঢ়ͰͷධՁͰ͋Δɽؔ਺ T (x) ͸ࠨӈ൓సͤͨ͞γ͸ 1, 2 ख (ͱ ۨ ͷ औ Γ ߹ ͍) ఔ ౓ ͠ ͔ ಡ Ή ͜ ͱάϞ Π υ ؔ ਺ 1/(1 + eax ) ͳͷͰ͜ΕΛ֊ஈ͕ؔͰ͖͍ͯͳ͍ɽ࣮ࡍͷର‫Ͱہ‬͸༗ྗͳల։Λ਺ͱߟ͑Δͱɼࣜશମ͸ɼ‫಺ހׅ‬ͷ͕ࠩෛͱͳ

20 खҎ্ઌ·ͰಡΉ͜ͱΛߟ͑Δͱɼֶश࣌ʹΔ‫਺ݸ‬Λɼֶशର৅ͷ‫ہ‬໘ͷू߹ P ͷ֤‫ہ‬໘ p͸΄Μͷઙ͍ࢥߟͰ‫ع‬ේͷҙਤΛ૝૾͍ͯ͠ΔͰɼϓϩ‫͕࢜ع‬બ͹ͳ͔ͬͨࢦ͠खͷू߹ Mp͜ͱʹ૬౰͢Δɽ

3 ‫ࡏݱ‬ͷ՝୊ͱਓͱͷ‫ڠ‬ௐʹ޲͚ͯύϥϝʔλௐ੔ͷࣗಈԽʹΑΓɼධՁؔ਺ͰཁʹͳΔͩΖ͏ɽ༻͍ΔධՁ߲໨Λେ෯ʹ૿΍͢͜ͱ͕Մೳͱ࠷‫ʹޙ‬ɼਓͱ‫ڠ‬ௐ͢ΔͨΊʹ͸ɼࢦ͠खΛબͳͬͨɽ2003 ೥ͷ࣌఺Ͱ͸ 100 ສఔ౓ͷௐ੔ͰΜͩഎ‫ܠ‬Λઆ໌͢Δೳྗ΋ඞཁͰ͋Δɽ‫ࡏݱ‬ͷ΋ ࠔ ೉ ͕ ͋ ͬ ͨ ͷ ʹ ର ͠ [6]ɼ‫ Ͱ ࡏ ݱ‬͸ ਺ ઍ ສক‫ع‬ϓϩάϥϜ͸ະ஌ͷ‫ہ‬໘Ͱ΋ฏ‫ۉ‬తʹ͸ྑ͔ΒԯͷΦʔμͷύϥϝʔλ͔Β༗ޮͳ΋ͷͷ͍ࢦ͠खΛબͿ͜ͱ͕Ͱ͖ΔΑ͏ʹͳ͕ͬͨɼΈௐ੔ͨ͠ධՁؔ਺͕࣮ࡍʹক‫ع‬ϓϩάϥϜͰͦͷϓϩάϥϜͷࢥߟํ๏͸ਓؒͱ͔ͳΓ཭Ε༻͍ΒΕ͍ͯΔɽ͜ͷධՁ߲໨ͷେ‫ن‬໛ԽʹΑ͍ͯΔ͜ͱ͔Βɼࢦ͠खͱ͍͏݁࿦ʹ͍ͨͬͨΓɼධՁ͸ਖ਼֬ʹͳͬͨɽཧ༝Λਓ͕ؒਪଌ͢Δ͜ͱ΋؆୯Ͱ͸ͳ͍ɽ‫ع‬ҰํͰɼ‫ػ‬ցֶश͸શͯͷ՝୊Λղܾͨ͠Θ࢜ͱϓϩάϥϜ͕ྗΛ߹Θͤͯର‫͢ہ‬Δͱ͍͏͚Ͱ͸ͳ͘ɼྑ͍ධՁؔ਺Λ࡞ͬͯ΋ɼ୳ࡧͷঢ়‫گ‬Λ૝ఆ͢Δͱɼର౳ͷཱ৔Ͱ૬ஊͯ͠ྑ͍ޮ཰͕૬खʹྼΕ͹উ཰͸མͪΔɽ·ͨɼධՁखΛ୳͢͜ͱ͸೉͘͠ɼ‫͕࢜ع‬ओମͰࢦͯ͠ิؔ਺ͷֶशͷաఔͰͷ୳ࡧͷ‫ڧ‬Խ΋ඞཁͰ͋ॿతʹϓϩάϥϜͷධՁ΋֬ೝ͢ΔελΠϧ͔ΔɽͦͷͨΊɼͦΕͧΕผʹൃలͨ͠୳ࡧͱධͦΕͱ΋ϓϩάϥϜʹࢦ͠खΛҰ೚͢Δ͔ͱ͍Ձؔ਺Λಉ࣌ʹѻ͍ɼֶशதͷ΋ͷΛ‫ؚ‬Ή‫ݸ‬ʑ͏‫͏·ͯͬ͠ͳͱ܎ؔͳ୺ۃ‬ɽ‫ݱ‬৔Ͱ৴པ͞ΕͷධՁؔ਺ͷ‫ݸ‬ੑʹదͨ͠୳ࡧΛߦ͏ख๏͕ॏΔਓ޻஌ೳγεςϜΛ࣮‫͢ݱ‬ΔͨΊʹ͸ɼ͜ͷ

将棋の棋譜の指し手から意図を読み取るক‫ع‬ͷ‫ع‬ේͷࢦ͠ख͔ΒҙਤΛಡΈऔΔ121121Α͏ͳ໰୊Λղܾͯ͠Ώ͘͜ͱ΋·ͨࠓ‫ޙ‬ͷ՝୊Ͱ͋Δɽம
1 ͳ͓ғ‫ޟ‬ϓϩάϥϜͰ͸ɼϞϯςΧϧϩ໦୳ࡧͱ͍͏ཚ਺Λ༻͍Δٕ๏͕༗ྗ͕ͩɼͪ͜Β΋ਓؒͷࢥߟํ๏Λ໛฿ͨ͠΋ͷͱ͸‫[ ͍͕͍ͨݴ‬2]ɽ

ࢀߟจ‫ݙ‬[1] M. Campbell, A. J. Hoane, Jr., and F.-h. Hsu. Deep Blue. Artificial Intelligence, 134(1–2):57–83, Jan.
2002.
[2] S. Gelly, L. Kocsis, M. Schoenauer, M. Sebag, D. Silver, C. Szepesvári, and O. Teytaud. The grandchallenge of computer go: Monte carlo tree search and extensions. Commun. ACM, 55(3):106–113, Mar.
2012.
[3] K. Hoki and T. Kaneko. Large-scale optimization for evaluation functions with minimax search. J. Artif.
Intell. Res. (JAIR), 49:527–568, 2014.
[4] K. Hoki and M. Muramatsu. Efficiency of three forward-pruning techniques in shogi: Futility pruning,null-move pruning, and late move reduction (LMR). Entertainment Computing, 3(3):51–57, 2012.
[5] ۚࢠ, ాத. ଟ਺ͷ‫ػࢉܭ‬Λ‫ͨ͠༻׆‬ήʔϜ໦୳ࡧٕज़ͷਐา–ࡾӜ߂ߦീஈͱ GPS ক‫ͱع‬ͷର‫ہ‬ΛৼΓฦͬ
ͯ–. ৘ใॲཧ, 54(9):914–922, 2013.

[6] ۚࢠ, ాத, ࢁ‫ޱ‬, ઒߹. ۨͷؔ܎Λར༻ͨ͠ক‫ع‬ͷධՁؔ਺. ୈ 8 ճήʔϜϓϩάϥϛϯά ϫʔΫγϣοϓ, pp.
14–21, Nov. 2003.

ۚࢠ ஌దʢ͔Ͷ͜ ͱ΋Ώ͖ʣ‫ࡏݱ‬ͷॴଐ: ৘ใֶ‫ ؀‬૯߹෼ੳ৘ใֶίʔε౦‫ژ‬େֶେֶӃ૯߹จԽ‫ڀݚ‬Պത࢜՝ఔमྃɽത࢜ʢֶज़ʣɽಉେֶେֶӃ૯߹จԽ‫ڀݚ‬Պॿखɼॿ‫ڭ‬ɼ।‫ڭ‬तΛ‫ͯܦ‬ɼ2015 ೥ΑΓ৘ใֶ‫؀‬।‫ڭ‬तɽ৘ใॲཧֶձɼਓ޻஌ೳֶձɼ೔ຊιϑτ΢ΣΞՊֶձɼ
ACMɽ2003 ೥ࠒΑΓɼΦʔϓϯιʔεͷক‫ع‬ϓϩάϥϜͰ͋Δ GPS ক‫ع‬ͷ։ൃʹࢀՃɽήʔϜϓϩάϥϛϯάɼ୳ࡧɼ‫ػ‬ցֶशɼਓ޻஌ೳʹ‫ڵ‬ຯΛ࣋ͭɽ৘ใॲཧֶձ࿦จ৆ (2013, 2007), ಉ૑ཱ 50प೥‫ه‬೦࿦จදজ (2010)ɼಉࢁԼ‫ه‬೦‫ڀݚ‬৆ (2008)ɼACM-ICPC Coach Award (2013) ड৆ɽ122

122

東京大学大学院情報学環紀要

情報学研究№89౦‫ژ‬େֶେֶӃ৘ใֶ‫ل؀‬ཁ ৘ใֶ‫ ڀݚ‬No. 89