ヌメロンのAI作った
ブログに慣れるのも兼ねて、以前作ったコマンドラインで遊べるヌメロンを紹介します。
・ヌメロンって何
簡単にいうと数当てゲームみたいな感じ。基本ルールは以下。
- それぞれのプレイヤーが、0-9までの数字が書かれた10枚のカードのうち3枚を使って、3桁の番号を作成する。カードに重複は無いので「550」「377」といった同じ数字を2つ以上使用した番号は作れない。
- 先攻のプレイヤーは相手の番号を推理してコールする。相手はコールされた番号と自分の番号を見比べ、コールされた番号がどの程度合っているかを発表する。数字と桁が合っていた場合は「EAT」（イート）、数字は合っているが桁は合っていない場合は「BITE」（バイト）となる。
- 例として相手の番号が「765」・コールされた番号が「746」であった場合は、3桁のうち「7」は桁の位置が合致しているためEAT、「6」は数字自体は合っているが桁の位置が違うためBITE。EATが1つ・BITEが1つなので、「1EAT-1BITE」となる。
- これを先攻・後攻が繰り返して行い、先に相手の番号を完全に当てきった（3桁なら3EATを相手に発表させた）プレイヤーの勝利となる。
今回は多少一般化して、n文字の中からm文字を使って、m桁の文字列を作成できることにする。
例えば、16進数(0-9, A-F)から5文字選ぶとすると"369AF"のような文字列を当てるゲームになる。
・ゲーム例
ルール: 10進数、3桁
自分 (345) 相手 (157)
自分「129」相手「1E0B」
相手「035」自分「1E1B」
自分「567」相手「1E1B」
相手「024」自分「0E1B」
自分「256」相手「1E0B」
相手「532」自分「1E1B」
自分「157」相手「3E0B」
自分の勝利！！！
・CPU側のアルゴリズム
いかに早く答えの候補を絞り込めるかが重要となる。それにはいかに相手から情報を得るか、情報を得るための番号をコールするかが肝である。
自分が番号をコールすることで候補がp倍に絞られる時、このpの値が小さければ小さいほど良い情報が得られたことになる。ここで選択情報量という概念を考える。
選択情報量の平均（エントロピー）を考える。
ここでのは考えられうる相手の発表の集合( ex. 0E0B, 0E1B, ...) で、
はその要素である。
は現時点での解答の候補が同様に確からしいと考えた時に
という発表が返ってくる確率である。
これを最大化するコールを考える。実装上は計算量の関係で解答候補が多すぎる場合のエントロピーの計算を簡略化しています。（もっとうまくやりたい）
・プログラム
まず、基本となる処理を記述。
CHARSで使う文字、DIGITで文字数を指定している。
common.py
#!/usr/bin/env python
# coding: utf-8
from collections import Counter
import numpy as np
CHARS = '1234567890'
DIGITS = 5
class Judge(object):
eat = 0
bite = 0
def __repr__(self):
return 'eat: {}, bite: {}'.format(self.eat, self.bite)
def __eq__(self, other):
return self.eat == other.eat and self.bite == other.bite
def __ne__(self, other):
return not (self.eat == other.eat and self.bite == other.bite)
def __hash__(self):
return self.eat * 1e4 + self.bite
def coincidence(n1, n2):
"""
n1とn2の一致度を測る
"""
j = Judge()
for i, n in enumerate(n1):
if n == n2[i]:
j.eat += 1
elif n in n2:
j.bite += 1
return j
def is_valid_number(number, digits, chars):
if len(number) != digits:
return False
if len(number) != len(set(number)):
return False
for v in number:
if not v in chars:
return False
else:
return True
def entropy(num, num_list):
"""
num_listが答えの候補である時にnumをcallすることで得られる情報量
Parameters
----------
num : list(str)
num_list : list(list(str))
Returns
----------
entropy: list(int)
"""
n = len(num_list)
j_list = [coincidence(num_, num).__hash__() for num_ in num_list]
counter = Counter(j_list)
pr = [x * 1.0 / n for x in counter.values()]
return sum(map(lambda p: p * -np.log2(p), pr))
AIの実装
agent.py
#!/usr/bin/env python
# coding: utf-8
from itertools import permutations
from numpy.random import shuffle
from random import choice
import copy
from common import *
class NumeronAgent(object):
"""
Numeron Player(AI)
"""
def __init__(self, number=None):
self.candidate = [''.join(i) for i in permutations(CHARS, DIGITS)]
if number is None:
number = choice(self.candidate)
if type(number) in [str, int]:
number = list(str(number))
self.number = number
self.turn = 1
assert len(number) == DIGITS
self.all_candidate = copy.deepcopy(self.candidate)
def reply_coincidence(self, opponent_call_number):
"""
相手の宣言した数字に対し、eatとbiteの数を返す
Parameters
----------
opponent_call_number : list(str) 相手の宣言した数字
Returns
-------
Judge eatとbiteの数
"""
return coincidence(self.number, opponent_call_number)
def decide_call_number(self, max_num=1000):
"""
次の宣言する数字を決める
Parameters
----------
max_num : int 探索数
Returns
-------
call_number : list(str) 最もエントロピーが高くなる数字
"""
if self.turn > 1:
shuffle(self.candidate)
if len(self.candidate) <= max_num:
array = self.candidate + self.all_candidate[:max_num - len(self.candidate)]
else:
shuffle(self.all_candidate)
array = self.all_candidate[:max_num]
entropy_list = map(lambda x: entropy(x, self.candidate[:max_num]), array)
call_number = array[np.argmax(entropy_list)]
else:
call_number = choice(self.candidate)
print('call number: {}'.format(call_number))
return call_number
def update_candidate(self, judge, call_number):
"""
候補を更新
Parameters
----------
judge : Judge 今回のeatとbite
call_number : list(str) 今回の宣言した数字
"""
self.candidate = filter(lambda x: coincidence(
x, call_number) == judge, self.candidate)
def action(self, opponent):
"""
1ターンの一連のアクションを行う
Parameters
----------
opponent : NumeronAgent
"""
call_number = self.decide_call_number()
j = opponent.reply_coincidence(call_number)
print(j)
if j.eat == DIGITS:
print('WIN!!!')
exit()
self.update_candidate(j, call_number)
print('candidate: {}'.format(len(self.candidate)))
self.turn += 1
class NumeronHumanAgent(NumeronAgent):
"""
Numeron Player(人間)
"""
def __init__(self):
number = self.input_number('please set your number (digits = {}): '.format(DIGITS))
assert len(number) == DIGITS
NumeronAgent.__init__(self, number)
def input_number(self, message):
while True:
number = list(raw_input(message))
if is_valid_number(number, DIGITS, CHARS):
return number
else:
print('invalid number')
def decide_call_number(self, max_num=1000):
number = self.input_number('call number: ')
assert len(number) == DIGITS
return number
main.py
#!/usr/bin/env python
# coding: utf-8
from agent import NumeronAgent, NumeronHumanAgent
class Game(object):
"""
Numeron対戦用クラス
"""
def __init__(self, player1, player2):
self.player1 = player1
self.player2 = player2
def main(self):
nof_turns = 1
while True:
print('---------- Turn {} ----------'.format(nof_turns))
print('---- pleyer1\'s turn ----')
player1.action(player2)
print('---- pleyer2\'s turn ----')
player2.action(player1)
nof_turns += 1
if __name__ == '__main__':
player1 = NumeronHumanAgent()
player2 = NumeronAgent()
game = Game(player1, player2)
game.main()
強さは自分と互角くらいでした。まあ運もあるのでわかんないですけど。桁数が多くなってくると叶わなくなります。
ただゲームの性質上これ以上強くなり得るのだろうか・・特殊ルールが入ってきたら変わってくるかも。
暇な人は試してみてください。
