著者
金子 知適 田中 哲朗 山口 和紀 川合 慧
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.48, no.11, pp.3438-3445, 2007-11-15
参考文献数
17
被引用文献数
2 or 0

将棋の評価関数として,駒(所有者,種類,位置を含む)の2 項関係を評価するモデルと,棋譜を使った自動的な調整方法を提案する.将棋の評価関数では駒の損得を基本としたうえで,駒の働きや玉の危険度など様々な評価項目が用いられている.しかしそのような駒の損得以外の評価項目は設計が難しく,また自動的な値の調整も困難であった.本稿では,駒の関係という単純な評価項目を提案し,既存の評価項目の多くが駒の関係により表現可能であることを示す.さらに,棋譜で指された指手と指されなかった手の差分に注目した判別分析を行うことで,重みを自動的に調整することを提案する.実際に評価関数を作成したところ,形を評価する実験で良い結果が得られた.さらに,対戦でも提案した評価関数を使ったプログラムが有為に勝ち越し,提案手法の有効性が示された.New evaluation function in shogi, based on pairwise piece relations, and a method for automated tuning of their weights are presented. Existing evaluation functions treat a lot of specific aspects, as well as material balance, of the game. Most of such aspects can, we show, be handled by the proposed method. Then, we automatically adjust the weights of pairwise piece relations, by means of discriminant analysis of many game records. Our experiments showed that reasonably accurate evaluation functions for preferable configuration of pieces can successfully be constructed. Moreover, significant improvement on strength was confirmed in self-play.
著者
小田原 大 金子 知適 川合 慧
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2004, no.64, pp.33-40, 2004-06-18

コンピュータパズルの倉庫番のソルバにおける課題は、手詰りの局面を効率良く検出することであり、特に袋小路の判定は難しい問題として知られている。既存の手法では判定に再帰的な探索を必要とするため、判定の効率が悪い。本稿では、袋小路を含めた「手詰り」状態の一般的な判定方法を提案し、それを探索に組合せることを提案する。具体的には問題を区域に分割し、ユニットと呼ばれる各区域の状態の組合せによって効率的に手詰りの状態を判定する。実際に倉庫番の問題に適用したところ、既存の手法では判定が難しい局面に対しても手詰りと判定することに成功した。A new method of detecting deadlock states is proposed. We define unit as a part of a map, and decompose a map into units. Each unit has gateways. The keeper can enter the unit through some gateways depending on status of other areas. We judge whether the entire state is a deadlock or not by using combination of local status of units. As a result, we could express a lot of deadlocks and showed ways of applying it to effective search.
著者
中村 政隆 伊藤 元己 川合 慧 佐久間 雅
出版者
東京大学
雑誌
基盤研究(C)
巻号頁・発行日
2003 (Released:2003-04-01)

複数の種(taxon)の遺伝子の塩基列もしくはアミノ酸列をデータとして、そこから系統樹(phylogenetic tree)を構築するアルゴリズムは、距離行列法と、与えられたデータのもとでの各二分木のコストを定義してコスト最小の二分木を求める、という2つのタイプに大別できる。距離行列法(Pairwise Distance Method)としては、UPGMA/WPGMA法(実用にはあまり用いられてない)、及び近隣結合法(Neighbour Joining Method, NJ法)などが知られている。それに対して、初期解から局所探索、つまり受刑探索を繰り返して最適器を求めるときの目的関数の取り方として、最小二乗法、最小進化法、最大節約法(Parsimony)、最尤法(Maximum Likelihood Method)などが知られている。一般に組み合わせ最適化の理論では、これらの樹形探索のような局所探索を繰り返すときには、適当なメタヒューリスティックアルゴリズムを使うとより効率的なアルゴリズムが得られることが知られている。実際には、組み合わせ最適化の分野でメタヒューリスティックアルゴリズムの名の下に以下の3つが知られている(1)遺伝的アルゴリズム(Genetic Algorithm)(2)タブー探索(Tabu Search)(3)進化的アルゴリズムこれらの戦略を系統樹アルゴリズムの樹形探索の部分に適用し、シミュレーションを繰り返してみた結果、タブー探索がもっとも効果的であるという知見を得た。
著者
竹内 聖悟 林 芳樹 金子 知適 山口 和紀 川合 慧
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.48, no.11, pp.3446-3454, 2007-11-15

