https://smooth-pudding.hatenablog.com/entry/2025/05/04/102642

こんにちは。
今回は Water Sort Puzzle のソルバを作っていきます。最近はAIを使った開発ツールの発展がすさまじく、私も勉強しながら使い始めているところです。そこで、今回のソルバづくりでは Cursor の機能をどんどん使ってコードを書いていこうと思います。

前回:
smooth-pudding.hatenablog.com

Water Sort Puzzle ってどんなゲーム？

どんなゲームか言葉で説明するよりも、プレイ画面を見たほうが早いでしょう。YouTube で「Water Sort Puzzle」と検索すると、多数のプレイ動画がヒットします。例えば↓
www.youtube.com

開発の方針

大まかに、以下のように動くプログラムを作ろうと思います。

色水のパターンを入力する
深さ優先探索で解法を探す
答えの経路を出力する

深さ優先探索は非常によく知られたアルゴリズムなので、この実装はAIの得意分野です。ただし、「Water Sort Puzzle への適用」部分は怪しいので、適切に抽象クラスを挟んで実装を分離するようにします。具体的には

State クラス: グラフのノードに対応する部分
Action クラス: グラフのエッジに対応する部分

というふうに準備することにします。

上記のクラスが準備できたら、AI の能力を発揮してもらって、深さ優先探索を実装してもらいます。また、合わせてこのアルゴリズムのテストプログラムも生成してもらいます。

次に State クラスと Action クラスを Water Sort Puzzle 用に実装してもらいます。Water Sort Puzzle はオセロなどゲームと比べると有名ではないので、AI がちゃんとルールを把握しているかは怪しいので、

AI と対話しながらルールを確認・明文化する
そのルールに基づいて実装を与えてもらう

という2ステップにすることにします。

最後に、色水のパターン入力と答えの出力を行うサンプルプログラムを生成してもらいます。ここまで実装が終わっていればおそらくササッと実装してくれることでしょう。

下準備

Python の開発環境と Cursor は事前に準備しておきます。また適当な作業フォルダを作成し、直下に main.py を追加しておきます。中身は以下のようにします。

def main():
    pass


if __name__ == "__main__":
    main()

今後このプログラムを実行することにします。

ライブラリのファイルを入れるためのフォルダ wsp_lib を作成し、その中に空の __init__.py を作成しておきます。
また Cursor で生成するときのルールを定める .cursorrules というファイルをプロジェクトルートに配置します。中には以下のように書いておきます。

Generate all codes according to the PEP8 standard.
Use Japanese in comments.

これは必須ではありませんが、git 環境を整えておくことをおすすめします。AI はあらぬ方向に編集してしまうことがしばしばあり、手戻りが必要になる場面が多いです。もちろん数手戻す機能はあるものの、試行錯誤した上で「やっぱやーめた！」となる場面ではやはり git の機能が便利です。以下のコマンドをプロジェクトルートで実行し、 git 環境を作成しておきます。

git init .

今後特に明記しませんが、適宜 git commit して途中の状態を保存します。

抽象クラスの準備

Agent を開き (ctrl+I で開きます)、以下のように命令します。

深さ優先探索を用いてゲームの探索を行おうと思っています。深さ優先探索の対象となるグラフの要素を抽象化したクラスとして、ノードに対応する State クラスと、エッジに対応する Action クラスを作成してください。実装したものは wsp_lib/graph_base.py に保存してください。

手元で実行したところ、以下の3つが生成されました。

State クラス
Action クラス
DFSSearcher クラス

命令では「抽象クラスを実装して」としたのですが、合わせて深さ優先探索のメソッドも実装しちゃったみたいです。やや命令通りにならないあたりがAIらしいですね。

