🀄上海のクリア可能パターン生成

🀄上海🀄

「上海」とは、積み上げられた麻雀牌の山から、

• 左右少なくとも一方に隣接する牌が無く、
• 上に別な牌が積み重なっていない、
• 同じ柄の牌の組

を取り除いて行き、すべて取り除いたらクリアというパズルゲームです。

基本的には 144枚(数牌+字牌+花牌+季節牌)の牌を使いますが、難易度や盤面設定により様々なバリエーションがあります。牌の積み方も色々。

上海の指南書や攻略サイトなどでは、

• 左右少なくとも一方に隣接する牌が無く、上に別な牌が積み重なっていない牌

のことを、自由牌と呼ぶようです。

この定義を使って言い換えれば、「上海」は、

• 積み上げられた麻雀牌の山から、同じ柄の自由牌の組を取り除いて行き、全て取り切ったらクリアというパズルゲーム

ということになります。

サンプル: とりあえず遊んでみよう

See the Pen Shanghai by nagtkk (@nagtkk) on CodePen.

大きい画面で
難易度低めの積み方

• マウスクリックで選択
• 全部消せたら clear
• これ以上取ることができない状態(詰み)になったら game over と表示されます。
• 各種ボタン
  • Undo: 一手戻る
  • Reset: 最初に戻る
  • New: 新規問題を生成
• 生成される問題は、解答が一つ以上存在します。

本題

前回、四川省をやったのでその流れで上海、なんですけど、

上海は真面目に作ろうとすると結構難しい。

コード自体は割とシンプルに収まるのですが、盤面の生成周りが色々と大変。
少なくとも初心者向きとは言い難い。

と言うわけで、前回と異なり実装例の紹介まで行きません。
基礎部分の作り方と盤面生成の話をメインにしようかと思います。

サンプルの中身が見たい方は CodePen からどうぞ。
描画部分は相変わらず手抜き気味ですが。

あとは四川省でやったショートコーディングも無しです。
上海は色々と理由があって向かないと思っているので。

基礎部分: 盤面状態の表現と自由牌判定

さて、上海を作るには、まず麻雀牌の山をデータとして表現する必要があります。
上海で用いられる麻雀牌の山は、山と言うくらいですから３次元です。
また、単に並んでいるだけではなく牌を縦横「半分ずらして」配置することができます。

やり方は一通りではありませんが、今回は「縦横二倍の密度の盤面」を高さ毎に用意し、
4マスセットで一つの牌を表現することにします。

こうしておけば、「半分ずらし」も問題なく表現できます。
「隣の牌」は、データ上「2マス」離れていることになります。

この形式のデータで自由牌か否かを判定するには、判定対象の座標を (x,y,z) とすると、以下の領域に他の牌があるかを判定すれば良いことになります。

柄の判定は、柄 ID でも付けて比較すればよいので略。

これで実行に必要なものは一通りそろいました。

選択された二つの牌が、

• 同じ柄である
• どちらも自由牌である

ならば、取り除くだけです。

いやあ楽ちん楽ちん、

とならないところが上海の怖いところ。

乱数による盤面生成の問題点

前回の「四川省」も、今回の「上海」も、単に乱数のみで盤面を生成すると、最初から詰んでる(クリア不能)パターンが発生することがあります。

四川省の時は、実装例では「内部的に一度手当たり次第に解いてみて、解けなかったら再生成」としていました。
ショートコーディング版ではそれすらさぼって、「詰んでたらプレイヤーがリロードしてね」と雑な対処をしていました。
「四川省」は、そもそも初期状態で詰んでいる可能性が低いので、こんなんでも割と遊べてしまいます。

が、「上海」ではそうもいきません。乱数頼りで盤面生成すると、最初から詰んでいるケースが多いのです。

どのくらい詰みやすいかは、牌の積み方で変わってきますが、今回使った積み方 TURTLE (サン電子版では「龍」)では、50個生成して全部クリア不能 みたいなことも起こります。

