ブログ移行します

brookbach.com

自分のドメインを有効活用したいと思っていて，今年からきちんとこちらで書くようにしたので移行します．ぶっちゃけはてなブログの方が機能そろってたり色々便利な部分もあるんだけど，まぁそこをDIYするのも楽しみということで．

RustでAIその2 続き

概要

前回

brookbach.hatenablog.com

の続き，だいぶ間があいちゃったのでとりあえず雑だけど投稿してみる

数手先読み

• 数手先読みする
• SEARCH_DEPTHを定義
• 1.8.0ではRefCellにOrdが定義されていないのでRefNode(RefCell)として定義
• RefNodeはタプルなので，borrow, borrow_mut,into_innerを呼び出されたときに中身をそのまま呼ぶ関数を定義

#[derive(Eq, PartialEq, Debug)]
struct RefNode(RefCell<Node>)
impl PartialOrd for RefNode {
    fn partial_cmp(&self, other: &RefNode) -> Option<Ordering> {
        self.0.borrow().partial_cmp(&*other.0.borrow())
    }

    fn lt(&self, other: &RefNode) -> bool {
        *self.0.borrow() < *other.0.borrow()
    }

    #[inline]
    fn le(&self, other: &RefNode) -> bool {
        *self.0.borrow() <= *other.0.borrow()
    }

    #[inline]
    fn gt(&self, other: &RefNode) -> bool {
        *self.0.borrow() > *other.0.borrow()
    }

    #[inline]
    fn ge(&self, other: &RefNode) -> bool {
        *self.0.borrow() >= *other.0.borrow()
    }
}

impl Ord for RefNode {
    #[inline]
    fn cmp(&self, other: &RefNode) -> Ordering {
        self.0.borrow().cmp(&*other.0.borrow())
    }
}

impl RefNode {
    fn borrow(&self) -> Ref<Node> {
        self.0.borrow()
    }

    fn borrow_mut(&self) -> RefMut<Node> {
        self.0.borrow_mut()
    }

    fn into_inner(self) -> Node {
        self.0.into_inner()
    }
}

定義できたら，元記事を参考に幅優先探索を実装

探索後，一番スコアが高いノードの親ノードまでトラバース この時点の親ノードは，Rc(RefNode)となっているので，Rc::try_unwrapでRcをはがしてからRefNodeの中身をinto_innerで取り出す

