AHC065参加記

はじめに

AtCoder Heuristic Contest 065 に参加し、304位(perf 1471)でした。

今回は初めて本格的にAIを使ってコーディングするスタイルでやったので、そのあたりも含めて参加記を書きたいと思います。

問題


  • 縦20x横20のグリッドに番号のついた箱が敷き詰められている
  • グリッドにベルトコンベアを設置して番号順に箱を搬出する（搬出口はグリッドの上部中央のマス）
  • ベルトコンベアの条件
    • サイクル状でなくてはならない
    • ただし2マスのみからなるベルトコンベアは許容（実質的に隣あう箱をスワップすることになる）
    • 同じマスに置けるベルトコンベアのレールは2つまで
    • 異なるベルトコンベアを同時に動かすことはできない
  • なるべく少ないターン数（ベルトコンベアを一マスだけ進めるのを1ターンと数える）ですべての箱を搬出せよ

解法

縦2x横Nの横長ベルトコンベアと、縦Nx横2の縦長ベルトコンベアを敷き詰め、次の箱を搬出するまでを1遷移としたビームサーチを行いました。

ベルトコンベア

縦2x横Nの横長ベルトコンベアと、縦Nx横2の縦長ベルトコンベアを敷き詰めることでどの位置にある箱であっても上下左右自由に動かすことができるようになります。

これにより次の箱を搬出口まで最短距離で運ぶことができるようになります。

ビームサーチ

次の箱を搬出口まで最短距離で運ぶにしても複数のルートがあるため、ビームサーチで探索してよいルートを選ぶようにしました。

次の箱を搬出するまでを1遷移としています。ルートの選び方は全パターンを試すことはできないため、方向転換を2回まで（例：左右に動いてから上に曲がり、再度左右に曲がるなど）とするルートに絞りました。

評価関数はターン数 + 1～8個先の箱と搬出口までの距離としています。

正確にいうと、T(i) : 箱0～箱iを搬出するまでにかかった通算ターン数、D(i) : 箱iと搬出口のマンハッタン距離とした場合、評価関数 E(i) は

E(i) = T(i) + Σ (D(i+j) / j)  [j = 1〜8]

としています。

意味合い的にはこの後近々搬出することになる箱が搬出口に近いほうがうれしいのでそれを考慮しています。jの数が大きくなると減衰するのは、実際にその箱が次の搬出対象になるまでに位置が変わってしまっている可能性が高くなるのを考慮しているためです。

このほか番号が隣り合う箱同士の距離なども少し検討しましたが、大きな効果が出なかったので採用はしませんでした。

反省点

1個ずつ搬出するやり方にとらわれ過ぎた感じはします。感想戦を眺めた感じだと、まとめて一気に搬出できるような方法が強かったようですので、そこにあまり思い至らなかったのは少し頭が固かったかなというのが反省点です。

連続する箱同士を近づけてまとめて運び出せないかというのは少しだけ頭をよぎったのですが、評価関数で箱同士の距離を考慮する程度しか具体案が思い浮かばず、試した結果もいまいちだったので、そこで案自体をボツにしてしまいました。

ビームサーチで遷移の選択肢が限られていたことと、盤面の重複除去が考えられていなかったことで、導入してもあまり効果出せなかったのかなという気がしています。

あとビームサーチでもまだ伸ばす余地がありそうなので、そのあたりも力不足を感じました。

AIの使い方について

今回はコーディングにAIを活用しました。使ったのはGemini (高速モード)です。無料で使える範囲です。また、ブラウザのチャット欄を使っています。

基本的には方針は自分で考え、その方針でAIにコードを書いてもらうという使い方をしました。

開始～30分

最初は横長(高さ2x幅N)、縦長(高さNx幅2)のベルトコンベアをそれぞれ敷き詰めて、一つずつ上→左右で順番に箱を出すシンプルな方針とし、それを実現するコードを書いてもらう

～1時間30分

