はじめに

　最近Rustが面白いなーと思っていてちょっと使ってる．もうちょい書けるようになりたくて，なんか書く題材ないかなーと探してたらCodingameでRustが使えることに気がついた．

www.codingame.com

　あんまり探索したりするゲームAIって書いたこと無かったので，ちょうど良いと思いこの記事を参考にRustで書いてみた

　Rust初心者なのでここもっとうまく書けるよーとかってのあったら教えてください．

自殺しないAI

マクロ，定数

　標準入力からの取得，標準エラー出力への出力マクロがサンプルプログラムに記載されているのでありがたく利用する．定数は構造体みたいなのでまとめられるのかもしれないけどとりあえず列挙した．

macro_rules! print_err {
    ($($arg:tt)*) => (
        {
            use std::io::Write;
            writeln!(&mut ::std::io::stderr(), $($arg)*).ok();
        }
    )
}

macro_rules! parse_input {
    ($x:expr, $t:ident) => ($x.trim().parse::<$t>().unwrap());
}

const DX: [i32; 4] = [1, 0, -1, 0];
const DY: [i32; 4] = [0, 1, 0, -1];
const OUTPUT: [&'static str; 4] = ["RIGHT", "DOWN", "LEFT", "UP"];

const MAX_PLAYER_NUM: i32 = 4;
const COL: i32 = 30;
const ROW: i32 = 20;

構造体

　参考記事はJavaなので，Playerクラスの中にNodeクラスがあり，それぞれメソッドを持つという形になっている．

　Rustはオブジェクト指向ではなく，構造体を書き，それが関数を持つ（言い方正しいかな？）形になる．

というわけで次のような3つの構造体を作った．

Player : プレイヤーの状態を持つ
Node : あるターンのゲームの状態を持つ．前のターンのNodeへのリンクと，人数分のPlayer，今の状態のスコア，出力を持つ．
Game : ゲームの状態を持つ．最新のNodeへのリンクと，ゲームの参加者n，自分の番号pを持つ．

　今回，NodeのリンクはRcで持つようにした．Rc, RefCellについてはこの辺が参考になった．

mutなスマポ (BoxとかRcとかCellとか) - Qiita

#rustlang における構造体のmutabilityと`Cell/RefCell` - snyk_s log

　また，RefとかBoxとかRcとかRefCellとかわけわかめだったので Learning Rust With Entirely Too Many Linked Lists を写経した．Rustで色々なリストを実装していて，このへんのやつって実際こう使うのかーってわかって良かった．

type Link = Option<Rc<RefCell<Node>>>;

struct Game {
    head: Link,
    n: usize,
    p: usize,
}

#[derive(Eq, PartialEq, Clone)]
struct Node {
    parent: Link,
    score: i32,
    players: Vec<Player>,
    output: String,
}

#[derive(Eq, PartialEq, Clone)]
struct Player {
    x0: i32,
    y0: i32,
    x1: i32,
    y1: i32,
    locked_field: [[bool; ROW as usize]; COL as usize],
}

main

　というわけでこの3つの構造体をもとに関数を実装していった．まずはmain()．

fn main() {
    let mut game = Game::new();

    loop {
        game.input();
        let ans = game.search();
        println!("{}", ans.output);
    }
}

new

　次に，各構造体のnew()関数．Nodeは，親が与えられた場合はその情報をクローンしたものを作成するようにした．情報の追加，変更は作成した後に行う．

impl Game {
    fn new() -> Self {
        Game {
            head: None,
            n: 0,
            p: 0,
        }
    }
}

impl Node {
    fn new(parent: Option<Rc<RefCell<Self>>>) -> Rc<RefCell<Self>> {
        if let Some(parent) = parent {
            // create child
            Rc::new(RefCell::new(Node {
                parent: Some(parent.clone()),
                score: parent.borrow().score,
                players: parent.borrow().players.clone(),
                output: String::new(),
            }))
        } else {
            // create the first
            Rc::new(RefCell::new(Node {
                parent: None,
                score: 0,
                players: vec![],
                output: String::new(),
            }))
        }
    }
}

impl Player {
    fn new() -> Self {
        Player {
            x0: -1, y0: -1, x1: -1, y1: -1,
            locked_field: [[false; ROW as usize]; COL as usize]
        }
    }
}

input

　入力を取得し，情報を更新する．初回のみゲームの情報と最初のNodeを作り，以後は前ターンのNodeを親としてnew_nodeを作った後にPlayer情報を更新するようにした．最後にGame::headをnew_nodeに更新する．

impl Game {
    fn input(&mut self) {
        let new_node = Node::new(self.head.clone());

        // input game data
        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line).unwrap();
        if self.head.is_none() {
            // initialize game data & players
            let inputs = input_line.split(" ").collect::<Vec<_>>();
            self.n = parse_input!(inputs[0], usize);
            self.p = parse_input!(inputs[1], usize);
            new_node.borrow_mut().players = vec![Player::new(); self.n];
        }

        // input player data
        for i in 0..self.n {
            let mut input_line = String::new();
            io::stdin().read_line(&mut input_line).unwrap();
            let inputs = input_line.split(" ").collect::<Vec<_>>();

            let ref mut player = new_node.borrow_mut().players[i];
            player.x0 = parse_input!(inputs[0], i32);
            player.y0 = parse_input!(inputs[1], i32);
            player.x1 = parse_input!(inputs[2], i32);
            player.y1 = parse_input!(inputs[3], i32);
            player.locked_field[player.x0 as usize][player.y0 as usize] = true;
            player.locked_field[player.x1 as usize][player.y1 as usize] = true;
        }

        self.head = Some(new_node);
    }
}