search関数はこんな感じ

    fn search(&mut self) -> Node {
        let mut heap = BinaryHeap::new();

        heap.push(self.head.clone().unwrap());
        for _ in 0..SEARCH_DEPTH {
            let mut tmp = heap.clone();
            heap.clear();

            while let Some(current_node) = tmp.pop() {
                for i in 0..DX.len() {
                    let next_node = Node::new(Some(current_node.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_mut().eval_player(self.p);
                    next_node.borrow_mut().score += score;
                    heap.push(next_node.clone());
                }
            }
        }

        // the top of heap is the best result after search
        let mut node = heap.pop().unwrap();
        // traverse until the next of head
        loop {
            let next_node;
            match node.borrow_mut().parent.take() {
                Some(parent) => {
                    next_node = parent;
                }
                None => { panic!(); }
            }
            if next_node == self.head.clone().unwrap() {
                break;
            }
            node = next_node;
        }
        heap.clear();
        Rc::try_unwrap(node).ok().unwrap().into_inner()
    }

ビームサーチ版

ヒープをビーム幅に縮小する以外は同じ

    fn search(&mut self) -> Node {
        let mut heap = BinaryHeap::new();

        heap.push(self.head.clone().unwrap());
        for _ in 0..SEARCH_DEPTH {
            let mut tmp = BinaryHeap::new();
            for _ in 0..BEAM_WIDTH {
                if let Some(data) = heap.pop() {
                    tmp.push(data);
                } else {
                    break;
                }
            }
            heap.clear();

            while let Some(current_node) = tmp.pop() {
                for i in 0..DX.len() {
                    let next_node = Node::new(Some(current_node.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_mut().eval_player(self.p);
                    next_node.borrow_mut().score += score;
                    heap.push(next_node.clone());
                }
            }
        }

        // the top of heap is the best result after search
        let mut node = heap.pop().unwrap();
        // traverse until the next of head
        loop {
            let next_node;
            match node.borrow_mut().parent.take() {
                Some(parent) => {
                    next_node = parent;
                }
                None => { panic!(); }
            }
            if next_node == self.head.clone().unwrap() {
                break;
            }
            node = next_node;
        }
        heap.clear();
        Rc::try_unwrap(node).ok().unwrap().into_inner()
    }

最終版

use std::io;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::rc::Rc;
use std::cell::{Ref, RefMut, 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;

const SEARCH_DEPTH: usize = 100;
const BEAM_WIDTH: usize = 20;

#[derive(Eq, PartialEq, Debug)]
struct RefNode(RefCell<Node>);

type Link = Option<Rc<RefNode>>;

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

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

#[derive(Eq, PartialEq, Debug, 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 PartialOrd for RefNode {
    fn partial_cmp(&self, other: &RefNode) -> Option<Ordering> {
        self.0.borrow().partial_cmp(&*other.0.borrow())
    }

    fn lt(&self, other: &RefNode) -> bool {
        *self.0.borrow() < *other.0.borrow()
    }

    #[inline]
    fn le(&self, other: &RefNode) -> bool {
        *self.0.borrow() <= *other.0.borrow()
    }

    #[inline]
    fn gt(&self, other: &RefNode) -> bool {
        *self.0.borrow() > *other.0.borrow()
    }

    #[inline]
    fn ge(&self, other: &RefNode) -> bool {
        *self.0.borrow() >= *other.0.borrow()
    }
}

impl Ord for RefNode {
    #[inline]
    fn cmp(&self, other: &RefNode) -> Ordering {
        self.0.borrow().cmp(&*other.0.borrow())
    }
}

impl RefNode {
    fn borrow(&self) -> Ref<Node> {
        self.0.borrow()
    }

    fn borrow_mut(&self) -> RefMut<Node> {
        self.0.borrow_mut()
    }

    fn into_inner(self) -> Node {
        self.0.into_inner()
    }
}

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 & create new 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 as usize];
        }

        // input player data
        for i in 0..self.n as usize {
            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);
        }
        for i in 0..self.n as usize {
            let x0 = new_node.borrow().players[i].x0;
            let y0 = new_node.borrow().players[i].y0;
            let x1 = new_node.borrow().players[i].x1;
            let y1 = new_node.borrow().players[i].y1;
            for j in 0..self.n as usize {
                new_node.borrow_mut().players[j].locked_field[x0 as usize][y0 as usize] = true;
                new_node.borrow_mut().players[j].locked_field[x1 as usize][y1 as usize] = true;
            }
        }

        self.head = Some(new_node);
    }

    fn search(&mut self) -> Node {
        let mut heap = BinaryHeap::new();

        heap.push(self.head.clone().unwrap());
        for _ in 0..SEARCH_DEPTH {
            let mut tmp = BinaryHeap::new();
            for _ in 0..BEAM_WIDTH {
                if let Some(data) = heap.pop() {
                    tmp.push(data);
                } else {
                    break;
                }
            }
            heap.clear();

            while let Some(current_node) = tmp.pop() {
                for i in 0..DX.len() {
                    let next_node = Node::new(Some(current_node.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_mut().eval_player(self.p);
                    next_node.borrow_mut().score += score;
                    heap.push(next_node.clone());
                }
            }
        }

        // the top of heap is the best result after search
        let mut node = heap.pop().unwrap();
        // traverse until the next of head
        loop {
            let next_node;
            match node.borrow_mut().parent.take() {
                Some(parent) => {
                    next_node = parent;
                }
                None => { panic!(); }
            }
            if next_node == self.head.clone().unwrap() {
                break;
            }
            node = next_node;
        }
        heap.clear();
        Rc::try_unwrap(node).ok().unwrap().into_inner()
    }
}

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

        Rc::new(RefNode(RefCell::new(new_node)))
    }

    fn eval_player(&mut self, p: usize) -> i32 {
        let x = self.players[p].x1;
        let y = self.players[p].y1;
        if self.players[p].can_move(x, y) && self.score >= 0 {
            self.players[p].locked_field[x as usize][y as usize] = true;
            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 x >= 0 && x < COL && y >= 0 && 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);
    }
}

感想

