1日9時間寝たい

本当は10時間寝たいです

テトリスのAIを作った

パソコンを使ったのでたぶんAIです。

youtu.be

github.com

AI

ver.1 ランダム

ピースをランダムに回転させてランダムな位置に落とします。すぐにゲームオーバーになります。

ver.2 評価関数

各ターンでピースの回転・落とす位置を全部試して一番よさげな手を選びます。

よさを決める要素はたとえば次のようなものが挙げられます:

  • このターンで消した段の数
  • いまの盤面で積み上がっているブロックの最大の高さ

これらに適当に係数をかけたものを評価関数として手のよさを評価します。

有効な手すべてについて評価して、一番良い手を選びます。

ver.3 GA

評価関数の各変数にかかる係数を少しずつ変えながら強いAIを探すのは精神に悪いです。

そこで次のようにします。

  1. 評価関数の係数が異なる個体 (AI) を複数用意する
  2. それらにゲームをプレイさせてみてスコアの高かった個体の一部を エリート とする
  3. エリート から1つ、全体から1つ個体をえらんでそれらから新しい個体をつくる
    • たとえば係数が1種類だとして、係数$a$を持つ個体と係数$b (>a)$を持つ個体から新しい個体をつくるときその係数は$[a, b]$からランダムに選ぶようにします
  4. 一定数新しい個体ができたら古い個体たちは消して2に戻って繰り返す
  5. 適当な回数繰り返したら終わる

このような方法はGA (Genetic Algorithm) と呼ばれています。

思い出

もっと強いのを作りたかった。

GA...のつもりだけど、第5世代くらいで収束してしまっているのでダメです。

カーソル行の直前・直後に空行を挿入する micro の plugin を作った

micro editor で Insert Line Above/Below するプラグインを作りました。

VSCodeCtrl+Enter とか Ctrl+Shift+Enter とかに割り当てられている *1 あれです。

レポジトリ

github.com

Demo

コード

実装のメイン部分は10行くらいなので、プラグインというには大げさでせいぜいマクロといったところでしょう。

function insertLineBelow()
  local v = CurView()
  v:EndOfLine(false)
  v:InsertNewline(false)
end

function insertLineAbove()
  local v = CurView()
  v.Cursor:Up()
  insertLineBelow()
end

インストール

1 . ~/.config/micro/settings.jsonpluginchannels の部分を次のように書き換えます。

{
  "pluginchannels": [
    "https://raw.githubusercontent.com/micro-editor/plugin-channel/master/channel.json",
    "https://raw.githubusercontent.com/ia7ck/insertline/master/channel.json"
  ]
}

2 . micro の コマンドモードで plugin install insertline を入力してEnterを押します。

使い方

コマンドモードで insertlinebelow と打つと、カーソル行の下に空行が、 insertlineabove と打つと、カーソル行の上に空行が挿入されます。

キーボードショートカット

デフォルトでは Alt+Enterinsertlinebelow に割り当てています。

insertlineabove には何も割り当てていません *2

この設定は ~/.config/micro/keybindings.json を編集することで変更できます *3




メモ

マクロじゃダメなの?

Ctrl+U でマクロの登録、Ctrl+J でマクロの実行ができます *4 が複数登録ができません。

プラグインの開発

ここ を見ると、~/.config/micro/init.lua にコードを書けばプラグインが作れることが分かります。micro 本体が提供している関数や変数は ここ で確認できます。

たとえば、CurView() は Go のコード内で定義されている View 構造体のポインタを返します。EndOfLine*View 型の変数をレシーバにとってカーソルを行の末尾に移動させる関数です。InsertNewline も同様にして、現在のカーソル位置で改行する関数です。こういうのはIDEを使って複数ファイルを横断検索して、気になる関数とかがあれば定義元にジャンプする機能を使うといいです(と最近気づきました)。

Go だと *View 型の変数 v に対して EndOfLine を実行するにはドット . を使って v.EndOfLine() としますが、lua でそれに対応する記法は v:EndOfLine() です。意図せず再帰的に関数が呼ばれるのを防ぐためには引数に false を指定しておくといいみたいです *5

プラグインの公開

channel.jsonrepo.json を用意することで、micro のコマンドモードから plugin install でインストールできるようになります *6 。ただし、上で示したように ~/.config/micro/settings.json をあらかじめ編集しておく必要があります *7

ABC108/ARC102 D All Your Paths are Different Lengths

ABC108/ARC102 D

f:id:poyopoyoyon:20180904160234g:plain

公式解説の英語版の方法

$L=L'$のグラフから$L=L'+1, 2L'$のグラフを作るには

  • $L=L'+1$

    先頭から末尾の頂点へ長さ$L'$の辺を引く

  • $L=2L'$

    すでに引いてある辺の長さを全て2倍にして、末尾の頂点から新しい頂点へ長さ$0$と長さ$1$の辺を引く