Df-pn探索による6×6 TRAXの解析

全文

(1)Vol.2016-GI-35 No.7 2016/3/8. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. Df-pn ୳ࡧʹΑΔ 6×6 TRAX ͷղੳ ‫ ݪ܂‬࿨ਓ1,a). ‫ ాח‬խ࿨1. தౡ ຑҥ1. ੢୩ ୴1. ੁ‫ ݪ‬ਅ1,b). อ໦ ๜ਔ1,c). ֓ཁɿೋਓྵ࿨‫׬‬શ৘ใήʔϜͷ TRAX Λɼdf-pn ୳ࡧΛ༻͍ͯղੳͨ͠ɽ൫໘ͷେ͖͞Λ 6x6 ʹ੍‫͠ݶ‬ ͨ৔߹ʹɼॳ‫ہظ‬໘ͷ୳ࡧ͕ऴྃ͢Δ͜ͱ͕֬ೝ͞ΕͯɼҾ͖෼͚ͱ͍͏ग़ྗ͕ಘΒΕͨɽ. Analysis of 6×6 TRAX by using df-pn search Kuwabara Kazuto1,a). Kamada Masakazu1 Nakajima Mai1 Hoki Kunihito1,c). Nishitani Tan1. Sugawara Shin1,b). Abstract: We analyzed two-player zero-sum perfect-information game TRAX by using df-pn search. We confirmed that the initial position had been searched with an output of draw when the board size is reduced to 6×6.. 1. ͸͡Ίʹ TRAX ͸. *1 ɼ1980. ೥ʹχϡʔδʔϥϯυਓͷ David. ਤ 1. Trax Ͱ࢖༻͢ΔλΠϧ. Smith ࢯ͕ߟҊͨ͠λʔϯ੍ͷೋਓྵ࿨֬ఆ‫׬‬શ৘ใήʔ ϜͰ͋ΔɽଞͷϘʔυήʔϜͱ͸ҟͳΓɼ൫໘ͷେ͖͞ʹ ͸‫ج‬ຊతʹ੍‫͏͍ͱ͍ͳ͕ݶ‬ಛ௃͕͋Δɽ. TRAX ʹ͸ϦϛςουτϥοΫεͱ‫ݺ‬͹ΕΔ൫໘ͷେ͖. 2. Trax ͷϧʔϧ TRAX ͷϧʔϧʹ͍ͭͯઆ໌͢Δ [1]ɽ. ͞Λ੍‫ͯ͠ݶ‬ϓϨΠ͢Δ༡ͼํ͕ଘࡏ͢ΔɽϦϛςουτ ϥοΫεͰ͸൫໘ͷॎ෯ɼԣ෯͕ 8 ΑΓେ͖͘ͳΔΑ͏ͳ. 2.1 ήʔϜͷਐߦ. ৔ॴʹ͸λΠϧΛ഑ஔ͢Δ͜ͱ͕ग़དྷͳ͍ɽ൫໘͕શͯຒ. TRAX ͸ɼλΠϧΛ 1 ຕͣͭަ‫ʹޓ‬ฒ΂͍ͯ͘ 2 ਓ༻ର. ·ͬͨ࣌఺Ͱܾண͕ண͍͍ͯͳ͔ͬͨ৔߹͸Ҿ͖෼͚ͱͳ. ઓήʔϜͰ͋Δɽฒ΂ΔλΠϧ͸ਤ 1 ʹࣔ͞ΕΔΑ͏ʹ 6. Δɽຊ࿦จͰ͸͜ΕΛ 8×8 TRAX ͱ‫Ϳݺ‬ɽ. छྨ͋Δɽઌख͕നɼ‫ޙ‬ख͕੺ͷϓϨΠϠͰ͋ΔɽλΠϧ. ຊ‫Ͱڀݚ‬͸͜ͷΑ͏ͳ൫໘ͷେ͖͞Λ੍‫ ͨ͠ݶ‬TRAX. Λ഑ஔ͢Δࡍɼ੺ͷϥΠϯ͸੺ɼനͷϥΠϯ͸നʹͭͳ͕. Λ AND/OR ໦Λ༻͍ͯղੳ͢ΔɽϋογϡදΛ࢖༻ͨ͠. ΔΑ͏ʹλΠϧΛ഑ஔ͠ͳ͚Ε͹ͳΒͳ͍ɽࣗ෼ͷ৭ʹ΋. Γɼdf-pn ୳ࡧΛ༻͍ͨΓ͢Δ͜ͱʹΑͬͯେ෯ʹ໦୳ࡧ͕. ૬खͷ৭ʹ΋ͭͳ͙͜ͱ͕Ͱ͖Δɽ. ޮ཰Խ͞ΕΔ͜ͱΛࣔ͢ɽ·ͨɼ൫໘ͷେ͖͞Λ 6×6 ʹ੍. ྫ͑͹ਤ 2 ͷࠨͷ൫໘͸ɼ3 ख·ͰλΠϧΛ഑ஔͨ͠ঢ়. ‫ͨ͠ݶ‬৔߹ʹɼॳ‫ہظ‬໘ͷ୳ࡧ͕ऴྃ͢Δ͜ͱ͕֬ೝ͞Ε. ଶͰ͋Δ͕ɼ࣍ͷ 4 ख໨Λ഑ஔ͢Δ৔߹ӈԼͷΑ͏ʹҟͳ. ͯɼҾ͖෼͚ͱ͍͏݁Ռ͕ಘΒΕͨͨΊɼ͜ΕΛใࠂ͢Δɽ. Δ৭ͷϥΠϯ͕ͭͳ͕Δख͸഑ஔ͢Δ͜ͱ͕Ͱ͖ͳ͍ɽ. 1. a) b) c) *1. ి‫ؾ‬௨৴େֶ The University of Electro-Communications, Chofu, Tokyo 182–8585, Japan [email protected] [email protected] [email protected] Official TRAX Website: http://www.traxgame.com/ (last access, 2016). c 2016 Information Processing Society of Japan . 2.2 ࿈࠯ϧʔϧ TRAX Ͱ͸ɼ௨ৗɼઌखɾ‫ޙ‬ख͸ަ‫ ʹޓ‬1 ຕͣͭλΠ ϧΛ഑ஔ͍ͯ͘͠ɽ͔͠͠ɼ࿈࠯ϧʔϧ͕ద༻͞ΕΔ৔߹ ͸ɼྫ֎తʹ 1 λʔϯͰ 2 ຕҎ্ͷλΠϧ͕഑ஔ͞ΕΔɽ ࿈࠯ͷൃੜ৚݅͸ɼλΠϧΛ 1 ຕஔ͍ͨ‫ޙ‬ɼλΠϧ͕ͳ͍. 1.