コンパイラがきちんと指摘してくれるの，それはそうなんだけど，アルゴリズムの部分とかが間違ってると結局正常には動かなくて逆にうるさく指摘される分そちらに注力してしまってアルゴリズムに集中できないような気がする．ただコンパイラのチェックを通るとその部分に対しては変なバグが発生することがなくて安心．

まぁ慣れればそこで間違えることはなくなるんだろう（実際今回も書いてくうちにどうすればいいかなんとなくわかってミスは減った（気がする））． けどやっぱ学習曲線が険しいなぁと．

rubyのpryとか，Haskellのghciみたいに，型とかライフタイムとか借用周りとか今どうなってるのか見れるREPLが欲しい．

たぶんもっと慣れてる人は，そのへんをほとんど無意識に適用できるようになってる気がするので，そういう人達の知見をグラフィカルな形で初心者にもわかりやすく説明してくれるツールがほしいんじゃ

ライフタイムとか，所有権がどこに行くかとかどこにあるかとかアニメーションで表示したりできないのかなと．

まとめると，Rust書いてて面白いし安全に極振りしてるの重要視されないかもだけど実は大事なのでもっとメジャーになるといいなと思いました．

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

はじめに

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

www.codingame.com

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

qiita.com

　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++とか書いているときにメモリリークとか気がつきやすくなったりするかも．

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

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

情報系の大学生の自分が2016年に読んだ本のまとめ

はじめに

　2016年に読んだ本を備忘録として書いていく．2015年の記事はこれ．

brookbach.hatenablog.com

本

　以下のようにざっくりとしたジャンルにわけて本の簡単な感想を書く．

• 知恵・知識
• 情報系
• 小説
• 漫画

知恵・知識

アイデアのつくり方

　旅行に行く飛行機の中で2時間ぐらいで読めた．情報収集→整理→思考→ひらめき→出力っていう流れを踏むこと，言われてみれば確かにって感じだけど実践するのは難しい．

　あと，ひらめいたものを実際に作ると思ってたよりしょぼくて落胆するってのはあるあるだと思った．

理科系の作文技術 (中公新書 (624))

　論文とかの文章の書き方についての本．最初に出版されたのが結構前（1970年ぐらい）なので，ちょっと情報が古いかも．でも基本は変わってない．

　ちゃんと文章を書き始める前に読んだのであんまり内容を覚えてない，今読んだら違う感想持つかも

「分かりやすい表現」の技術―意図を正しく伝えるための16のルール (ブルーバックス)

　標識，説明書，ポスターなど多くの人が見るものに対して，どういう形のものがわかりやすいのか，わかりにくいものはなぜわかりにくいのかをきちんと解説している．外野からみたらすごいわかりにくくても作ってる人にはそれわかんないんだよね

本を読む本 (講談社学術文庫)

　何か読むもの，特に本を対象とした読み方についての本．流し読み，点検読書，分析読書，シントピカル読書っていう流れに沿って本の読み方を解説しており，各段階において，どういうことに意識しながら読んでいけば良いのかが書いてある．

　無意識にやっていることもあったけど，この本に書いてある手法は難しい本，論文とかを読むときの助けになると思う．また，良い読み方って良い書き方でもあるんだなーと思った． 　定期的に本を読むようになっていて良いタイミングで読めた．それと，小説については世界に入りこむことが大事って書いてあってちょっと意外だった．

ご冗談でしょう、ファインマンさん〈上〉 (岩波現代文庫)

　ファインマンという物理学者のエッセイ本で，難しい物理の話ではなく，この人の自伝的な本．歴史的な話とか，知識に関する話とかが書いてあって読んでてためになるし面白かった．通しての感想は，この人知的好奇心がすごいなーと思った．

予想どおりに不合理: 行動経済学が明かす「あなたがそれを選ぶわけ」 (ハヤカワ・ノンフィクション文庫)

　行動経済学の本．机の上で考えてみると不合理なのに，実験してみるとなぜか人々はそう動いてしまうんだよねって話．無料でアメを配るのと1円で配るのとでは人が持って行く数が大きく違ったり，冷静なときに予想する自分が興奮しているときの状態と，実際に自分が興奮しているときの状態は全然違ったりとか，あー言われてみればそういうことあるわっていう話がたくさん書いてある．