Chat を開いて (ctrl+L で開きます）、graph_base.py を要約させたところ以下のようになりました。

実装を確認し、少し気に入らない部分があったので、追加で命令します。具体的には、生成されたコードでは Action のメソッドとして is_valid (引数で与えられた State に対して、その Action が有効であるかを判定するメソッド) が準備されていたのですが、ゲームのルールに基づく内容は State 側にまとめておきたいので、移動させるよう命令してみます。また、Action を State に適用させる命令も State と Action で二重に準備されていたので、State 側の方だけ残すように命令してみます。

ファイル全体を選択し、ctrl+K を押して命令の窓を出します。ここに命令を書きます。

実行すると、無事命令通りの結果が得られました。

深さ優先探索のロジックを実装する

本当はこのステップで実装しようと思っていたのですが、前のステップで勢い余って生成されたので、ファイルを分ける処理だけを行うことにします。

graph_base.py を開いた状態で、Agent に以下のように命令します。

深さ優先探索を行うクラスを別のファイルに移動して。ファイルは新たに wsp_lib/dfs.py を作成して。

この処理は手動でやろうとすると意外と大変です。具体的にはだいたい以下のステップになるでしょう。

wsp_lib/dfs.py を作成する
当該クラスを wsp_lib/dfs.py に移動する
必要なクラスを import する

AIはある程度賢いので、これぐらいであれば自分で考えて処理してくれます。

さて、実装内容を確認して、概ね問題なさそうなことが確認できたので、テストプログラムを作成してもらいます。dfs.py を開いた状態で以下のように命令します。

DFSSearcher の search および get_solution の単体テストを作成して。作成にあたっては unittest を用いること。

命令の結果、以下を実行してくれました。

プロジェクトルートに test というディレクトリを作成
その下に test_dfs.py を作成
State のモック MockState と Action のモック MockState を実装した上で、DFSSearcher のテストを作成
作成したテストが問題なく通過することを確認 (通過しなければ問題を修正)

生成のコード量が多くなると、コードの質が落ちがちになります。今回も、いくつか修正してほしいポイントが見つかりました。ただ、問題点をひとつひとつ拾って命令すると結構手間がかかります。そこで、AI自身にレビューさせてみます。

test_dfs.py で Agent を開いて、以下のように命令します。

test_dfs.py の実装を確認し、問題点があればいくつか箇条書きで挙げてください。それぞれの問題点には通し番号を振ってください。

すると、問題点が10個列挙されました。これらを確認し、重大度と変更容易性を鑑みて、修正を依頼します。例えばこんな感じです。

1. の内容を修正して。修正後はテストが問題なく実行できるかを確認すること。

それでも満足できない場合は、いよいよ自分で命令します。

上記のポイントは、修正箇所の範囲を絞ることです。修正箇所が多いと、その分修正に必要な確認量が多くなり、しんどくなります。自分で確認できるくらいの小さな変更に分けるとよいでしょう。

Water Sort Puzzle のルールを確認する

Water Sort Puzzle はオセロなどと比べて超有名とまではいかないので、いきなり AI に実装を任せるのではなく、一旦自然言語でルールをまとめることにします。

まず Agent を開いて、以下の内容を命令してみます。

Water Sort Puzzle という有名なパズルゲームがあります。多数の試験管があり、色のついた水を仕分けることを目的とするゲームです。このゲームはスマートフォンのゲームとして多数開発されています。
この Water Sort Puzzle のルールについてわかりやすくまとめた文書を作成してください。形式はマークダウンとし、wsp_rules.md として保存してください。

生成された内容を読み、認識のズレがないか確認します。ラッキーなことに、ほぼほぼ問題ないルールが生成されました。もし修正が必要であれば、手で修正するか、AIに依頼します。

Water Sort Puzzle のルールに基づいた State と Action を実装する

先程作成した wsp_rules.md を開いた状態で、改めて Agent を開きます。+ボタンから wsp_lib/graph_base.py への参照を追加した上で、以下のように命令します。

wsp_rules.md に基づいて、Water Sort Puzzle に特化した State と Agent それぞれの具象クラスを実装してください。実装したものは wsp_lib/wsp_graph.py に保存してください。

しっかりと生成してくれました。先程と同様、気になる点は追加で命令して修正してもらいます。

こちらもテストプログラムを作成してもらいましょう。ルールの md ファイルと wsp_graph.py を参照した上で、以下のように命令します。

wsp_graph.py の WSPAction および WSPState のテストを作成して。

既に作成済みのテストと同じ形式で、問題なくテストが生成されました。

main 関数を実装する

以上でパーツはそろったので、main を実装してもらいましょう。Agent を開き、main.py と wsp_graph.py と dfs.py を参照した状態で以下を命令します。

main() 関数以下に、以下の処理をする実装を与えてください。
1. 初期状態を与える
2. 深さ優先探索を行う
3. 探索結果を標準出力する

これで完成です！

以下は実行例です。

【初期状態】
チューブ0: [赤,赤,緑,黄]
チューブ1: [黄,緑,黄,緑]
チューブ2: [赤,赤,黄,緑]
チューブ3: [空]
チューブ4: [空]

【解決策が見つかりました！ステップ数: 11】
開始状態:
チューブ0: [赤,赤,緑,黄]
チューブ1: [黄,緑,黄,緑]
チューブ2: [赤,赤,黄,緑]
チューブ3: [空]
チューブ4: [空]

ステップ 1:
アクション: チューブ0からチューブ3へ水を移動
チューブ0: [赤,赤,緑]
チューブ1: [黄,緑,黄,緑]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄]
チューブ4: [空]

