著者

保木 邦仁

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.78-83, 2006-11-10

---

将棋プログラムBonanzaの思考アルゴリズムの主要な特徴の一つである,局面評価の機械学習に関する手法を紹介する.これの手法では,minimax探索の振る舞いを決める特徴ベクトルの自動学習を目指す.熟練した人間の棋譜との指し手一致の度合いを図る目的関数を設計し,これに停留値を与える静的評価関数f(v)の特徴ベクトルvを求める.さらに,v=0となる自明な解の除去や,棋譜サンプル数の不足に起因するオーバーフィッティングを回避するため,ラグランジュ未定乗数法を用いて目的関数に拘束条件を課す.目的関数の停留値は静的評価関数の勾配∇f(v)を用いて探索される.これは,古くから知られている最適制御理論の枠組みに沿った手法である.しかし,約6万局の学習データから1万以上の要素を持つ特徴べくとるを生成し,駒割に加え序盤の駒組,中盤の駒の動き,終盤の速度計算等の複雑な盤面特徴の把握が必要とされる将棋において,有効に働く局面評価関数が生成された.筆者に知る限り,本稿で提案される手法は,チェスやその変種の静的評価関数の自動学習法として”実用に耐え,役に立つ”初めてのものである.

著者

村田 朋紀 橋本 剛 長嶋 淳

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.17-24, 2006-11-10

---

ゲーム木探索において,何らかの枝刈りを行う場合,一時的に損をするが後で良くなる手筋を読むことは困難である.本研究では有効な手筋を少ない計算量で導き出し,有効な手順を深く探索させることを目的とする.そのために手筋を自動で収集・登録し,数手一組として探索に用いるためのフレームワークが必要である.本稿では部分局面パターンにn-gram統計を使用し,棋譜データベースから手筋を自動で抽出する手法を提案する.この手法により大量の棋譜から局面に対し有効な手筋データのみを獲得することに成功した.また,獲得した手筋データを探索に用いる手法を提案し,性能評価を行った結果,探索性能の大幅な向上に成功した.

著者

三島 健 櫻井 英俊 野下浩平

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.136-142, 2006-11-10

---

ゲームHexは、先手必勝手順の存在が証明されているが、具体的な必勝手順を示すことは長年の研究課題である。本稿では、石の連結性を定義するための新しい概念として、δ連結を提案し、それに基づいて、連結に関与する領域を拡張するための新しい技法δ拡張を導入する。この技法の応用として、従来の技法で記述するには複雑すぎるとされていた8×8盤面の初手63 に対する必勝手順を示す。また、この技法の強力さを示す例として、8×8盤面の初手54 に対する野下の必勝手順(2005)を大幅に簡単化する。同様にして、9×9 盤面に対する必勝手順を示すことができるが、本稿ではその証明木を示す(現在細部のチェック中)。

著者

長嶋 淳 橋本 剛 橋本 隼一

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.1-8, 2006-11-10

---

端攻めを苦手としていることは,改善が必要なコンピュータ将棋の弱点の1つである.本研究では,局面情報から端攻めの可能性を判定し,可能性の高い局面において重点的に端攻めの手を読ませることで,この問題に取り組む.多数の棋譜を分析して得られた条件をもとに将棋プログラムTACOS へ端攻めルーチンを実装し,評価を行なった.その結果,実装前と比較してTACOSは多くの局面で端攻めを行なえるようになった.

著者

吉本 晴洋 繁富利恵 副田 俊介 金子 知適 田浦 健次朗

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.191-194, 2006-11-10

---

本稿では人狼BBS というゲームをP2P 上で安全に行なうためのプロトコルを提案する。P2P での実装はサーバの管理が不要というメリットがあるが、信頼できる第三者がいないため、プレイヤーが不正を行うことができてしまう。本研究では匿名通信路やゼロ知識証明などの暗号技術を用いて不正を防止するプロトコルを提案した。

著者

白井 裕己 五十嵐 力 但馬 康宏 小谷 善行

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.32-39, 2006-11-10

著者

高橋 克吉 伊藤 毅志 村松 正和 松原 仁

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.120-127, 2006-11-10

著者

吉本 晴洋 繁富利恵 副田 俊介 金子 知適 田浦 健次朗

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.191-194, 2006-11-10

著者

竹内 聖悟 林 芳樹 金子 知適 川合 慧

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.56-63, 2006-11-10

---

本稿では、勝率と評価値の歪みに基づいた評価関数の調整法を提案し、将棋を例題に、本手法の有効性を示す。評価関数の調整は強いプログラムの作成に不可欠であるが、どこに問題があるか発見することや評価値を適切にあたえることはゲームの知識が必要であり困難が多い。本研究では、評価関数に問題がある局面では勝ち易さを適切に評価できず、勝率と評価関数との関係に歪みが生じていることに着目し、条件毎に勝率と評価値のグラフを描くことにより評価関数の問題点をを発見することを提案する。本手法を将棋において先手と後手の進行度差がある局面に対して用い、プレイヤ毎の進行度を評価しない評価関数には問題があることを示した。さらに、その問題を解決するため、進行度差を評価に含めた評価関数を設計し、値の自動的な調整を行った。そして、自己対戦によって調整後のプログラムの棋力の向上を確認し、本手法の有効性を示した。

著者

Grimbergen Reijer

雑誌

ゲームプログラミングワークショップ2006論文集

巻号頁・発行日

vol.2006, pp.70-77, 2006-11-10

---

In this paper it will be explained how to use bitboards for move generation in shogi. In chess, bitboards have been used in most strong programs because of the easy representation of a chess board by a single 64-bit integer. For shogi, a less efficient representation has to be used because a shogi board has 81 squares instead of 64. A representation with an array of three integers is proposed, where each integer represents 27 squares of the board. This representation is then used for move generation in a similar way to the methods used in chess, for example by using rotated bitboards for generating the moves of the sliding pieces rook, bishop and lance. A comparison of move generation speed between the method using bitboards and by using the more common method of attack tables showed that by using bitboards the move generation speed of the program Spear was improved by 48.8%.