(2) Vol.2016-GI-35 No.7 2016/3/8. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. TRAX ͱ‫ݺ‬͹ΕΔมछͰ͸λΠϧΛ഑ஔͰ͖Δεϖʔ ε੍͕‫͞ݶ‬ΕΔɽϧʔϧ͸௨ৗͷ TRAX ʹ४ͣΔ͕ɼ৔ ʹ഑ஔͰ͖ΔλΠϧ͸ॎԣ 8 ྻ·ͰͱͳΔɽ64 ຕ͢΂ͯͷ λΠϧΛ഑ஔͯ͠΋উෛ͕͔ͭͳ͚Ε͹Ҿ͖෼͚ͱͳΔɽ ຊ‫Ͱڀݚ‬͸ɼ8×8 ΑΓαΠζͷখ͍͞ TRAX ΋ѻ͏ɽ ·ͨɼ3 ຊҎ্ͷಉ৭ͷϥΠϯ͕ू·Δۭ͖εϖʔε͕Ͱ ͖ΔΑ͏ͳख͸ඇ߹๏खͱͯ͠ѻ͍ɼۭ͖εϖʔε͕࢒ͬ ਤ 2. ෆਖ਼ͳλΠϧͷ഑ஔ. ͍ͯͯ߹๏ख͕ͳ͍৔߹ʹ͸ख൪ϓϨΠϠͷෛ͚ͱ͢Δɽ. 3. ୳ࡧϓϩάϥϜͷ࣮૷ AND/OR ໦Λ୳ࡧͯ͠ήʔϜ‫ہ‬໘ͷউഊΛ‫ٻ‬ΊΔ [2]ɽ AND/OR ໦͸ Min-Max ໦ͷಛघ‫͋Ͱܗ‬Γɼ֤ϓϨΠϠͷ རಘ͸ 0 ͱ 1 ͷ 2 ஋Ͱද͞ΕΔɽ ਤ3. ࿈࠯͕ 2 ճൃੜ͠ɼ‫ ܭ‬3 ຕͷλΠϧ͕ 1 λʔϯͰ഑ஔ͞Εͨྫ. 3.1 AND/OR ໦ AND/OR ໦͸ɼAND અ఺ͱ OR અ఺͔Βߏ੒͞Εɼࠜ અ఺Λ‫ࡏݱ‬ͷ‫ہ‬໘ͱ͢Δ͖ࠜͭ໦Ͱ͋Δɽ֤અ఺͸֤ήʔ Ϝ‫ہ‬໘ʹରԠ͠ɼઅ఺ؒͷࢬ͸ήʔϜͷਐߦʹରԠ͢Δɽ ਤ 4. 3 ຊͷന৭ϥΠϯ͕ 2 ౓ͷ࿈࠯ൃੜ‫ ʹޙ‬1 Օॴʹू·ͬͨྫ. OR અ఺Ͱ͸ɼརಘΛ 1 ʹ͍ͨ͠ํͷϓϨΠϠ͕ख൪Λ ࣋ͭɽAND અ఺Ͱ͸རಘΛ 0 ʹ͍ͨ͠ํͷϓϨΠϠ͕ख ൪Λ࣋ͭɽ֤અ఺͸ 1ɼ0ɼෆ໌ͷ͍ͣΕ͔ͷ஋Λ࣋ͭɽ ࢠઅ఺Λ࣋ͨͳ͍અ఺Λઌ୺અ఺ͱ‫Ϳݺ‬ɽήʔϜऴྃ৚ ݅Λຬͨͨ͠ઌ୺અ఺Λऴ୺અ఺ͱ‫ͼݺ‬ɼརಘ͕ͦͷ··. ਤ 5 ੺ͷϧʔϓͱനͷϏΫτϦʔϥΠϯͷҰྫ. ऴ୺અ఺ͷ஋ͱͳΔɽ ࢠઅ఺Λ࣋ͭઅ఺Λ಺෦અ఺ͱ‫Ϳݺ‬ɽOR ಺෦અ఺ͷ஋. ৔ॴʹू·Δಉ৭ϥΠϯͷ਺͕ 2 ʹͳΔ͜ͱͰ͋Δɽ͜ͷ. ͸ɼ஋͕ 1 ͷࢠઅ఺͕ 1 ͭͰ΋ଘࡏ͢Ε͹ 1ɼ͢΂ͯͷࢠ. Α͏ͳۭ͖εϖʔε͸ࣗಈతʹຒΊΒΕΔɽ࿈࠯ϧʔϧʹ. અ఺ͷ஋͕ 0 ͳΒ 0ɼͦΕΒͰͳ͚Ε͹ෆ໌ͱͳΔɽAND. ैͬͯλΠϧΛ഑ஔͨ͠‫ޙ‬ɼ͞Βʹ࿈࠯ൃੜ৚͕݅ຬͨ͞. ಺෦અ఺ͷ஋͸ɼ஋͕ 0 ͷࢠઅ఺͕ 1 ͭͰ΋ଘࡏ͢Ε͹ 0ɼ. Εͨ৔߹ʹ΋ಉ͡Α͏ʹۭ͖εϖʔε͕ࣗಈతʹຒΊΒΕ. ͢΂ͯͷࢠઅ఺ͷ஋͕ 1 ͳΒ 1ɼͦΕΒͰͳ͚Ε͹ෆ໌ͱ. Δ (ਤ 3 ࢀর)ɽ. ͳΔɽ. ·ͨɼ͋Δۭ͖εϖʔεʹಉ৭ͷϥΠϯ͕ 3 ຊҎ্ू ·ͬͨͱ͖͸ɼͦͷλʔϯͷϓϨΠϠͷख͸ແޮͱͳΓɼ λʔϯ࠷ॳͷ൫໘ʹ‫͖ר‬໭͞ΕΔ (ਤ 4 ࢀর)ɽ. 3.2 ਂ͞༏ઌ୳ࡧͷ൓෮ਂԽ AND/OR ໦Λ෯༏ઌ୳ࡧ͢Δͱɼ໦ͷαΠζ͕༗‫ݶ‬ͷ ৔߹ɼ‫ݪ‬ཧతʹ͸ࠜͷ஋Λඞͣ‫͚ͭݟ‬Δ͜ͱ͕ग़དྷΔɽ͠. 2.3 উར৚݅. ͔͠ɼ෯༏ઌ୳ࡧʹ͸๚໰ͨ͠શઅ఺Λอଘ͢ΔͨΊʹେ. ϧʔϓ͔ϏΫτϦʔϥΠϯ͕‫ܗ‬੒͞ΕΔͱήʔϜऴྃͱ. ྔͷϝϞϦΛඞཁͱ͢Δͱ͍͏࣮༻্ͷܽ఺͕͋ΔɽҰ. ͳΔɽϧʔϓͱ͸ɼ྆୺͕ͭͳ͕ͬͨϥΠϯͰ͋Δ (ਤ 5. ํɼਂ͞༏ઌ୳ࡧ͸อଘ͢Δઅ఺͸গͳ͍ͱ͍͏ར఺͕͋. ࠨࢀর)ɽϏΫτϦʔϥΠϯͱ͸ɼ൫໘ͷ࠷্୺ͱ࠷Լ୺Λ. Δ͕ɼ୹ख਺ͰήʔϜ͕ऴྃ͢ΔΑ͏ͳ؆୯ͳखॱΛ‫ݟ‬ಀ. ॎஅɼ·ͨ͸࠷ࠨ୺ͱ࠷ӈ୺Λԣஅ͢Δɼ௕͞ 8 ྻҎ্ͷ. ͢Մೳੑ͕͋Δɽਂ͞༏ઌ୳ࡧͷΑ͏ʹϝϞϦফඅΛ཈. ϥΠϯͰ͋Δ (ਤ 5 ӈࢀর)ɽനͷϧʔϓ·ͨ͸ϏΫτϦʔ. ͑ɼ͔ͭ෯༏ઌ୳ࡧͷΑ͏ʹ࠷୹खॱΛ‫͚ͭݟ‬Δ͜ͱ͕Մ. ϥΠϯ͕‫ܗ‬੒͞ΕΔͱനͷউͪɼ੺ͷϧʔϓ·ͨ͸ϏΫτ. ೳͳख๏͕൓෮ਂԽͰ͋Δɽ. ϦʔϥΠϯ͕‫ܗ‬੒͞ΕΔͱ੺ͷউͪͱͳΔɽख൪ϓϨΠϠ. ൓෮ਂԽͰ͸ਂ͞༏ઌ୳ࡧͷਂ͞Λᮢ஋ͱͯ͠୳ࡧΛऴ. Ͱͳ͍ํͷϓϨΠϠͷউར৚͕݅ຬͨ͞ΕΔ৔߹΋͋Δɽ. ྃͤ͞Δɽ࠷ॳ͸ਂ͞ͷᮢ஋Λ 1 ͱͯ͠୳ࡧΛߦ͍ɼղ͕. ·ͨɼനͱ੺྆ํ͕ಉ࣌ʹউར৚݅Λຬͨͨ͠ͱ͖͸ख൪. ‫͔ͭݟ‬Βͳ͚Ε͹ᮢ஋Λ 2 ʹͯ͠୳ࡧΛߦ͏ɽ͜ͷΑ͏ʹ. ϓϨΠϠͷউͪͱͳΔɽ. ͯ͠ᮢ஋Λ 1 ͭͣͭ૿΍͠ͳ͕Β୳ࡧΛࠜઅ఺ʹ஋͕ͭ͘ ·Ͱ‫܁‬Γฦ͢ɽ. 2.4 ϦϛςουτϥοΫε TRAX ʹ ͸ λ Π ϧ ͷ ຕ ਺ ʹ ੍ ‫ ͍ ͳ ͕ ݶ‬ɽҰ ํ ɼ8×8 c 2016 Information Processing Society of Japan . 2.