search

　探索は， std::collections::BinaryHeap - Rust を利用して行う．処理内容は参考記事と同じになっている（たぶん）ので割愛．

　CodingameのRustバージョンが1.8.0で，RefCellにOrd，PartialOrdが実装されていない(1.10.0から)ためBinaryHeapに入れるとエラーが出る．そこで，Rc::try_unwrap(), RefCell::into_inner()を利用してRcとRefCellをはがし，Nodeを直接突っ込む．（この次のAIでは結局自分でOrd, PartialOrdを書いた）

impl Game {
    fn search(&self) -> Node {
        let mut heap = BinaryHeap::new();
        for i in 0..DX.len() {
            let next_node = Node::new(self.head.clone());
            next_node.borrow_mut().players[self.p].x1 += DX[i];
            next_node.borrow_mut().players[self.p].y1 += DY[i];
            next_node.borrow_mut().output = OUTPUT[i].to_string();
            let score = next_node.borrow().eval_player(self.p);
            next_node.borrow_mut().score += score;
            // because RefCell at 1.8.0 does not implemented Ord, push Node
            heap.push(Rc::try_unwrap(next_node).ok().unwrap().into_inner());
        }
        heap.pop().unwrap()
    }
}

eval

　評価についても参考記事と同じ．ここは割とサクッと書けた．

impl Node {
    fn eval_player(&self, p: usize) -> i32 {
        let x = self.players[p].x1;
        let y = self.players[p].y1;
        if self.players[p].can_move(x, y) {
            0
        } else {
            -1
        }
    }
}
impl Player {
    fn can_move(&self, x: i32, y: i32) -> bool {
        if 0 <= x && x < COL && 0 <= y && y < ROW && !self.locked_field[x as usize][y as usize] {
            true
        } else {
            false
        }
    }
}

最終コード

use std::io;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::rc::Rc;
use std::cell::RefCell;

macro_rules! print_err {
    ($($arg:tt)*) => (
        {
            use std::io::Write;
            writeln!(&mut ::std::io::stderr(), $($arg)*).ok();
        }
    )
}

macro_rules! parse_input {
    ($x:expr, $t:ident) => ($x.trim().parse::<$t>().unwrap());
}

const DX: [i32; 4] = [1, 0, -1, 0];
const DY: [i32; 4] = [0, 1, 0, -1];
const OUTPUT: [&'static str; 4] = ["RIGHT", "DOWN", "LEFT", "UP"];

// const MAX_PLAYER_NUM: i32 = 4;
const COL: i32 = 30;
const ROW: i32 = 20;

type Link = Option<Rc<RefCell<Node>>>;

struct Game {
    head: Link,
    n: usize,
    p: usize,
}

#[derive(Eq, PartialEq, Clone)]
struct Node {
    parent: Link,
    score: i32,
    players: Vec<Player>,
    output: String,
}

#[derive(Eq, PartialEq, Clone)]
struct Player {
    x0: i32,
    y0: i32,
    x1: i32,
    y1: i32,
    locked_field: [[bool; ROW as usize]; COL as usize],
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        self.score.cmp(&other.score)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.score.cmp(&other.score))
    }
}

