[GDD2010][DevQuiz] Shiritoriのソースコード

Google Developer Day 2010のDevQuizで出題された「Shiritori」レベル3を解いた際に使用したソースコードです。言語にはPythonを使用しました。サーバの回答を入力すると、自分が答えるべき単語を出力するというスクリプトです。出力までには1～3分ほど時間がかかります。辞書は、スクリプトと同じディレクトリに以下の形式でdata.txtを置くことで設定します。

    * （単語1）
    * （単語2）
    * （単語3）
    * （以下同様）

本ソースコードでは、アルファベータ法を実装してみました。しかし、初めに作成したコードでは、レベル1やレベル2は突破できたものの、レベル3は単語の候補が多くなりすぎて、プログラムから全く回答が返ってこないという状態になってしまいました。

そこで先読みの深さを制限するほかに、枝刈りを行いました。例えば、axxb, ayyb, bxxa, byya

という辞書があったとし、サーバがaxxbを回答したとします。プレイヤーの候補はbxxaもしくはbyyaとなります。ところがそのどちらを選んでも、辞書の中にayybという、プレイヤーに再びbのつく単語を選ばせることのできる単語が存在するため、サーバはその単語を回答してくると予測できます。すると、プレイヤーの候補としてbxxa, byyaのそれぞれを候補としてその先の手を読むのではなく、どちらか一方、例えばbxxaだけの先の手を読むだけで十分です。このように、プレイヤーが前回と同じ文字を先頭に持つ単語を回答しなければならない状況になりうる単語が複数ある場合は、そのうちの1つのみを先読みの候補とし、それ以外は無視することで枝刈りを行いました。特にレベル3はこのような状況になる単語が大量にあるため、この枝刈りを行うことで、答えが全く返ってこなくなる状況から、1～3分待てば回答が返ってくるほどまでに進歩しました。

#!/usr/bin/env python
# coding: UTF-8

import re
import sys
import bisect

# 辞書のパス
DICTIONARY_FILE = u'data.txt'

# 辞書から単語を取り出すための正規表現。
WORD_PATTERN = re.compile(ur'\s*\*\s*(\w+)\s*')

# 探索を行う深さ
FIRST_DEPTH = 10

MAX_SCORE = sys.maxint
MIN_SCORE = -sys.maxint - 1

# 自分が勝ったことを表す
MY_WIN = MAX_SCORE - 1
# サーバが勝ったことを表す
SERVER_WIN = MIN_SCORE + 1

# ターンを表す定数
MY_TURN = 0
SERVER_TURN = 1

def compress_word(word):
    u"""
    単語を2文字に圧縮する。
    """
    if 2 < len(word):
        return word[0] + word[len(word) - 1]
    else:
        return word

class CompressedDictionary(list):
    u"""
    圧縮された単語からなる辞書。
    """
    def __init__(self, source_dictionary):
        self.extend([compress_word(a_word) for a_word in source_dictionary])
        self.sort()

    def __contains__(self, item):
        index = bisect.bisect_left(self, item)
        return index < len(self) and self[index] == item

    def clone(self):
        u"""
        本辞書を複製する。
        """
        return CompressedDictionary(self)

    def get_word(self, compressed_word, source_dictionary):
        u"""
        圧縮された辞書から元の単語を取り出す。
        """
        if compressed_word in self:
            for a_word in source_dictionary:
                if a_word[0] == compressed_word[0] and \
                        a_word[len(a_word) - 1] == compressed_word[1]:
                    return a_word
        else:
            raise ValueError()

    def remove(self, x):
        u"""
        辞書から単語を削除する。
        """
        index = bisect.bisect_left(self, x)
        if index < len(self) and self[index] == x:
            del self[index]
        else:
            raise ValueError()

    def remove_word(self, word):
        u"""
        辞書から単語を、未圧縮の単語を指定して削除する。
        """
        first_character = word[0]
        last_character = word[len(word) - 1]
        index = bisect.bisect_left(self, word)
        if index < len(self):
            candidate_word = self[index]
            if candidate_word[0] == first_character and \
                    candidate_word[1] == last_character:
                self.remove(candidate_word)
            else:
                raise ValueError()