(3) Vol.2016-GI-35 No.7 2016/3/8. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. 3.3 τϥϯεϙδγϣϯςʔϒϧ. Δɽ୳ࡧதͷઅ఺ͷূ໌਺ͱ൓ূ਺Λ࠶‫͢ࢉܭ‬Δͱ͖ʹ͸. ຊ‫Ͱڀݚ‬͸ɼ೚ҙͷ 2 ‫ہ‬໘ʹରͯ͠ɼλΠϧͷ഑ஔͱख. ͜ͷ഑ྻΛࢀরͨ͠ɽ͜ΕʹΑΓɼຖճࢠઅ఺ͷ‫ہ‬໘Λੜ. ൪͕ಉ͡Ͱ͋Ε͹ɼͦͷ‫ہ‬໘ʹ౸ୡ͢Δखॱ͕ҟͳ͍ͬͯ. ੒ͯ͠κϒϦετϋογϡΩʔΛ‫ٻ‬ΊɼTT Λࢀর͢Δ৔. ͨͱͯ͠΋ಉ͡‫ہ‬໘ͱΈͳ͢ɽͦͯ͠ɼͦͷΑ͏ͳෳ਺ͷ. ߹ʹൺ΂ͯ໿ 4 ഒͷߴ଎Խ͕ୡ੒͞Εͨɽ. ‫ہ‬໘Λ 1 ͭͷઅ఺ʹରԠͤ͞Δɽ͕ͨͬͯ͠ɼ໦Ͱ͸ͳ ͘ඇ८ճάϥϑ (DAG) ͷ୳ࡧΛߦ͏͜ͱͱͳΔɽͳ͓ɼ. TRAX Ͱ͸ 1 λʔϯ͋ͨΓ 1 ຕҎ্ͷλΠϧ͕഑ஔ͞Εɼ. 3.7 ΨϕʔδίϨΫγϣϯ (GC) TT ͷΤϯτϦ͕શͯຒ·ͬͯ͠·ͬͨ࣌ʹ GC Λߦ͍ɼ. ഑ஔͨ͠λΠϧ͕ফ໓͢Δ͜ͱ΋ͳ͍ͨΊ८ճ͸ଘࡏ͠. ۭ͖ΤϯτϦΛ֬อ͢Δɽ͋Δ‫ہ‬໘Λࠜͱ͢Δ෦෼໦ͷα. ͳ͍ɽ. Πζ͕େ͖͍΄Ͳɼͦͷ‫ہ‬໘৘ใ͸Ձ஋͕ߴ͍ͱߟ͑ΒΕ. ൓෮ਂԽΛߦͬͨΓɼDAG Λ୳ࡧͨ͠Γ͢ΔͨΊɼಉҰ. ΔɽͳͥͳΒ͹ɼ෦෼໦ͷαΠζ͕େ͖͍΄Ͳ࠶‫࣌ʹࢉܭ‬. અ఺Λ 2 ճҎ্๚໰͢ΔΑ͏ͳ͜ͱ͕සൟʹ‫͜ى‬Δɽͦ͜. ͕͔͔ؒΔ͔ΒͰ͋Δɽ͕ͨͬͯ͠ɼΤϯτϦΛࣺͯΔ࣌. Ͱɼ୳ࡧͷޮ཰ԽΛ͸͔ΔͨΊɼτϥϯεϙδγϣϯςʔ. ͸෦෼໦ͷαΠζ͕খ͍͞Α͏ͳΤϯτϦ͔Βࣺ͍ͯͯ͘. ϒϧ (ҎԼ TT) Λར༻͢ΔɽTT ͱ͸୳ࡧͨ͠‫ہ‬໘ͷ݁Ռ. ͷ͕ྑ͍ɽ. Λอଘ͢ΔϋογϡදͰ͋Δɽ͋Δ‫ہ‬໘Λ୳ࡧ͠Α͏ͱ͠. ຊ‫ڀݚ‬ͷ࣮૷͸ɼsmall Tree GC ʹ‫[ ͮ͘ج‬7]ɽTT ͷΤ. ͨ࣌ɼͦͷ‫ہ‬໘ͷ݁Ռ͕ TT ʹอଘ͞Ε͍ͯΕ͹͜ΕΛࢀ. ϯτϦʹ͋Δઅ఺ͷ৘ใΛొ࿥͢Δࡍɼ͜ͷઅ఺ҎԼͷ୳. র͢Δ͚ͩͰ୳ࡧΛऴྃग़དྷΔͨΊɼ୳ࡧ͕࣌ؒ୹ॖ͞Ε. ࡧʹཁͨ͠๚໰અ఺਺Λอଘ͢ΔɽTT ͷΤϯτϦ͕શͯ. Δɽ2 ‫ہ‬໘ͷൺֱ΍ϋογϡΩʔʹ͸ɼखͷཚ਺஋ͷഉଞ. ຒ·ͬͨΒɼ࣍ͷૢ࡞Λߦ͏ɽ. త࿦ཧ࿨Λͱͬͨ 64 ϏοτͷκϒϦετϋογϡ๏Λ࢖. ( 1 ) ᮢ஋ θ Λ 1 ʹઃఆ͢Δ. ༻͢Δ [3]ɽ·ͨɼϋογϡද͸νΣʔϯϋογϡ๏Λ༻. ( 2 ) ๚໰અ఺਺͕ θ ΑΓখ͍͞ΤϯτϦΛશۭͯʹ͢Δ. ͍࣮ͯ૷ͨ͠ɽ. ( 3 ) TT ͷۭ͖༰ྔ͕Ұఆͷׂ߹ r Λ௒͍͑ͯͨΒ GC Λ ऴྃ͢Δ. 3.4 ਂ͞༏ઌূ໌਺୳ࡧ (df-pn ୳ࡧ) Df-pn ୳ࡧ͸ Allis Βͷূ໌਺୳ࡧΛਂ͞༏ઌͰ୳ࡧ͢. ( 4 ) ͦ͏Ͱͳ͚Ε͹ θ Λ 1 ૿΍͠ɼखॱ 2 ΁໭Δ ຊ‫Ͱڀݚ‬͸ r ͸ 0.3 ʹઃఆͨ͠ɽ. Δํ๏Ͱ͋Δ [4]ɽ300 ख٧ΊҎ্ͷ٧ক‫ع‬Λશͯղ͍ͨ͜ ͱͰ༗༻ੑ͕ࣔ͞Εͨ [5], [6]ɽূ໌਺୳ࡧͰ࣍ͷ࠷༗ྗઅ ఺ΛબͿͱ͖ʹલճͱಉ͡‫ܦ‬࿏ΛͨͲͬͨͱ͢Δͱɼࠜ·. 3.8 ਂ͞Λ੍‫ͨ͠ݶ‬ઙ͍ AND/OR ໦୳ࡧͷซ༻ 1ɼ2 खͰήʔϜ͕ऴྃ͢ΔΑ͏ͳ‫ہ‬໘ʹରͯ͠͸ɼTT. Ͱ໭ͬͯજΔͱ͍͏ૢ࡞͸ແବͰ͋ΔɽDf-pn ୳ࡧͰ͸ɼ. Λ༻͍ͨΓূ໌਺ɼ൓ূ਺Λ༻͍ͨΓ͢Δ͜ͱʹΑΔ୳ࡧ. ࠷༗ྗઅ఺͕୳ࡧதͷઅ఺ͷԼʹ͋Δͱ͖͸໭Βͣͦͷ·. ͷޮ཰Խ͸͋·Γ๬Ίͳ͍ɽͦͷͨΊɼdf-pn ୳ࡧͷ಺෦. ·୳ࡧΛߦ͏͜ͱ͕ग़དྷΔɽ. અ఺Ͱઙ͍ਂ͞ d ͷ AND/OR ໦୳ࡧΛߦ͏ɽ. Df-pn ୳ࡧͰ͸ɼ୳ࡧଧͪ੾Γͷ৚݅ʹ༻͍ΒΕΔᮢ஋. ͜ͷ಺෦અ఺ v Λࠜͱͨ͠ઙ͍ਂ͞ d ͷ AND/OR ໦୳. ͱͯ͠ਂ͞༏ઌ୳ࡧͷ୳ࡧਂ͞͸༻͍ͳ͍ɽূ໌਺ͱ൓ূ. ࡧʹΑΓɼv ͷ஋͕൑໌ͨ͠৔߹ɼ͜ͷ݁ՌΛ TT ʹอଘ. ਺Λᮢ஋ʹ༻͍ͯଧͪ੾Γ৚݅Λઃఆ͠ɼ֤અ఺Λ๚໰͢. ͢Δɽͨͩ͠ɼGC Ͱ༻͍ΒΕΔ৘ใͰ͋Δ෦෼໦ͷ๚໰. Δॱ൪Λ੍‫͢ޚ‬Δɽ. ճ਺͸ 0 ͱͯ͠อଘ͢Δɽ͜͜Ͱɼ͜ͷઙ͍୳ࡧͰ๚໰͠ ͨઅ఺৘ใ͸ TT ʹొ࿥͠ͳ͍ɽઙ͍ AND/OR ໦୳ࡧ͕. 3.5 ରশੑΛߟྀͨ͠ಉҰ‫ہ‬໘ͷ‫ݕ‬ग़. ऴྃͯ͠΋ v ͷ஋͕൑໌͠ͳ͍৔߹ɼઙ͍ AND/OR ໦୳. ୳ࡧͷޮ཰ԽͷͨΊɼճసɼ൓సɼฏߦҠಈͯ͠౳͘͠ͳ. ࡧʹΑͬͯ஋͕൑໌͠ͳ͔ͬͨࢠઅ఺Λ༻͍ͯ df-pn ୳ࡧ. Δ‫ہ‬໘ΛಉҰ‫ہ‬໘ͱΈͳ͢ɽ͜ͷͨΊʹɼκϒϦετϋο. Λ‫ܧ‬ଓ͢Δɽ͜ΕʹΑΓɼTT ΤϯτϦ΁ͷొ࿥ճ਺Λ‫ݮ‬. γϡΩʔΛੜ੒͢Δࡍʹ͸ɼճస͓Αͼ൓స͞Εͨ n×n. Β͠ɼGC ͷൃੜճ਺͕࡟‫͞ݮ‬ΕΔɽ. TRAX ͷ൫໘Λɼn×n ͷฏ໘ʹ࠶഑ஔ͢Δɽ͜ͷ࣌ʹɼશ. ͜ͷΑ͏ʹɼઙ͍ AND/OR ໦୳ࡧΛ df-pn ୳ࡧʹซ༻. ͯͷλΠϧ͸‫ܗ‬Λม͑ͣʹࠨ্ʹ‫ͤد‬Δɽ͜ͷΑ͏ʹͯ͠. ͢Δํ๏͸ઌߦ‫ʹڀݚ‬΋ΈΒΕΔ [8]ɽ͜ͷઌߦ‫Ͱڀݚ‬͸ɼ. ੜ੒͞Εͨ 8 ͭͷ 64 ϏοτϋογϡΩʔͷ͏ͪɼ࠷΋஋. ٧ক‫ ͍͓ͯʹع‬df-pn ୳ࡧ͕ޮ཰Խ͞Εɼ୳ࡧઅ఺਺͓Α. ͕খ͍͞΋ͷΛɼ‫ہ‬໘ͷΩʔͱ͢Δɽ. ͼ୳ࡧ͕࣌ؒ࡟‫͞ݮ‬ΕΔ͜ͱΛ‫ݟ‬ग़ͨ͠ɽͳ͓ɼ͜ͷઌߦ ‫Ͱڀݚ‬͸৽‫ن‬અ఺ͷΈʹରͯ͠ઙ͍ AND/OR ໦୳ࡧΛߦ. 3.6 ࢠઅ఺৘ใͷ഑ྻ΁ͷอଘ Df-pn ୳ࡧͰ͸ɼ๚໰ͨ͠અ఺ͷূ໌਺ɼ൓ূ਺ͳͲͷ৘. ͏͜ͱΛ໨ࢦ͕ͨ͠ɼຊ‫Ͱڀݚ‬͸͜ΕΛ๚Εͨશͯͷ df-pn ୳ࡧͷ಺෦અ఺ʹର͠ߦͬͨɽ. ใΛ TT ʹอଘ͢Δɽຊ‫Ͱڀݚ‬͸ɼTT ΁ͷอଘʹՃ͑ͯ. ຊ‫Ͱڀݚ‬͸ɼd ͸ 0, 1, 2 ͷ͍ͣΕ͔ͱ͍ͯ͠Δɽd = 0 ͷ. ୳ࡧ‫ܦ‬࿏্ͷ֤ਂ͞ͷઅ఺ʹର͢Δશࢠઅ఺ͷ৘ใ (ϋο. ৔߹͸͜ͷ୳ࡧΛશ͘ߦΘͣɼੜ੒ͨ͠ࢠઅ఺શͯʹର͠. γϡΩʔɼূ໌਺ɼ൓ূ਺) Λ TT ͱ͸ผͷ഑ྻʹอଘ͢. df-pn ୳ࡧΛߦͬͨɽ. c 2016 Information Processing Society of Japan . 3.

