概要

Rustでしりとりを行う簡単なコマンドラインのプログラムを作ってみました。

構成

Rule: 利用可能な単語の一覧、禁止する最後の文字の一覧を定義します。
Judge: Rule に従って前の単語と今の単語からゲームが終了したかどうかを判別します。
Agent: 相手の単語を受け取って次の単語を出力するエージェント。自分の対戦相手。

詳細

文字列処理

しりとりでよく使う処理として単語の先頭と末尾の文字を取り出すというものが挙げられます。Rustでは文字列は&strやStringを使用しますが、文字はcharがUnicodeに対応しているのでを使用します。

pub fn get_first_char(s: &str) -> char {
    s.chars().next().unwrap()
}

pub fn get_last_char(s: &str) -> char {
    let last_char = s.chars().last().unwrap();
    match last_char {
        'ー' => {
            let (last_idx, _) = s.char_indices().last().unwrap();
            let new_str = &s[..last_idx];
            get_last_char(new_str)
        }
        'ァ' => 'ア',
        'ィ' => 'イ',
        'ゥ' => 'ウ',
        'ェ' => 'エ',
        'ォ' => 'オ',
        'ッ' => 'ツ',
        'ャ' => 'ヤ',
        'ュ' => 'ユ',
        'ョ' => 'ヨ',
        _ => last_char,
    }
}

文字列に対してcharsメソッドを使用することでcharの配列のようなChars型の変数が得られます。これに対してnextやlastを使用することで先頭とと末尾の文字が取得できます。なお、末尾に関しては長音符の場合は一つ前の文字を利用するという処理を再帰を用いて実現し、小さい仮名文字については通常の文字に直す処理をべた書きで入れています。とりあえず暗黙的にカタカナを仮定しています。

ゲームの進行判定


#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Rule {
    pub tokens: HashSet<String>,
    pub invalid_last_chars: HashSet<char>,
}

impl Rule {
    pub fn new(tokens: impl IntoIterator<Item = String>) -> Self {
        Self {
            tokens: tokens.into_iter().collect(),
            invalid_last_chars: HashSet::new(),
        }
    }

    pub fn with_invalid_last_chars(
        tokens: impl IntoIterator<Item = String>,
        invalid_last_chars: impl IntoIterator<Item = char>,
    ) -> Self {
        Self {
            tokens: tokens.into_iter().collect(),
            invalid_last_chars: invalid_last_chars.into_iter().collect(),
        }
    }
}

Rule は単語の一覧と禁止末尾文字の一覧で定義されます。

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum JudgeResult {
    // game is not over
    Continue,
    // current player is the loser
    Lose,
}

pub struct Judge {
    remained_token_map: HashMap<char, HashSet<String>>,
    invalid_last_chars: HashSet<char>,
}

impl Judge {
    pub fn new(rule: Rule) -> Self {
        let Rule {
            tokens,
            invalid_last_chars,
        } = rule;
        let mut remained_token_map: HashMap<char, HashSet<String>> = HashMap::new();
        for token in tokens {
            let first_char = get_first_char(&token);
            let token_set = remained_token_map
                .entry(first_char)
                .or_insert_with(HashSet::new);
            token_set.insert(token);
        }
        Self {
            remained_token_map,
            invalid_last_chars,
        }
    }

    fn remove_token(&mut self, token: &str) {
        let first_char = get_first_char(token);
        let token_set = self.remained_token_map.get_mut(&first_char).unwrap();
        token_set.remove(token);
    }

    pub fn make_judgement(&mut self, token: &str, previous_token: Option<String>) -> JudgeResult {
        // check if given token is empty
        if token.is_empty() {
            return JudgeResult::Lose;
        }

        // check if given token ends with invalid last char
        let last_char = get_last_char(token);
        if self.invalid_last_chars.contains(&last_char) {
            return JudgeResult::Lose;
        }

        let first_char = get_first_char(token);

        // check if given token starts with the last char of previous token
        if let Some(previous_token) = previous_token {
            let previous_last_char = get_last_char(previous_token.as_str());
            if previous_last_char != first_char {
                return JudgeResult::Lose;
            }
        }

        // check if given token exists in the remained map
        if self
            .remained_token_map
            .get(&first_char)
            .map(|tokens| !tokens.contains(token))
            .unwrap_or(false)
        {
            return JudgeResult::Lose;
        }

        // update remained map
        self.remove_token(token);
        JudgeResult::Continue
    }
}