最初のコードをベースに経路を複数通り試すビームサーチに変更したコードを書いてもらう

～3時間

ビームの幅・深さを調整したり、評価関数を改善したり。一部コードは書いてもらいましたが、コードは壁打ちした結果を参考にして自分で修正するのがメイン。

～4時間(コンテスト終了)

KotlinのコードをC++に変換してもらう。その結果を使ってビームの幅・深さを調整。
これで順位が50位くらい浮上した気がするので思った以上に効果がありました。

途中、動かないコードやWAになるようなコードを書くこともありましたが、その場合は実際の出力結果を渡したり、以下のような感じでビジュアライザの結果でおかしいところを教えると比較的スムーズにデバッグできた感じでした。

感想

結果自体はいまひとつでしたが、今回一番の課題だったAIを使いながらのコーディング自体は結構スムーズに進められましたし、ビームサーチのアプローチ自体はそれなりに上手く進められたと思います。自分が課題と思っていた点に対して取り組めたということで、いい経験が得られたという点は満足です。ビームサーチの評価関数を工夫して結果が少しずつよくなるというのは、ヒューリスティックではオーソドックスなことだと思いますが、自分ではあまり経験してこなかったので、その点も満足です。

ここまで読んでくださりありがとうございました。

このブログの人気の投稿

AHC063参加記

イメージ
はじめに AtCoder Heuristic Contest 063 に参加しました。 その参加記です。 問題 問題はこちらです。 https://atcoder.jp/contests/ahc063/tasks/ahc063_a 自分なりにかいつまんで言うと 正方形状のグリッド上を蛇が移動できます。蛇の体自体もグリッドの連結した数マスを占めます。 グリッドのマス目には色のついた餌が散らばっています。 蛇が餌を食べると蛇のしっぽが長くなり、長くなった部分は食べた餌の色になります。 グリッド内の餌をすべて食べたときに蛇の色が指定通りになっている、つまり正しい順番で決められた色の餌をできるだけ少ないターン数で食べていくのが目標です。 ただし、胴体と頭が重なると胴体を噛みちぎります。噛みちぎられたしっぽ側はその位置で再び餌となってグリッド上に配置されます。 つまり、順番通りに餌を食べられなかった場合は、噛みちぎることで途中からやり直しすることができます。 解法 ルールベースに一部ビームサーチを採用しました。 正しい餌を食べるルートをビームサーチで一気に決定し、正しい餌が見つからない状況や間違った餌を食べてしまっている状況はルールベースで打開。 具体的には、完成するまで以下1～3のいずれかの行動をとります。数字が小さいほうが優先です。これを完了するまで（もしくはターン数や制限時間に達するまで）繰り返します。 1. 間違った餌を食べてしまっている場合 頭から間違った餌までのどこかの胴体を噛みちぎって分離し、その後正しい位置まで胴体を復元。 胴体を噛みちぎるための経路をBFSで求めています。ただし最短経路だけにすると手詰まりになりやすいため噛みちぎることが可能な行き先マスをすべて求めてその中からランダムに決定するようにしています。 2. 正しい餌が見つかる場合 途中で違う餌を食べることなく、かつ胴体を噛みちぎることなく正しい餌を取ることができる場合、次の餌までの移動を1遷移としたビームサーチを行い、最も多くの餌を取り続けられるルートを採用。餌の数が同じルートが複数ある場合はターン数が少ないものを採用としました。 次の餌までの移動を1遷移とした理由は、自分がビームサーチをほぼ初採用という状況だったのでビームサーチで解くところを単純化したかったためです。例えば1ターン1遷移などとし...
続きを読む

AHC066参加記