(4) Vol.2016-GI-35 No.7 2016/3/8. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report ද 1. 3×3 TRAXɼઌखউͪͱҾ͖෼͚ͷརಘΛ 1 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 1ɽ. ᖖ⏝ᑐᩘ䜢䛸䛳䛯᥈⣴⠇Ⅼᩘ. ਤ 6 8 7 6 5 4 3 2 1 0. 6 ࣌ؒҎ಺ʹ݁Ռ͕ಘΒΕͳ͔ͬͨ໰୊. G . G . ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. ਂ͞. ൓෮ਂԽ. 2.2. 2,899,038. 8. ൓෮ਂԽ (TT ར༻). 0.0. 7,495. 8. df-pn (d = 0). 0.0. 1,063. -. G . ද 2. 3×3 TRAXɼ‫ޙ‬खউͪͱҾ͖෼͚ͷརಘΛ 0 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 0ɽ. 0. 10. 20. 30. 40. 50. ၥ㢟␒ྕ. ਤ 7. TRAX puzzles Λղ͘ͷʹཁͨ͠୳ࡧઅ఺਺. ද 3. ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. ਂ͞. ൓෮ਂԽ. 2.8. 4,561,403. 8. ൓෮ਂԽ (TT ར༻). 0.0. 8,765. 8. df-pn (d = 0). 0.0. 2,548. -. 4×4 TRAXɼઌखউͪͱҾ͖෼͚ͷརಘΛ 1 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 1ɽ. 4. ࣮‫݁ݧ‬Ռ TRAX ʹ df-pn ୳ࡧΛద༻͠ɼήʔϜͷ݁ՌΛ‫ٻ‬Ίɼੑ ೳͷ‫ূݕ‬Λߦ͏ɽ ࣮‫ڥ؀ͨ͠༻࢖ʹݧ‬͸ҎԼͷ௨ΓͰ͋Δɽ. ද 4. ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. ਂ͞. ൓෮ਂԽ (TT ར༻). 35.3. 2,775,271. 11. df-pn (d = 0). 1.4. 69,150. -. 4×4 TRAXɼ‫ޙ‬खউͪͱҾ͖෼͚ͷརಘΛ 0 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 0ɽ. OS Windows 8 Pro 64-bit CPU Intel(R) Xeon(R) CPU E3-1220 v3 @ 3.10GHz TT ʹ͸ 120,000,000 ΤϯτϦʔ (໿ 3.4GB) Λ֬อͨ͠ɽ. ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. ਂ͞. ൓෮ਂԽ (TT ར༻). 36.5. 2,817,170. 11. df-pn (d = 0). 2.3. 95,557. -. 4.1 TRAX puzzles Λ༻͍ͨ‫ূݕ‬ TRAX ΦϑΟγϟϧαΠτͰެ։͞Ε͍ͯΔɼTRAX puzzles*2 Λ df-pn ୳ࡧͰղ͖ɼ୳ࡧઅ఺਺Λൺֱ͢Δɽશ ෦Ͱ 52 ໰ͷ໰୊͔ΒͳΓɼ೉қ౓ (easyɼintermediateɼ. 0 ͱͨ͠୳ࡧͷ྆ํΛߦ͏ɽ n ͕ 3 ͱ 4 ͷ୳ࡧ݁ՌΛද 1 ͔Βද 4 ʹࣔ͢ɽTT ͱ. hard) ͱ࣍ͷख൪ (നɼ੺) Ͱ෼͔Ε͍ͯΔɽશͯ࣍ͷख൪. df-pn ୳ࡧ͸ TRAX ͷ୳ࡧΛେ෯ʹޮ཰Խ͢Δ͜ͱ͕໌Β. ͕উͭ‫ہ‬໘Ͱ͋Δɽ. ͔ͱͳͬͨɽ3×3 TRAX ͱ 4×4 TRAX ͸Ҿ͖෼͚ͱ͍͏. ੍ ‫ ݶ‬ͷ ͳ ͍ TRAX ͸ ࣮ ૷ ग़ དྷ ͳ ͍ ͨ Ί ɼή ʔ Ϝ Λ. ݁Ռ͕ಘΒΕͨɽ. 255×255 TRAX ͱΈͳͯ͠୳ࡧ͠ɼॎԣͷྻ͕ 255 ʹ ୡ͠ͳ͍͜ͱΛ֬ೝͨ͠ɽ·ͨɼ୳ࡧ͕࣌ؒ 6 ࣌ؒ‫ܦ‬ա͠ ͯ΋ղΛ‫͚ͭݟ‬Δ͜ͱ͕ग़དྷͳ͚Ε͹ɼ୳ࡧΛଧͪ੾ͬͨɽ ࣍ͷख൪͕উͬͨ৔߹ͷརಘ͸ 1ɼෛ͚ͨ৔߹ͷརಘ͸ 0 ͱͨ͠. 4.3 ઙ͍ AND/OR ໦୳ࡧΛซ༻͢Δ͜ͱʹΑΔ df-pn ୳ࡧͷޮ཰Խ‫ূݕ‬. n ͕ 5 ͱ 6 ͷ୳ࡧ݁ՌΛද 5 ͔Βද 8 ʹࣔ͢ɽઙ͍ AND/OR ໦୳ࡧͷਂ͞ d ͕େ͖͍΄Ͳ df-pn ୳ࡧઅ఺਺. ਤ 7 ʹ݁ՌΛࣔ͢ɽউഊ݁ՌΛಘΔ͜ͱ͕ग़དྷͨ৔߹ʹ. ͕‫ݮ‬গ͠ɼd Λ 0 ͔Β 1 ʹͨ͠৔߹ʹ͸୳ࡧ࣌ؒ΋‫ݮ‬গ͢. ͸શͯ୊ҙͱಉ݁͡Ռ͕ಘΒΕͨɽਤ 6 ͷ໰୊ͷΈ࣌ؒ಺. Δ͜ͱ͕ࣔ͞Εͨɽ͔͠͠ɼd Λ 1 ͔Β 2 ʹͨ͠৔߹ʹ͸. ʹղΛ‫͚ͭݟ‬Δ͜ͱ͕ग़དྷͳ͔ͬͨɽઙ͍ AND/OR ໦୳. ୳ࡧ͕࣌ؒ૿Ճͯ͠͠·͏͜ͱ΋ࣔ͞Εͨɽ5×5 TRAX. ࡧͷਂ͞ d ͕େ͖͍΄Ͳ df-pn ୳ࡧઅ఺਺͕‫ݮ‬গ͠ɼTT. ͱ 6×6 TRAX ΋Ҿ͖෼͚ͱ͍͏݁Ռ͕ಘΒΕͨɽ. ͷ࢖༻ΤϯτϦ਺΋‫ݮ‬গ͢Δ͜ͱ͕෼͔ͬͨɽ. 5. ͓ΘΓʹ. 4.2 TT ͱ df-pn ୳ࡧͷੑೳ‫ূݕ‬ n×n TRAX Ͱ͸Ҿ͖෼͚͕ଘࡏ͢ΔͨΊɼ݁Ռ͸উͪɼ ෛ͚ɼҾ͖෼͚ͷ 3 ௨ΓʹͳΔɽAND/OR ໦୳ࡧ͸རಘ. αΠζΛ੍‫ ͨ͠ݶ‬TRAX ͷॳ‫ہظ‬໘Λ df-pn ୳ࡧΛ༻ ͍ͯղੳͨ͠ɽ ൫໘ͷେ͖͞Λ 6×6 ʹ੍‫ͨ͠ݶ‬৔߹ʹɼ ॳ‫ہظ‬໘ͷ୳ࡧ͕ऴྃ͢Δ͜ͱ͕֬ೝ͞ΕͯɼҾ͖෼͚ͱ. ͕ 3 ௨Γ͋Δ৔߹Λѻ͏͜ͱ͕ग़དྷͳ͍ͷͰɼઌखউͪ΋. ͍͏݁Ռ͕ಘΒΕͨɽਂ͞Λᮢ஋ͱͨ͠ AND/OR ໦୳ࡧ. ͘͠͸Ҿ͖෼͚ͷརಘΛ 1ɼઌखෛ͚ͷརಘΛ 0 ͱͨ͠୳. ΑΓ΋ɼূ໌ɾ൓ূ਺Λᮢ஋ͱͨ͠ df-pn ୳ࡧͷํ͕ޮ཰. ࡧͱɼઌखউͪͷརಘΛ 1ɼઌखෛ͚ͱҾ͖෼͚ͷརಘΛ. Α͘‫ہ‬໘Λ୳ࡧ͢Δ͜ͱ͕ࣔ͞ΕͨɽDf-pn ୳ࡧΛߦ͏৔. *2. TRAX puzzles http://www.traxgame.com/games puzzles.php (last access, 2016). c 2016 Information Processing Society of Japan . ߹ɼ֤୳ࡧઅ఺Ͱਂ͞ͷઙ͍ AND/OR ໦୳ࡧΛ࣮ߦ͢Δ ͱ୳ࡧޮ཰͕޲্͢Δ͜ͱ͕֬ೝ͞Εͨɽ. 4.