Judgeは審判で、前の単語と現在の単語からゲームが進行できるかどうかを判断します。終了となる条件は以下の通りです。

現在の単語が空文字列
現在の単語の最後の文字が禁止リストに含まれる
現在の単語の先頭が前回の単語の末尾の文字から始まっていない
現在の単語が残りの使用可能単語リストに含まれていない

以上のいずれの条件にも当てはまらない場合は現在の単語を使用済みとして状態を更新します。

Agentの実装

Agentは以下のインターフェースとします。相手の単語を受け取り、新しい単語を返します。相手の単語はすでにJudgeによって問題ないと判別されていることを前提としています。

pub trait Agent {
    fn next_token(&mut self, token: &str) -> Option<String>;
}

今回は以下のように辞書を用いたシンプルなロジックを実装しました。


pub struct SimpleAgent {
    remained_token_map: HashMap<char, HashSet<String>>,
}

impl SimpleAgent {
    pub fn new(rule: Rule) -> Self {
        let mut remained_token_map: HashMap<char, HashSet<String>> = HashMap::new();
        for token in rule.tokens {
            let last_char = get_last_char(&token);
            if rule.invalid_last_chars.contains(&last_char) {
                continue;
            }
            let first_char = get_first_char(&token);
            let token_set = remained_token_map
                .entry(first_char)
                .or_insert_with(HashSet::new);
            token_set.insert(token);
        }
        Self { remained_token_map }
    }
}

impl Agent for SimpleAgent {
    fn next_token(&mut self, token: &str) -> Option<String> {
        // remove given token from remained map
        let first_char = get_first_char(token);
        let token_set = self.remained_token_map.get_mut(&first_char).unwrap();
        token_set.remove(token);

        // get next token
        let last_char = get_last_char(token);
        let token_set = self.remained_token_map.get(&last_char);
        let next_token = token_set
            .and_then(|s| s.iter().next())
            .map(|s| s.to_string())?;

        let first_char = get_first_char(next_token.as_str());
        let token_set = self.remained_token_map.get_mut(&first_char).unwrap();
        token_set.remove(next_token.as_str());

        Some(next_token)
    }
}

やっている内容としては

初めに与えられた単語の一覧を先頭の文字でグループ分けしておく
相手の単語の最後の文字を取り出し、この文字を先頭とするグループから一つ単語を取り出す

だけです。

全体

fn main() {
    // get args
    let args: Vec<String> = std::env::args().collect();
    let token_list_file = &args[1];
    let tokens = io::read_token_list(token_list_file);
    let rule = judge::Rule::with_invalid_last_chars(tokens, ['ン']);
    let mut judge = judge::Judge::new(rule.clone());
    let mut agent = agent::SimpleAgent::new(rule);
    let mut previous_token: Option<String> = None;
    // start game
    loop {
        // readline from stdin
        let mut player_token = String::new();
        std::io::stdin().read_line(&mut player_token).unwrap();
        player_token = player_token.trim().to_string();
        dbg!(&player_token);

        let result = judge.make_judgement(player_token.as_str(), previous_token);
        match result {
            JudgeResult::Lose => {
                println!("You lose!");
                break;
            }
            JudgeResult::Continue => {}
        }
        previous_token = Some(player_token);

        // agent's turn
        let agent_token = agent
            .next_token(previous_token.as_ref().unwrap())
            .unwrap_or_default();
        dbg!(agent_token.as_str());
        let result = judge.make_judgement(agent_token.as_str(), previous_token);
        match result {
            JudgeResult::Lose => {
                println!("You win!");
                break;
            }
            JudgeResult::Continue => {}
        }
        previous_token = Some(agent_token);
    }
}

コマンドライン引数として単語(UTF8)のリストのファイルパスを渡します。人間が先攻で標準入力から受け取り、審判に判定させ、エージェントも単語を出して審判が判断するというのを繰り返します。審判がゲーム終了と判定した際の単語が人間が出したものなら人間の負け、エージェント側のであれば人間の勝ちです。

ポケモンの名前の一覧をネット上で探してやってみました。

[src/main.rs:20] &player_token = "ピカチュウ"
[src/main.rs:36] agent_token.as_str() = "ウールー"
[src/main.rs:20] &player_token = "ルギア"
[src/main.rs:36] agent_token.as_str() = "アシレーヌ"
[src/main.rs:20] &player_token = "ヌラリヒョン"
You lose!

全然勝てません。。

今後の予定

木構造の探索等を用いて勝率が高くなるような単語を返す実装も作りたいです。(小並感)