何らかの対処をしないと「普通に遊べる」状態になりません。

一つのやり方は、盤面をランダムに生成しコンピュータに解かせるプログラムを書いてしまう方法です。
実際に解けたもののみ採用すれば、最初から詰んでいる状態は回避できます。
時間がかかるので、実行時にやるのではなく、事前に作りためて実行時には単にロードするだけ。
ついでに難易度のラベリングなんかもしておけば、ゲームの幅が広がります。
(自動で難易度判定するのは、それはそれで別方向で難しい話ですが)

あるいは、製作者が解いてみて解けたやつを記録するとか、手作業で盤面作るとかいう手もありかもしれません。(大変そう)

今回は別なアプローチで、「必ず一つ以上解が存在する」ように上海の盤面を自動生成する方法を解説しようかと思います。

追記: なお、白紙の状態から牌の組を置いていく、と言う方針を取ると、色々と問題がでてきます。コメント欄にて。

無地上海を利用した盤面生成

無地上海、という名前は今適当に決めました。
要は「柄のない」(あるいは「柄がすべて同じな」)上海のことです。
柄が無いので、自由牌ならどれでも組にできます。

生成したい普通の上海と同じ牌の積み方で無地上海を作り、自由牌からランダムに組を作って取り除いて行きます。
このとき、取った牌の組を元の位置も含めて覚えておきます。
そして、解いた後に実際に組(ペア)になった牌に後付けで柄を決め、元の形になるように積みなおします。

こうして出来上がった上海は、無地上海と同じ手順で解くことができます。
つまり、解が一つ以上存在する、を満たせたわけですね。

上海に限らず、パズルゲームでは「制約緩めて解いてしまって後付けで都合のいい条件を追加する」やり方がいろんな場面で役に立ったりします。自作のパズルゲーム作るときとか。
閑話休題。

これで詰んでない上海が作れた、

と言いたいところですが、これでも上手くいかないのが上海の怖いところ。(二回目)

無地上海にも解いている最中に「詰み」が発生する可能性があるので、完全ランダムではなく、詰みを回避するように解く必要があります。

無地上海の詰む・詰まない

柄のない上海が詰むのは「組が作れない」つまり「自由牌が一つしかない」ためです。

例えば以下のようなケース。

最終的に自由牌が 1 になって詰みます。
これらはあくまで一例で、他にも色々と自由牌 1 に至るパターンがあります。

「自由牌が 1 になったその時に詰んでいる」のではない点にご注意ください。
その前段階から、回避手段が存在しないので既に詰んでいます。
つまり、詰み回避のためには、「最終的に自由牌が 1 になるルート」に突入しないことが必要です。

逆に、詰み回避できているパターンも見てみましょう。

上は、「取り方によっては詰むけれど、順番を間違えなければ詰まない」ケース。
下は、「どうあがいても詰まない」ケースです。

これらは詰むパターンと一体何が違うのか、というのを厳密にやりだすとひたすら長くなるので、十分条件で抑え込んでしまいましょう。

$$ {\rm 最も高い自由牌の高さ} - {\rm 二番目に高い自由牌の高さ} \lt {\rm 自由牌の個数}$$

の時、まだ詰んでいません。そうでない場合、詰んでいる可能性があります。
とりあえず詰み回避条件とでも呼びましょうか。

よくわからんと言う人は、上の図と見比べてみるとわかりやすいかも。
要は、「自由牌 1 」の状態は「高低差を埋めるために必要な自由牌が足りない」時に発生するので、高低差が開きすぎちゃうと取り方工夫しても挽回できなくなるかもよ、ということですね。

初期状態で詰み回避条件に合致していれば、この条件を維持するように取ることで、無地上海は詰まずに解ききることが可能です。