def load_dictionary(dictionary_file):
    u"""
    辞書をファイルから読み込む。
    """
    dictionary = []
    with open(dictionary_file, 'r') as f:
        for a_line in f:
            match = WORD_PATTERN.match(a_line)
            if match:
                dictionary.append(match.group(1))
    return dictionary

def input_server_word(previous_word, dictionary):
    u"""
    サーバからの回答を入力する。
    """
    while True:
        print "Please input server's word."
        source_word = raw_input('---> ')
        word = compress_word(source_word)
        if word in dictionary:
            if previous_word:
                if previous_word[1] == word[0]:
                    return word
                else:
                    print '%s is invalid word. Please retry.' % (source_word)
            else:
                return word
        else:
            print '%s is not in dictioary. Please retry.' % (source_word)

def get_candidate_words(previous_word, current_dictionary):
    u"""
    回答の候補となる単語を返す。
    """
    previous_last_character = previous_word[1]
    return [a_word for a_word in current_dictionary
            if a_word[0] == previous_last_character]

def has_win_word(candidate_words, current_dictionary):
    u"""
    勝利できる単語が候補中にあるか否かを返す。
    勝利できる単語とは、末尾の文字を先頭に持つ単語が
    辞書の中にないような単語のことである。
    """
    for a_candidate in candidate_words:
        last_candidate_character = a_candidate[1]
        for next_candidate in current_dictionary:
            if next_candidate[0] == last_candidate_character:
                break
        else:
            return True
    else:
        return False

def get_dead_rate_in_bad_loop(candidate_words, current_dictionary):
    u"""
    ループになる可能性を返す。
    """
    dead_count = 0

    for my_candidate_word in candidate_words:
        alive = True
        my_candidate_first_character = my_candidate_word[0]
        for opponent_word in get_candidate_words(
                my_candidate_word, current_dictionary):
            if opponent_word[1] == my_candidate_first_character:
                dead_count += 1
    return float(dead_count) / len(candidate_words)

def get_frame_rate(previous_word, candidate_words):
    u"""
    ループにはめられている可能性を返す。
    """
    frame_count = 0

    target_character = previous_word[0]
    for my_candidate_word in candidate_words:
        if my_candidate_word[1] == target_character:
            frame_count += 1

    return float(frame_count) / len(candidate_words)

def calculate_score(turn, previous_word, current_dictionary):
    u"""
    スコアを計算する。
    """
    candidate_words = get_candidate_words(previous_word, current_dictionary)
    if 0 < len(candidate_words):
        if has_win_word(candidate_words, current_dictionary):
            if turn == MY_TURN:
                return MY_WIN
            elif turn == SERVER_TURN:
                return SERVER_WIN
            else:
                print u'失敗'
        else:
            score = 0
            dead_score = 50
            dead_rate = get_dead_rate_in_bad_loop(
                    candidate_words, current_dictionary)
            if dead_rate == 1:
                if turn == MY_TURN:
                    return SERVER_WIN
                elif turn == SERVER_TURN:
                    return MY_WIN
                else:
                    print u'失敗'
            score -= int(dead_score * dead_rate)
            frame_score = 100
            frame_rate = get_frame_rate(previous_word, candidate_words)
            score += int(frame_score * frame_rate)
            score *= len(candidate_words)
            if turn == MY_TURN:
                return score
            elif turn == SERVER_TURN:
                return -score
            else:
                print u'失敗'
    else:
        if turn == MY_TURN:
            return SERVER_WIN
        elif turn == SERVER_TURN:
            return MY_WIN
        else:
            print u'失敗'

def get_server_candidate_list(my_word, current_dictionary):
    u"""
    サーバが回答する可能性のある単語のリストを返す。
    """
    candidate_words = list(set(get_candidate_words(my_word, current_dictionary)))
    candidate_words.sort(lambda x, y: cmp(
            calculate_score(MY_TURN, x, current_dictionary),
            calculate_score(MY_TURN, y, current_dictionary)))
    return candidate_words

def is_loop(opponent_word, candidate_word, current_dictionary):
    u"""
    指定の単語でループに入るかどうかを返す。
    """
    last_loop_character = opponent_word[1]
    opponent_candidates = get_candidate_words(candidate_word, current_dictionary)
    for a_opponent_candidate in opponent_candidates:
        if a_opponent_candidate[1] == last_loop_character:
            return True
    else:
        return False