　読んだ後，ものを見る視点が少し変わった気がする．それが幸せかどうかはわからない．

ゼロからトースターを作ってみた結果 (新潮文庫)

　イギリスの大学生が，ゼロからトースターを作る話．鉄とか銅を鉱石取ってくるところから始めて面白い．ゼロからだと，プラスチックの方が鉄より作るの難しいっていうのは値段と比例してなくて面白いと思った（civilizationでもプラスチックの方が金属より後だしね）．身の回りにあるものを実際に作ってみろって言われたら難しいんだなーと．

パパラギ はじめて文明を見た南海の酋長ツイアビの演説集 (SB文庫)

　南海の酋長が，文明社会（西洋文化）に触れて考えたことを書いた本．物，お金，家とかを持って自慢げにしてるけどおまえらそんなの間違ってるぜ，っていっている．この人の言っていることはすごいわかるし，この人の過ごしているような環境で生きていた方が幸せなのではとは思う．でも，ここまで進んでしまった今の社会ではそれはもう難しいんだよなぁと思った．

情報系

コンピュータネットワークセキュリティ

　学科の授業の教科書として購入，主にネットワークにおいて，どんな攻撃があるのか，それに対してどんな防御方法があるのかをさらっと解説している．教科書っぽい感じはあるけど割と読みやすかった．

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

　ちょくだいさんというAtcoderの社長が何年か前に書いた競技プログラミングの入門本．競プロ強くなりたいなーと思ってとっかかりとして読んだ．強くなりたい

　競プロは本読むより問題解いた方が強くなるだろうなーと思ってる．これを読むよりAtCoderのABCを解きつつ解説読んだ方がためになるかも

UNIXという考え方―その設計思想と哲学

　UNIXについて，どういう考え方でこのOSができているのか，いくつかのポイントに分けて簡潔にまとまっている．自分がちょっとしたプログラムを書くときとかに参考になることが書かれていて，読んでいてためになった．