この方法は、十分条件で縛っているので、本来詰まないパターンも一部回避してしまっている(理論的に生成可能なパターンをすべて網羅はできない)ことになります。
実用上十分だろうと思いますが、一手間違えただけで即詰むようなスリルのある上海がやりたい、という場合には、この方法は適していません。

また「高さがある牌の下面には他の牌がある」という前提での話ですので、変則的な上海には適用できませんのでご注意を。

コーナーケース

今回の TURTLE では起こらない話ですが、牌の積み方によっては、実際には解けるけど初期状態で詰み回避条件に合致していない、と言うケースもあります。
その場合は、条件を満たすまで「最も高い自由牌を含む組」を取っていきます。
進めていくと、高低差が維持あるいは減少し、解が存在するならばいずれ条件を満たすようになります。

もし詰み回避条件を満たさないまま詰んでしまった場合。
その牌の積み方には、そもそも解が存在しません。
普通の上海としてもクリアパターンが存在しないことになります。

ちなみに、組の両方とも常に高いものから取っていくという方法でも、解が存在する場合には無地上海を解ききることができます。
ただし最終的に出来上がる上海は、とりあえず上から取っていけばクリアできるイージーモードになります。
ミニゲームとかはそれでもいいのかも。

詰み回避条件の維持

今回サンプルで使った方法は、基本的にはランダムに自由牌の組を選びますが、

$$ {\rm 最も高い自由牌の高さ} - {\rm 二番目に高い自由牌の高さ} + 2 \ge {\rm 自由牌の個数}$$

の時は、取り除く牌を、

• 一つ目は最も高いもの
• 二つ目はランダム

にする、というものです。

詰みルートに突入する可能性があるときに、片方を最も高いものから取ることで高低差が開かない(=詰み回避条件を維持する)ようにしています。
コーナーケースの場合にも、最も高い自由牌を含んだ組が選ばれます。

詰む危険性がない時には単にランダムに取っていくので、常に簡単になってしまうという心配はあまりありません。

さて、これで詰まずに無地上海が解けるようになったので、前述の方法で解が一つ以上存在する上海のパターンが作れます。

おつかれさま！

おまけ: 麻雀牌

スタイルシートでごり押し。
若干おかしいけど、まあ、黙ってりゃバレないバレない。

See the Pen Mahjong Tile by nagtkk (@nagtkk) on CodePen.

余談: なぜショートコーディングに向かないのか

一つには、ここまで散々述べてきたように、詰みパターンの回避を入れないとそもそも遊べる状態になりにくいからです。
ショートコーディング的には、その手のものを省いてでも短さを追求する方が「ぽい」と思うのですが、遊べないものを作ってもなあ、と色々と悩みどころ。

で、二つ目に「牌の積み方」が大半を占めてしまうから、というのがあります。

今回のサンプルでは、積み方データは牌の有無を表す 0 or 1の 配列で 32 * 17 * 5 = 2720 要素あります。でかい。

牌は144個しかないので、座標で持つようにすれば 144 要素にできますが、それでもまだでかい。

牌の有無を一行まとめて 32 ビットの整数として扱えば、17 * 5 = 85 要素。一要素当たりのコードが長くなるので効果はいまいち。

で、ここから短くしようと考えると、ランレングスかハフマンか、いや事前に要素間の差分を取ったほうが……それもうショートコーディングっていうかデータ圧縮の話だよね？

面白さが無いとは思いませんが、どんどん別物になってくるので、個人的にはショートコーディングには向いてないなあという結論に至りました。
上海自体は面白いんですけどね。

まとめ

• 上海のサンプルと基本的な作り方を解説しました。コード解説はサボった。
• 適当に盤面作るとまともに遊べないぞ！気をつけろ！
• 事前に盤面作ってもいいけど、楽したいよね。
• 無地上海使うと盤面生成できるぞ！
• 無地上海にも詰みがあるぞ！
• 詰みルート回避しよう！
• 回避できた！
• でもショートコーディングに向かない。悲しい。
• ｼｬﾝﾊｰｲ