utsubo’s blog

競技プログラミングとか.

ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて,そういえば組んだことがないなぁと思い立ち.

目的

パズドラのパズルにおいて,コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する.
今回は,ダメージ等については考慮しません.

方針

ビームサーチを使います.”ビームサーチ”で検索すれば良い記事が沢山出てくると思うので,詳細は割愛.

ビームサーチは下のをそのまま実装しました.

状態は,{”パズルの盤面の状態”,”今動かしている部分の座標”,”何手動かしたか”}とし,パズルを1手動かした状態を遷移状態としています(上下左右で4つの状態に遷移).
コンボ数をそのまま状態の評価値として扱います.

初期状態は,パズルをスライドさせるスタートの位置を変えたもの,計30個に設定.
また,ビーム幅は40000,最大ターンは12として実行します.

ZobristHashで盤面のハッシュ値を生成し,同じ盤面を2回探索しないようにしています(出来てるかは謎).


deleteしてないからヤバそうなC++コード
https://ideone.com/MbxQOR

まとめ

サクサクっと作った割には5,6コンボ出るので,凄いと思いました.
適当に作ったので(言い訳),全てにおいて杜撰なコードになっています.

記事の書き始めた時はもっとしっかり書こうと思っていたんだけど,途中で面倒くさくなってしまった.

グラフ理論系の好きな問題 5選

最近何もする気が起きないので,今までに見た数少ない問題の中で好きだった問題を紹介します(脚注にネタバレ).

1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes

*1が好きなので好きです.
https://community.topcoder.com/stat?c=problem_statement&pm=13523
TopCoder SRM 642 Div2 Hard TallShoes - kmjp's blog

2. Indeedなう A日程 D: Longest Path

全然わからなかったけど,解説を読んで実装するのが楽しかった.
D: Longest Path - Indeedなう(オープンコンテスト) | AtCoder
Indeedなう A日程 解説

4. CODE FESTIVAL 2015 決勝 I: 風船ツリー

これも実装が楽しい問題でした.
I: 風船ツリー - CODE FESTIVAL 2015 決勝(オープンコンテスト) | AtCoder
CODE FESTIVAL 2015 解説 - SSSSLIDE

まとめ

グラフ理論系の問題は実装が楽しいものが多くて好きです.
なんか最近の問題が多くて申し訳ない感じになりました.
手を付けてない組み合わせ系の問題に取り組みたい.






以下,問題の解法ネタバレ.

*1:二分探索

*2:最短経路問題

*3:フロー

2015年振り返り

こんな目標を立てていたらしい.
2015年の目標 - utsubo’s diary

競技プログラミング

レート等

  • SRM (903 -> 1165)
  • Marathon Match (? -> 864)
  • CodeForces (1440 -> 1702)
  • CODE FESTIVAL (138位 -> 91位)
  • CODE RUNNER (65位 -> 46位)

目標

  • SRM Div1 入り ✕(まだだめそう)
  • オンサイト ◯(CodeFes出れて良かった)
  • 蟻本読了 ✕(目標自体を忘れてた)
  • CF出る △(5回しか出てない)

若干成長できたのかなぁ.正直,誤差の範囲だと思ってます.
達成率は40%ぐらい.

英語

目標

  • 洋書読む ✕(目標自体を忘れてた)
  • 洋楽聞く △(聞き流しは多少)

洋楽は前よりかは聞いたから,達成率は20%ぐらい.

その他

目標

  • 何かしらで2つ以上作る ◯(まだまだな部分もあるけど)
  • ラブライブの声優に1人以上会う ✕(こんなのも立てていた)
  • 大学の特待生制度で15万貰う △(だめです)

まずまず.

雑記
  • 某社ツアーが最高でした.ほんと感謝.
  • そろそろ分野絞ってやらないといけないと強く感じます.
  • 各方面に迷惑をかけまくった一年だった.

今年も大変お世話になりました.2016年目標に続きます.

ACするとLEDがピカピカ

作ったもの

AtCoderのコンテストでACするとLEDが点滅する奴を作ってみました.こんなの↓

構成

Pythonで提出状況を取ってきてパース,正誤をシリアル通信でArduinoに送っています.
ArduinoではACであれば点滅,それ以外であったら点灯するようにしました.(他の色があれば,色を状態によって変えたかったのですが,手持ちになかったので...)
f:id:utsubo_21:20151225223411p:plain

pythonはシリアル通信にpyserialとhtmlパーサーにbeautifulsoupを使用.
beautifulsoupがよく分かってないので適当.
procon_led.py · GitHub

Arduinoは基本的なコマンドのみ.
serial_test · GitHub

まとめ

PythonArduino便利!

CODE RUNNER 予選B

予選B問題

問題はこんな感じでした.

魔法の力を、ためて戦え!「Charge And Hit」
「Charge And Hit」は3人1部屋でゲームを行います。ユーザーは入室/攻撃APIをリクエストするとシステムにより各部屋に割り振られます。部屋には10匹の敵が並んでいて、ユーザーは任意のタイミングで一番前の敵を魔法で攻撃します。攻撃によって敵に与えるダメージは「魔法をためた時間」に応じて高くなります。ただし敵の体力を超えるダメージは切り捨てられて体力と等しい値になります。部屋内で与えたダメージの合計値が大きい順に室内順位がつけられ、その室内順位に応じてスコアを得ます。ユーザーは他のユーザーより多くのダメージを与えて、スコアを多く得ることを目指します。

序盤

最初はとりあえず,3秒に1回殴るプログラムを書いて動かしながら方針を考えてました.これだけでも,最序盤は2位ぐらいまでいっててビビる.

メンテナンス前(開始1時間ぐらいでメンテナンスがあった)

Info APIからjsonを貰ってくるのに悪戦苦闘してたら時間が結構経ってしまった.
敵を倒せるなら殴るに変えてたら,一気に50位ぐらいまで落ちた.HPが高い敵を狙う人のカモになっていると気づく.

メンテナンス後

以下が最終的な方針.

1. 残りの敵の中でHPが上位30%の敵をリストに入れる
2. リスト内の敵が全て倒されていたら,上と同様にリストを更新

リスト内の敵が目の前に来た時
3.1. パワーがHPの7割を超えていたら殴る.
3.2. friendsの最大パワーが敵のHPの7割を超えていて,自分のパワーが3e7より大きければ殴る.
1~3をInfoを0.2秒ごとに貰ってきて繰返していた.

書いたコード: qb2015.py · GitHub

結果

10位 (∩´∀`)∩ワーイ
Ranking: http://graph.coderunner.jp/max.html

初めて良い感じの順位を取れてめっちゃ嬉しい.
本戦もこの調子でいけると良いんだけどなぁ...

反省

1位の方が言っていた「必ずルーム1位なら倒す」を思い付いていれば,もう少し伸びそうだった.
「後ろに並んでるHPが高い敵を狙って目の前の敵を誰も殴らない現象」が頻発する前に上位に抜け出せたのが大きかった.

IntelliJ IDEAからSceneBuilderが開かない(Mac)

少し困ったので調べると
java - How to use the SceneBuilder with IntelliJ on Mac - Stack Overflow

IntelliJ IDEAでパスを設定
Preference -> Language & Frameworks -> JavaFX -> /Application/SceneBuilder.app

Finderから
Applications -> SceneBuilderを右クリック -> パッケージの内容を表示 --> Contents -> MacOS -> ファイル名を "SceneBuilder" から "scenebuilder-launcher.sh" に変更.

とりあえず起動した.