[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

nginx実践入門 (WEB+DB PRESS plus)

Redis入門 インメモリKVSによる高速データ管理

　ISUCON本戦に参加するにあたり読んだ本たち．この中では大規模サービス技術入門が一番ためになった．どうしても大規模なアプリの，しかもインフラに触る機会って学生だとほとんどないから，ISUCONに参加したり本を読んだりしたことでなんとなく理解できて良かった．働くようになって実際にそういうのを作るようになったらまた読みたい．

暗号技術入門 第3版 秘密の国のアリス

　シーザー暗号から，楕円曲線暗号まで，それがどういうアルゴリズムで動いていて，どう作るのか，どう破られるのかしっかり書いてある本．サイモン・シン先生が書いた暗号解読は歴史，物語的な面に重点をおいていたが，この本は技術面に重点をおいている．両方読むと知識がマージされていいと思った．

ハッカーと画家 コンピュータ時代の創造者たち

　ポール・グレアムさんが書いたハッカーに関するエッセイ集．ハッカーとしての心構えとか，ソフトに関すること，デザインに関することとか幅広い分野の話が書いてあって面白い．熱いLisp推し． ここ http://practical-scheme.net/wiliki/wiliki.cgi?naoya_t%3Aポール・グレアムのエッセイと和訳一覧 にこの人の書いたエッセイの日本語訳がまとまっているのでこれを読んで主も白かったらこの本も面白いと思う．

小説

カラマーゾフの兄弟〈上〉 (新潮文庫)

　去年の暮れぐらいから読み始めて3月ぐらいに読み終わった．出てくる登場人物がみな一癖あるんだけど，ああこういう人いるなぁって感じの人ばかりで面白かった．自分は次男に一番共感したかなー．

車輪の下 (新潮文庫)

「詩人になれないのなら，何にもなりたくない」とかいう超名言を残したヘルマンヘッセが書いた半自伝小説．これは主人公にシンパシーを感じて，もし自分も大学を退学してたらこんなふうになってたかなーと思った．

　こういう歴史の教科書にでてくるような，名前は知ってるけど読んだことが無いっていう本を少しづつ読んでいきたいと思っている．

青の炎 (角川文庫)

　主人公は名門高校に通っていて，美人な母と妹，居候同然の養父と一緒に住んでいる．ミステリーものなんだけど心理描写多め．嫌な父親から母と妹を守るために，青年の熱い思いがどんどん燃え上がっていく．そして……

空飛ぶ馬 (創元推理文庫―現代日本推理小説叢書)

　いわゆる人の死なない推理小説．女子大生の主人公がなんかしら面白い題材を見つけて，それを知り合いの落語家に話に行く，という流れで短編集みたいになっている．平和でまったりした雰囲気だけど推理要素もちゃんとあって面白い．

　途中まで読んで何年か積んでたんだけど今年読んだ．なんで積んでたのかなーと考えたんだけど，推理自体は面白いんだけど主人公の自分語りがちょっと苦手だったからだと思う．

極大射程 上 (扶桑社ミステリー)

　凄腕の孤独なスナイパーが，謎の組織から謎の依頼をされ，気がついたら暗殺容疑で指名手配されたので謎を解明しつつ復讐していく話．ハードボイルド・・・って感想を持った．主人公が罠をかいくぐりつつかっこよく立ち向かっていって面白い．

　映画も見たんだけど，原作では頼りになる相棒がへっぽこになってたり，主人公が銃撃と爆発で無双していたりと，ミステリー&ハードボイルドな原作が完全にアメリカンアクション映画になっていて完全に別物．でも嫌いじゃない

推定無罪〈上〉 (文春文庫)

　弁護士の主人公が殺人の容疑を掛けられて，しかも被害者は実は主人公の浮気相手で……という話．雰囲気大人向け逆転裁判って感じで面白かった．推理物は面白いんだけど感想があまり書けなくてつらい，読んだ人同士で話したい

すばらしい新世界 (講談社文庫)

　完全なる階層社会，高度な機械文明のなかで生きる人の話を書いたディストピア小説．ディストピア小説のはずなんだけど，なんかこの小説の世界も悪くない，むしろ今よりましな部分もあるんじゃないかなとか思ってしまった．ただそれは階層の上の方の意見なのかな

漫画

　今年読んだ（読みはじめた）漫画．個々に感想を書くのがめんどかったので，ざっくりとしたジャンルにわけてジャンル毎に簡単なコメントを書く．

読んだ中では，

• 煩悩寺
• 乙嫁語り
• 波よ聞いてくれ

が大ヒットだった．

登場人物が男女問わずかわいい・いやされる

恋は光 1 (ヤングジャンプコミックスDIGITAL)

煩悩寺 1<煩悩寺> (コミックフラッパー)

金の彼女　銀の彼女（１） (月刊少年マガジンコミックス)

からかい上手の高木さん 1 (ゲッサン少年サンデーコミックススペシャル)

ストレッチ（１） (ビッグコミックススペシャル)

亜人ちゃんは語りたい（１） (ヤングマガジンコミックス)

ごちそうは黄昏の帰り道 1 (マーガレットコミックスDIGITAL)

かぐや様は告らせたい?天才たちの恋愛頭脳戦? 1 (ヤングジャンプコミックスDIGITAL)

シャーリー 1巻<シャーリー> (ビームコミックス（ハルタ）)

エマ 1巻<エマ> (ビームコミックス（ハルタ）)

乙嫁語り 1巻<乙嫁語り> (ビームコミックス（ハルタ）)

つぐもも ： 1 (アクションコミックス)

恋は雨上がりのように（１） (ビッグコミックス)

甘々と稲妻（１） (アフタヌーンコミックス)

ふらいんぐうぃっち（１） (週刊少年マガジンコミックス)

ＮＥＷ　ＧＡＭＥ！　１巻 (まんがタイムKRコミックス)

　あーこの人たち本当にかわいいなーとか思いながら読んでいた．かわいいなーとか思って読んでるけど，ちゃんと内容も濃くて面白いのが多い．ひとまとめにしてしまったけどそれぞれ違った良さがあるので片っ端から読むと良いです

おっさん・おねえさんがかっこいい

ディメンション W 1巻 (デジタル版ヤングガンガンコミックスSUPER)

無限の住人（１） (アフタヌーンコミックス)

新装版 無限の住人(1) (KCデラックス アフタヌーン)

最強伝説　黒沢　１

波よ聞いてくれ（１） (アフタヌーンコミックス)

　あーこのおっさん本当にかっこいいなーとか思いながら読んでいた．かっこいいなーとか思って(ry

SF・IT・近未来

僕だけがいない街(1)<僕だけがいない街> (角川コミックス・エース)

惑星のさみだれ （１） (ヤングキングコミックス)

レベルE 上 (ジャンプコミックスDIGITAL)

AIの遺電子　１ (少年チャンピオン・コミックス)

王様達のヴァイキング 1 (ビッグコミックス)

SFは小説，漫画どちらも好き．

そのほか

聲の形（１） (週刊少年マガジンコミックス)

幽☆遊☆白書―完全版 (1) (ジャンプ・コミックス)

ＲＡＶＥ（１） (週刊少年マガジンコミックス)

おやすみカラスまた来てね。 1 (ビッグコミックス)

　どれも面白かったです（適当）．

来年に向けて

　あいかわらず「本 おすすめ」とかで出てきた本を中心に読んでる．でも本ってデータ構造的には森になってて，一つの本を読むとそれに関連した本がたくさん出てくるので少しずつ色んな本に手を出していきたい．

　本はAmazonで中古で紙の本を買うことが多い．あとはBookoffに行って買ったりとか．逆に漫画はKindleで買ったり漫画喫茶で一気読みすることが多い．

　1年で100冊本を読む（漫画除く）目標だったんだけど，結局30冊ぐらいしか読んでない． 1~3月，10~12月はコンスタントに読めてたんだけど，4~6は院試，7~9は研究とかバイトとかで余裕が無かった．言い訳

　1年で100冊の目標は結構難しいので2017年はとりあえず60冊を目標にする． それと，本を読んだときの感想とか半年ぐらいたつと忘れるので都度ツイートしようかなと思った．

読みたい本のリスト

http://amzn.asia/7Ao7Szh

ISUCON6本戦に参加してきたよ

10月22日に行われたISUCON6本戦の参加記．

結果

惨敗

スタートラインに立って，一歩踏み出したぐらいで終わった感じ．

初期実装より低い点，というか最終的にはFailだった．

本番の流れ

じっさいどんな感じでやっていったかを書きます．時系列はわりと適当．

10:00~12:00 起動

予選と同様に1クリックでAzureにデプロイ，アプリの起動確認・・・の予定が，起動確認に2時間かかる．

レギュレーションに書いてあった，

アプリケーションは各サーバの port 443 を経由してアクセスできます。

を正しく読み取れず，http://[IP]:443でアクセスしようとする→できないを繰り返す．

他のチームがデプロイに失敗してたりしたので，再デプロイしてみたりするもできず

2時間ぐらいたって，mayokoが「https」でアクセスしたらいけることに気づく

12:00~13:00 環境の確認

自分も含めてチームメンバー全員，「docker？聞いたことはあるような...？」「react？知らない子ですね？」という状態だった．

「Docker 入門」「React とは」「React チュートリアル」

とかでググりながら何がどうなってるのかを確認する．

14:00~15:00 自分：dockerをやめる，他の二人：アプリのコードを見て明らかに悪いところの修正

というわけで実際に環境を見ていろいろ調べるも，どこに設定ファイルがあるかも分からないし，どうやってそれぞれの環境にアクセスするのかもわからずという状態．

ググってみたりwebapp/以下を見て，Dockerfileなどに書いてある処理を順に実行していったら環境が作成できそうだったので，思い切ってDockerをやめようと決断し，環境を作成し始める．

また，その間にメンバーにアプリの分析とかを頼む．

15:00~16:00 細々と修正

15:00過ぎぐらいにDockerから環境をとりだし終わりアプリの起動に成功する．

そこから自分もアプリを見て，構成とかボトルネックを調べる．

しかし，予選と違って明らかなボトルネックとなる場所がRuby側に無く途方に暮れる．

絵をリアルタイムで共有するところも，なんかアホなことやってるのは分かるんだけどそれをどう修正したらいいのか分からず，変えるとしたら全体的に変えなきゃいけない雰囲気を感じるも実装するには時間が足りなさそうと思ったり

それでもメンバーがちょこちょこ修正してくれたのをマージして少しスコア上がる．

この時間がISUCONやってるなーって感じがして，少しだけどスコアも上がって一番楽しかった．

細々としたところを修正した後で，アプリはメンバーに任せてサーバーを複数台に分散しようとする．

16:00~18:00 複数台構成にする→単機に戻す→Fail

複雑な構成にするスキルも時間も無かったので，少し考えてDB1台，Webアプリ3台，nginx1台の構成にしようと決める．

DBのリモートアクセスとかを手探りで設定したり，他のサーバーにアプリの実行環境を作成したり．

なんとか作成できたので，ベンチを回してみたところ，初期実装よりスコアが下がる．

この時点で17時ぐらい． 

時間も無く，しょうがないので単機にしようと決め，再起動しても動くようにして再起動試験を行うが，アプリが起動しない．

systemctlでの自動起動がうまくいってなかったりしたのでinit.d/以下に起動スクリプトおいて無理矢理起動するようにしたら今度は静的ファイルが無かったりしてベンチに落ちて途方に暮れる．

結局時間内に問題を解決できずFail．

反省

こんな感じで本番は終わった．もうちょい具体的に，いくつか色々考えたこととか反省点とかを箇条書き的に書いていく．

起動確認 

443=https, 冷静に考えてみたらそれはそうって感じだけど本番中はまったく気づかなかった．

懇親会のときにレギュレーションが不親切だったかも，とは言われたがWeb詳しくないとはいっても常識的に考えてそうだよなーと思ったので気づかなかった僕たちがアホだった．

最後の方になって，あと2時間あったらなーと死ぬほど思ったのでここで時間をロスしたのが非常に辛かった．

docker分離

Dockerを調べながらそのまま行くべきだったのか，分離して正解だったのかはわからないが，他にも分離しているチームはあったので悪くはなかったはず．

他のチームは，MySQLだけ取り出してたりとかしているところもあり，なるほどなーと思った．

DockerもReactも全く知らない状態で不完全とはいえアプリを取り出して動かせたところはだれかにほめてほしい

複数台構成

やろうとしてた構成は悪くなかったはず．

単機より点数出なかったのは，最適化が全然されてなかったせいで帯域とかがボトルネックになってしまったのかなーと思っている．

ここの分析をするべきだったが，それができなかったのを後悔している．

時間も経験も無いなかで一応複数台構成で不完全とはいえ動かせたところはだれかにほめてほしい

再起動

Failした直接の原因は，bundle.jsが無かったからだった．

Dockerからアプリを分離した時点で一回再起動してちゃんと動くか確認するべきだった．

役割分担

チームのスキル的に，自分がアプリを見つつインフラもやり，二人にはアプリの修正をお願いして，やってもらったのを確認しながらマージしていくって感じだった．

このスタイルで予選はなんとかなったが，本戦はそれじゃどうにもならなかった．

自分が諸々修正している間にアプリを見てもらったけど，結果的に他の二人に（たぶん）暇をさせてしまっていた．*1

せめて誰かDocker, Reactのどっちか使ったことあればなーとか，せっかく3人チームだったのにうまく動くことができずもったいなかったなーとか色々後悔はあるが，経験，実力的に今回の問題だとこうなるのは必然だったかなーとも思う．

その他諸々 

・ローカルの開発環境を作らず，本番をそのままいじっていた

・過去問をもっとやっておくべきだった

・もっとwebapp以下のコードをじっくり考察するべきだった 

・チーム練習ちゃんとやっておくべきだったなー

・発想自体はあってるんだけど実装に結びつかないみたいなのが多々あった

まとめ

というわけで，今回のISUCON6本戦は非常に悔しい結果に終わりました．

それでも，初参加で予選を突破し，本戦に参加できて，普段なかなかいじれないような構成のアプリをいじれて，非常に勉強になったし楽しかった．

来年も，もしあればぜひまた参加して賞金をもらいたいです．*2

謝辞

最後になりますが，ISUCON運営企業，スタッフのみなさん，お疲れ様でした＆ありがとうございました．とても楽しいイベントでした．

それと，急な誘いと無茶ぶりにもかかわらず一緒に参加してくれたmayokoとoshiumiにもめっちゃ感謝です．ありがとうございました．

*1:お絵かきアプリだったので，リンゴとかみかんとか書いてた

*2:oshiumiが就職してしまうので新しくチームメンバー探さなきゃ・・・？