Nishino TETSURO (西野 哲朗)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3400000, indirect: 1020000)
Computer Daihinmin involves playing Daihinmin, a popular card game in Japan, by using a player program. Because strong player programs of Computer Daihinmin use machine-learning techniques, such as the Monte Carlo method, predicting the program’s behavior is difficult. In this study, we extract the features of the player program through decision tree analysis. The features of programs are extracted by generating decision trees based on three types of viewpoints. To show the validity of our method, computer experiments were conducted. We applied our method to three programs with relatively obvious behaviors, and we confirmed that the extracted features were correct by observing real behaviors of the programs.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 基盤研究(C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: 1050000)
最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した．
続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした．
以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した．
このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た．
極大クリーク全列挙問題についてもさらに理論的，実験的に検討を続け，有効な進展結果を得た．

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 14200000, indirect: 4260000)
In this research, we focused on mistakes of human. We got the following research results by aiming at making game AI that makes human-like mistakes.
1) Classification by focusing on the cause of a mistake in human playing games.2) Proposal of a game AI with the model in consideration of human biological restrictions.3) Proposal and estimation of a game AI that adjust the strength in a game automatically and direct to a good game.4) Proposal of a game AI that realizes a human-like play by giving the "flow".
These research results bring new evaluation other than the directivity of "strength" to game AI and serve as new indicator to generate the various game AI.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
We have developed much faster algorithms for finding a maximum clique. These have been accomplished by introducing a near-maximum clique finding algorithm and by applying appropriately sorting and coloring vertices to the underlying branch-and-bound algorithm for finding a maximum clique. The effectiveness of the above algorithms has been confirmed by extensive computational experiments. In addition, we have also given a weaker condition under that the maximum clique problem can be solved in polynomial time in theory.
Our previous algorithm for enumerating maximal cliques has been extended to have algorithms for enumerating maximal pseudo-cliques. They are confirmed to work effectively for the analysis of networks.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
We have developed a polynomial-time algorithm for checking the equivalence of deterministic restricted one-counter transducers (DROCT's for short), which are deterministic pushdown transducers having just one stack symbol, that accept by final state with possible epsilon-moves. By extending this technique, we have also developed a polynomial-time algorithm for checking the inclusion of these DROCT's. Then, we have presented a polynomial-time algorithm for learning real-time DROCT's which accept by final state via membership and equivalence queries. Furthermore, we have shown that the regularity of the behavior of some programs for playing games of Daihinmin, which is one of card games, on computers can be extracted by using the EUREKA system which incorporated an identification algorithm of the class of k-reversible languages, which is a subclass of regular languages, for analyzing songs of the Bengalese finch.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 14700000, indirect: 4410000)
In this study, we construct various models of brain functions, such as motion, thinking and memory based on computational learning theory, and analyze their behavior in the following fashion: (1) we construct a state transition model for the motion and simulate the robot motion using this model, (2) we construct a neural network model for the memory and analyze its behavior, and (3) we design an efficient algorithm for card game playing using Monte Carlo Simulation. Finally we construct a unified methodology for simulating brain functions based on the above results.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3200000, indirect: 960000)
We developed some sufficient conditions and algorithms for arbitrary graphs by which the maximum clique problem can be solved in polynomial time. These algorithms can find an exact maximum clique in any arbitrary graph without any condition. We also confirmed experimentally that our newly developed another maximum-clique-finding algorithm works very efficiently. These algorithms were effectively applied for some problems as in bioinformatics.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 10900000, indirect: 3270000)
Songbird has been actively studied as a good model for their complex brain mechanism in song learning. Male Bengalese Finch learns singing by imitating external models. Birdsongs are strings of sounds as represented by sequence of alphabets. We implemented an automatic system which extracts a song grammar from a given phoneme data by using computational method, and use it to build a model of development processes of song grammars whose validity was checked by real data. Our experimental results suggest such kind of experiment on behavioral sequence is important to discover new knowledge.