イメージ
 はじめに AtCoder Heuristic Contest 066 に参加し、438位(perf 1447)でした。 結果は微妙ですが、少し特徴のある解法を試したので、その辺りの説明を中心に参加記を残したいと思います。 問題 https://atcoder.jp/contests/ahc066/tasks/ahc066_a グリッドに番号のついたボールとかごが散らばっている ロボットを操作してボールを同じ番号のかごに入れる ロボットは最大1個のボールを運ぶことができる ロボットの基本動作は'F'(直進)、'R'(右回転)、'L'(左回転)、'S'(今いる位置に置いてあるボールと持っているボールを交換) 上記基本動作のほか、ロボットにはマクロ機能がある 'M': マクロ記録開始/終了。開始～終了までに実行した操作列がマクロに記録される。 'P': 記録したマクロを実行する マクロは1つしか登録できない。新しいマクロの記録終了まで古いマクロが有効。 なるべく少ない操作列ですべてのボールをかごに入れる ただしTターン以内に収めること。'P'でマクロを再生した場合、そのマクロの長さ分だけターン数を消費することに注意 解法 マクロを固定してボールの処理順を焼きなましました。マクロは3～8回連続で直進するものを用意してその中で一番結果が良かったものを採用しました。 この解法にプラスして一気にまとめて処理できそうなボールはグループ化して回転ベルトコンベアマクロを作って一気に処理しました。 ボールの処理順 まず最初に使うマクロを決めたとき(例えば3回連続直進)に開始点および各ボール/かご同士の移動にかかる操作数をBFSで求めました。遷移は'F'(直進)、'R'(右回転)、'L'(左回転)、'P'(マクロ使用)です。今回は向きを変えるのにも1手必要になるため、向きも考慮した頂点倍化BFSを使っています。 これを使って操作列が少なくなるようなボールの処理順を焼きなましで求めました。 ただし次に述べる回転ベルトコンベアマクロで処理するボール群は除いています。 回転ベルトコンベアマクロ 例えば4つのボールがあった...
続きを読む

AHC064参加記

はじめに AtCoder Heuristic Contest 064 に参加し、440位(perf 1298)でした。 成績は芳しくないですが、参加記を残そうと思います。 問題 https://atcoder.jp/contests/ahc064/tasks/ahc064_a ルールベースで車両を1台ずつ順番に揃えていく方法を採用しました。 指定された線路に車両を指定された順番に少ないターン数で並べていくのが目的。 線路には最終的に列車がならぶ出発線のほか、バッファ的な意味合いの待機線がある 車両は全部で100台、出発線・待機線はそれぞれ10列。 列車は出発線ー待機線間を移動可能（出発線同士、待機線同士の直接移動は不可） 1ターンに車両が衝突しない限り（＝移動線が交錯しない限り）同時に複数の移動が可能 解法 ルールベースで車両を1台ずつ順番に揃えていく方法を採用しました。 ターゲットとする車両（以下、対象車両）を以下の3ステップで目的の場所へ運びます。  1. 対象車両を待機線の先頭へ移動 対象車両が出発線、待機線のどちらにいるかで分岐します。 出発線にいる場合：その列の末尾から対象車両までを待機線へ移動。 待機線にいる場合：対象車両より前にある車両を、目的以外の出発線へ一時退避   2. 目的地の整理  目的の出発線にある邪魔な車両を、対象車両がいる待機線とは別の待機線へ移動。  3. 目的地への移動 対象車両を待機線から目的の出発線へ移動。  出発線・待機線間の移動は、物理的な距離が近くなるものを優先して選択しました 。 処理順は「IDの下1桁（＝格納先の列番号）」が小さい順とし、同グループ内はランダムに決定。制限時間いっぱい試行してベストなスコアを採用しました。 最後に、全手順を見直して独立して行える（＝移動線が交錯しない）操作を1ターンに集約する後処理を行っています。  反省点 車両をひとつずつ処理することに縛られてしまった この手順に縛られている限り、一つの車両を正しい位置に移動させ終わるまで、ほかの車両のことを考慮することが全くできません。 この手順の制約が大きすぎて改善する余地がほとんどありませんでした。 車両の処理順を一部ランダム化して山登り（あるいは多点スタート）のような形を試しま...
続きを読む