impl Game {
    fn new() -> Self {
        Game {
            head: None,
            n: 0,
            p: 0,
        }
    }

    fn input(&mut self) {
        let new_node = Node::new(self.head.clone());

        // input game data
        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line).unwrap();
        if self.head.is_none() {
            // initialize game data & players
            let inputs = input_line.split(" ").collect::<Vec<_>>();
            self.n = parse_input!(inputs[0], usize);
            self.p = parse_input!(inputs[1], usize);
            new_node.borrow_mut().players = vec![Player::new(); self.n];
        }

        // input player data
        for i in 0..self.n {
            let mut input_line = String::new();
            io::stdin().read_line(&mut input_line).unwrap();
            let inputs = input_line.split(" ").collect::<Vec<_>>();

            let ref mut player = new_node.borrow_mut().players[i];
            player.x0 = parse_input!(inputs[0], i32);
            player.y0 = parse_input!(inputs[1], i32);
            player.x1 = parse_input!(inputs[2], i32);
            player.y1 = parse_input!(inputs[3], i32);
            player.locked_field[player.x0 as usize][player.y0 as usize] = true;
            player.locked_field[player.x1 as usize][player.y1 as usize] = true;
        }

        self.head = Some(new_node);
    }

    fn search(&self) -> Node {
        let mut heap = BinaryHeap::new();
        for i in 0..DX.len() {
            let next_node = Node::new(self.head.clone());
            next_node.borrow_mut().players[self.p].x1 += DX[i];
            next_node.borrow_mut().players[self.p].y1 += DY[i];
            next_node.borrow_mut().output = OUTPUT[i].to_string();
            let score = next_node.borrow().eval_player(self.p);
            next_node.borrow_mut().score += score;
            // because RefCell at 1.8.0 does not implemented Ord, push Node
            heap.push(Rc::try_unwrap(next_node).ok().unwrap().into_inner());
        }
        heap.pop().unwrap()
    }
}

impl Node {
    fn new(parent: Option<Rc<RefCell<Self>>>) -> Rc<RefCell<Self>> {
        if let Some(parent) = parent {
            // create child
            Rc::new(RefCell::new(Node {
                parent: Some(parent.clone()),
                score: parent.borrow().score,
                players: parent.borrow().players.clone(),
                output: String::new(),
            }))
        } else {
            // create the first
            Rc::new(RefCell::new(Node {
                parent: None,
                score: 0,
                players: vec![],
                output: String::new(),
            }))
        }
    }

    fn eval_player(&self, p: usize) -> i32 {
        let x = self.players[p].x1;
        let y = self.players[p].y1;
        if self.players[p].can_move(x, y) {
            0
        } else {
            -1
        }
    }
}

impl Player {
    fn new() -> Self {
        Player {
            x0: -1, y0: -1, x1: -1, y1: -1,
            locked_field: [[false; ROW as usize]; COL as usize]
        }
    }

    fn can_move(&self, x: i32, y: i32) -> bool {
        if 0 <= x && x < COL && 0 <= y && y < ROW && !self.locked_field[x as usize][y as usize] {
            true
        } else {
            false
        }
    }
}


fn main() {
    let mut game = Game::new();

    loop {
        game.input();
        let ans = game.search();
        println!("{}", ans.output);
    }
}

というわけで

　とりあえず自殺しないAIを書いた．記事が思ったより長くなったので次のAI（先読み，Chokudaiサーチ）は別に書く．

　Rustを書いていると，ここでは参照だけもらってーとか，いまこれをborrow_mut()したらだめとか，この変数はここで消えるからこれの参照持ったままじゃだめだとか，色々注意しながら書かなきゃいけないので~~疲れる~~面白い．変な構造にしてるとまともにコード書き進められなかったりして，ゆるふわな言語になれていると辛い面白い．逆にRustに慣れるとC/C++とか書いているときにメモリリークとか気がつきやすくなったりするかも．

　ただ，色々仕組みがあってすごい安全なのはわかるんだけど，初心者だとコンパイラに注意されても何が悪いのかわからなかったり，じゃあどう書けば・何を使えばいいんだよってのでハマるので，そのへんもっと情報が豊かになったらいいなーと思った．

　でもやっぱりなんとなく書いてて面白いです．

鉄分は大事。（特にヘム鉄）

こっち→ https://brookbach.com

RustでAI その１自殺しないAI