def select_server_word(history, dictionary, limit, depth):
    u"""
    サーバ側の回答を予測する。
    """
    my_word = history[len(history) - 1]
    current_dictionary = dictionary.clone()
    current_dictionary.remove(my_word)
    if depth == 0:
        return calculate_score(SERVER_TURN, my_word, current_dictionary), None
    score = MAX_SCORE
    word = None
    candidate_words = get_server_candidate_list(my_word, current_dictionary)
    if 0 < len(candidate_words):
        loop_candidates = [a_candidate for a_candidate in candidate_words
                if is_loop(my_word, a_candidate, current_dictionary)]
        for a_loop_candidate in loop_candidates:
            candidate_words.remove(a_loop_candidate)
        if 0 < len(loop_candidates):
            a_loop_candidate = loop_candidates[0]
            current_history = history[:] + [a_loop_candidate]
            candidate_score, _ = select_my_word(
                    current_history, current_dictionary, score, depth - 1)
            score = candidate_score
            word = a_loop_candidate
        if score != SERVER_WIN and limit <= score:
            for a_candidate_word in candidate_words:
                current_history = history[:] + [a_candidate_word]
                candidate_score, _ = select_my_word(
                        current_history, current_dictionary, score, depth - 1)
                if candidate_score < score:
                    score = candidate_score
                    word = a_candidate_word
                if score == SERVER_WIN or score <= limit:
                    break
        return score, word
    else:
        return MY_WIN, None

def get_my_candidate_list(server_word, current_dictionary):
    u"""
    自分が回答できる単語のリストを返す。
    """
    candidate_words = list(set(get_candidate_words(server_word, current_dictionary)))
    candidate_words.sort(lambda x, y: cmp(
            calculate_score(SERVER_TURN, x, current_dictionary),
            calculate_score(SERVER_TURN, y, current_dictionary)))
    candidate_words.reverse()
    return candidate_words

def select_my_word(history, dictionary, limit, depth):
    u"""
    自分の回答を予測する。
    """
    server_word = history[len(history) - 1]
    current_dictionary = dictionary.clone()
    current_dictionary.remove(server_word)
    if depth == 0:
        return calculate_score(MY_TURN, server_word, current_dictionary), None
    score = MIN_SCORE
    word = None
    candidate_words = get_my_candidate_list(server_word, current_dictionary)
    if 0 < len(candidate_words):
        loop_candidates = [a_candidate for a_candidate in candidate_words
                if is_loop(server_word, a_candidate, current_dictionary)]
        for a_loop_candidate in loop_candidates:
            candidate_words.remove(a_loop_candidate)
        if 0 < len(loop_candidates):
            a_loop_candidate = loop_candidates[0]
            current_history = history[:] + [a_loop_candidate]
            candidate_score, _ = select_server_word(
                    current_history, current_dictionary, score, depth - 1)
            score = candidate_score
            word = a_loop_candidate
        if score != MY_WIN and score <= limit:
            for a_candidate_word in candidate_words:
                current_history = history[:] + [a_candidate_word]
                candidate_score, _ = select_server_word(
                        current_history, current_dictionary, score, depth - 1)
                if score < candidate_score:
                    score = candidate_score
                    word = a_candidate_word
                if candidate_score == MY_WIN or limit <= score:
                    break
        return score, word
    else:
        return SERVER_WIN, None

def calculate_my_word(server_word, dictionary, max_depth):
    u"""
    次に出すべき単語を求める。
    """
    score, my_word = select_my_word([server_word], dictionary, MAX_SCORE, max_depth)
    return my_word

def main():
    source_dictionary = load_dictionary(DICTIONARY_FILE)
    dictionary = CompressedDictionary(source_dictionary)

    server_word = input_server_word(None,dictionary)
    current_dictionary = dictionary.clone()
    depth = FIRST_DEPTH
    turn = 1

    while True:
        my_word = calculate_my_word(server_word, current_dictionary, depth)
        current_dictionary.remove_word(server_word)
        select_word = current_dictionary.get_word(my_word, source_dictionary)
        print 'Select %s' % (select_word)
        print '\n'
        current_dictionary.remove(my_word)
        server_word = input_server_word(my_word, current_dictionary)
        turn += 1

if __name__ == '__main__':
    main()