テトリスのAIを作った
パソコンを使ったのでたぶんAIです。
AI
ver.1 ランダム
ピースをランダムに回転させてランダムな位置に落とします。すぐにゲームオーバーになります。
ver.2 評価関数
各ターンでピースの回転・落とす位置を全部試して一番よさげな手を選びます。
よさを決める要素はたとえば次のようなものが挙げられます:
- このターンで消した段の数
- いまの盤面で積み上がっているブロックの最大の高さ
これらに適当に係数をかけたものを評価関数として手のよさを評価します。
有効な手すべてについて評価して、一番良い手を選びます。
ver.3 GA
評価関数の各変数にかかる係数を少しずつ変えながら強いAIを探すのは精神に悪いです。
そこで次のようにします。
- 評価関数の係数が異なる個体 (AI) を複数用意する
- それらにゲームをプレイさせてみてスコアの高かった個体の一部を エリート とする
- エリート から1つ、全体から1つ個体をえらんでそれらから新しい個体をつくる
- たとえば係数が1種類だとして、係数$a$を持つ個体と係数$b (>a)$を持つ個体から新しい個体をつくるときその係数は$[a, b]$からランダムに選ぶようにします
- 一定数新しい個体ができたら古い個体たちは消して2に戻って繰り返す
- 適当な回数繰り返したら終わる
このような方法はGA (Genetic Algorithm) と呼ばれています。
思い出
もっと強いのを作りたかった。
GA...のつもりだけど、第5世代くらいで収束してしまっているのでダメです。
カーソル行の直前・直後に空行を挿入する micro の plugin を作った
micro editor で Insert Line Above/Below するプラグインを作りました。
VSCode で Ctrl+Enter
とか Ctrl+Shift+Enter
とかに割り当てられている *1 あれです。
レポジトリ
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.json
の pluginchannels
の部分を次のように書き換えます。
{ "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+Enter
を insertlinebelow
に割り当てています。
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.json
と repo.json
を用意することで、micro のコマンドモードから plugin install
でインストールできるようになります *6 。ただし、上で示したように ~/.config/micro/settings.json
をあらかじめ編集しておく必要があります *7 。
*1:https://code.visualstudio.com/docs/getstarted/keybindings#_basic-editing
*2:なにか良いのがあったら教えてください
*3:https://github.com/ia7ck/insertline/blob/master/help/insertline.md#key-bindings
*4:https://github.com/zyedidia/micro/blob/master/runtime/help/keybindings.md#default-keybinding-configuration
*5:https://github.com/zyedidia/micro/blame/master/runtime/help/plugins.md#L171
*6:https://github.com/zyedidia/micro/blob/master/runtime/help/plugins.md#plugin-manager
*7:https://qiita.com/10sr/items/0ed6f3dc4a01159115fc#channel
ABC108/ARC102 D All Your Paths are Different Lengths
公式解説の英語版の方法
$L=L'$のグラフから$L=L'+1, 2L'$のグラフを作るには
$L=L'+1$
先頭から末尾の頂点へ長さ$L'$の辺を引く
$L=2L'$
すでに引いてある辺の長さを全て2倍にして、末尾の頂点から新しい頂点へ長さ$0$と長さ$1$の辺を引く