(5) Vol.2016-GI-35 No.7 2016/3/8. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report ද 5. 5×5 TRAXɼઌखউͪͱҾ͖෼͚ͷརಘΛ 1 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 1ɽ d ୳ࡧ࣌ؒ (s). ද 6. ୳ࡧઅ఺਺. GC ൃੜճ਺. 0. 90.6. 2,400,757. 0. 1. 41.6. 1,258,075. 0. 2. 84.5. 385,322. 0. 5×5 TRAXɼ‫ޙ‬खউͪͱҾ͖෼͚ͷརಘΛ 0 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 0ɽ d ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. GC ൃੜճ਺. 150.0. 4,086,531. 0. 1. 79.4. 2,466,704. 0. 2. 212.7. 1,004,546. 0. 0. ද 7. 6×6 TRAXɼઌखউͪͱҾ͖෼͚ͷརಘΛ 1 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 1ɽ d ୳ࡧ࣌ؒ (s). ද 8. ୳ࡧઅ఺਺. GC ൃੜճ਺. 0. 7,249.0. 97,333,448. 0. 1. 3,563.6. 66,475,706. 0. 2. 8,780.8. 26,060,356. 0. 6×6 TRAXɼ‫ޙ‬खউͪͱҾ͖෼͚ͷརಘΛ 0 ͱͨ͠৔߹ɽࠜ અ఺ͷ஋͸ 0ɽ d ୳ࡧ࣌ؒ (s). ୳ࡧઅ఺਺. GC ൃੜճ਺. 0. 28,529.5. 367,199,042. 2. 1. 14,190.9. 242,817,026. 2. 2. 22,059.7. 66,786,537. 0. ࢀߟจ‫ݙ‬ [1] [2]. [3]. [4]. [5]. [6]. [7]. [8]. Bailey, D.: Trax Strategy For Beginners, D.G. Bailey, New Zealand, second edition (1997). খ୩ળߦɼ‫؛‬ຊষ޺ɼࣲ‫ݪ‬Ұ༑ɼɹླ໦߽ɿήʔϜ‫ࢉܭ‬ϝ ΧχζϜ: ক‫ع‬ɾғ‫ޟ‬ɾΦηϩɾνΣεͷϓϩάϥϜ͸Ͳ ͏ಈ͘. Zobrist, A. L.: A new hashing method with application for game playing, ICCA journal, Vol. 13, No. 2, pp. 69–73 (1970). Allis, L. V., van der Meulen, M. and Van Den Herik, H. J.: Proof-number search, Artificial Intelligence, Vol. 66, No. 1, pp. 91–124 (1994). ɹ௕ҪาɼɹࠓҪߒɿdf-pn ΞϧΰϦζϜͷ٧ক‫ع‬Λղ͘ ϓϩάϥϜ΁ͷԠ༻ɼ৘ใॲཧֶձ࿦จࢽɼ Vol. 43, No. 6, pp. 1769–1777 (2002). Kishimoto, A., Winands, M. H., M¨ uller, M. and Saito, J.-T.: Game-tree search using proof numbers: The first twenty years, ICGA Journal, Vol. 35, No. 3, pp. 131–156 (2012). Nagai, A.: A New Depth-First-Search Algorithm for AND/OR Trees, Master’s thesis, The University of Tokyo, Tokyo, Japan (1999). ۚࢠ஌దɼాத఩࿕ɼࢁ‫ޱ‬࿨‫ل‬ɼɹ઒߹‫ܛ‬ɿ৽‫ن‬અ఺Ͱ‫ݻ‬ఆ ਂ͞ͷ୳ࡧΛซ༻͢Δ df-pn ΞϧΰϦζϜɼୈ 10 ճήʔ ϜɾϓϩάϥϛϯάϫʔΫγϣοϓɼpp. 1–8 (2005).. c 2016 Information Processing Society of Japan . 5.

(6)