勝率と評価値の関係に基づいた問題点の発見手法を提案し,その有効性を示す.強いプログラムの作成には良い評価関数が不可欠だが,既存の評価関数の問題点の発見や評価値の適切な調整には,対戦などの試行錯誤が必要であり困難であった.本研究ではまず,問題点の発見手法として,評価関数が与える評価値に対する勝率に着目しそのグラフを描くことを提案し,評価関数に欠陥が存在する場合には複数の線として明確に図示されることを示す.さらに,欠陥を解決した評価関数では評価値に対する勝率のグラフが条件によらず一本化されるため,グラフにより評価関数の改善を確認できることを示す.実際に将棋,チェス,オセロについて評価関数の欠陥を図示ができることを示し,将棋においてはその改善がグラフで確認できることを示す.さらに自己対戦から実力が改善されていることを確認した.
著者
川合 慧
出版者
一般社団法人情報処理学会
雑誌
情報処理 (ISSN:04478053)
巻号頁・発行日
vol.21, no.11, pp.p1162-1173, 1980-11-15
著者
竹内 聖悟 林 芳樹 金子 知適 川合 慧
雑誌
ゲームプログラミングワークショップ2006論文集
巻号頁・発行日
vol.2006, pp.56-63, 2006-11-10

本稿では、勝率と評価値の歪みに基づいた評価関数の調整法を提案し、将棋を例題に、本手法の有効性を示す。評価関数の調整は強いプログラムの作成に不可欠であるが、どこに問題があるか発見することや評価値を適切にあたえることはゲームの知識が必要であり困難が多い。本研究では、評価関数に問題がある局面では勝ち易さを適切に評価できず、勝率と評価関数との関係に歪みが生じていることに着目し、条件毎に勝率と評価値のグラフを描くことにより評価関数の問題点をを発見することを提案する。本手法を将棋において先手と後手の進行度差がある局面に対して用い、プレイヤ毎の進行度を評価しない評価関数には問題があることを示した。さらに、その問題を解決するため、進行度差を評価に含めた評価関数を設計し、値の自動的な調整を行った。そして、自己対戦によって調整後のプログラムの棋力の向上を確認し、本手法の有効性を示した。
著者
川合 慧
出版者
一般社団法人情報処理学会
雑誌
情報処理 (ISSN:04478053)
巻号頁・発行日
vol.45, no.9, pp.962-969, 2004-09-15

プログラミングの問題には、見るからに難しそうなもの、少し考えれば分かるような気がするもの、コツが分かればあっけなく解けるもの、など、いろいろなものがある。特にやっかいなのは、見かけはやさしそうであるが具体的なプログラムを作ってみるとやたらと複雑になる種類の問題である。この「見かけ」は、多くの場合人間の先入観によることが多く、その中でも図形的な要素が寄与していることが多い。今回はその種の問題を取り上げる
著者
辰己 丈夫 中野 由章 野部 緑 川合 慧
雑誌
研究報告コンピュータと教育(CE)
巻号頁・発行日
vol.2009-CE-100, no.9, pp.1-8, 2009-06-27

大学生は、大学生にふさわしい情報リテラシーを身に付けるだけでなく、専門課程や卒業後も自律的にその能力を維持・更新し続ける基礎的な能力が求められる。だが、高校の情報科の現実の授業内容はパソコン操作スキルに偏っていて、そのことが、大学の一般情報教育に悪影響を与えている。ところで、アメリカ学術研究会議は、1999年に生涯に渡って情報技術を使い続けていくために十分な能力を「情報フルーエンシー」と名付け、その中身を提案した。本稿では、まず「情報フルーエンシー」の概念と内容を分析し、続いて、パソコン操作スキルではない一般情報教育を行なっている 3 つの大学の標準教科書と、情報フルーエンシーで提案された 30 項目の学習目標が、それらの教科書でどのように実現されているかを調査した。そして、その調査の結果を元に、大学の一般情報教育に情報リテラシーの目標を導入するためには、どのようなことが必要となるかを具体的に提案する。