ステップ 2:
アクション: チューブ0からチューブ4へ水を移動
チューブ0: [赤,赤]
チューブ1: [黄,緑,黄,緑]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄]
チューブ4: [緑]

ステップ 3:
アクション: チューブ1からチューブ4へ水を移動
チューブ0: [赤,赤]
チューブ1: [黄,緑,黄]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄]
チューブ4: [緑,緑]

ステップ 4:
アクション: チューブ1からチューブ3へ水を移動
チューブ0: [赤,赤]
チューブ1: [黄,緑]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄,黄]
チューブ4: [緑,緑]

ステップ 5:
アクション: チューブ1からチューブ4へ水を移動
チューブ0: [赤,赤]
チューブ1: [黄]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄,黄]
チューブ4: [緑,緑,緑]

ステップ 6:
アクション: チューブ1からチューブ3へ水を移動
チューブ0: [赤,赤]
チューブ1: [空]
チューブ2: [赤,赤,黄,緑]
チューブ3: [黄,黄,黄]
チューブ4: [緑,緑,緑]

ステップ 7:
アクション: チューブ2からチューブ1へ水を移動
チューブ0: [赤,赤]
チューブ1: [緑]
チューブ2: [赤,赤,黄]
チューブ3: [黄,黄,黄]
チューブ4: [緑,緑,緑]

ステップ 8:
アクション: チューブ1からチューブ4へ水を移動
チューブ0: [赤,赤]
チューブ1: [空]
チューブ2: [赤,赤,黄]
チューブ3: [黄,黄,黄]
チューブ4: [緑,緑,緑,緑]

ステップ 9:
アクション: チューブ2からチューブ1へ水を移動
チューブ0: [赤,赤]
チューブ1: [黄]
チューブ2: [赤,赤]
チューブ3: [黄,黄,黄]
チューブ4: [緑,緑,緑,緑]

ステップ 10:
アクション: チューブ0からチューブ2へ水を移動
チューブ0: [空]
チューブ1: [黄]
チューブ2: [赤,赤,赤,赤]
チューブ3: [黄,黄,黄]
チューブ4: [緑,緑,緑,緑]

ステップ 11:
アクション: チューブ1からチューブ3へ水を移動
チューブ0: [空]
チューブ1: [空]
チューブ2: [赤,赤,赤,赤]
チューブ3: [黄,黄,黄,黄]
チューブ4: [緑,緑,緑,緑]