マインクラフトで表現する組み合わせ最適化問題 featuring K3Tunnel Part2

はじめに

　本投稿は、マインクラフトで表現する組み合わせ最適化問題 featuring K3Tunnel Part1の続編です。Part1では、K3Tunnelサイト内に用意されているミッション「家電買いかえ大作戦」を、装備買いかえ大作戦に置き換えて、マインクラフトの世界で組み合わせを試行錯誤できるようにする仕組みを紹介しました。Part2では、Education Editionに搭載されているビジュアルプログラミング機能（MakeCode）を用いて、K3Tunnelサイト上にあるプログラムサンプルを移植し、10万円の予算におさまる組み合わせの中から、家族全体の満足ポイントが高くなるものを抽出してみようと思います。

K3Tunnelのプログラムサンプル

　まずは、本家のプログラムです。家電買いかえ大作戦のプログラムは、1～3のチュートリアルを順に進めることで徐々に完成していきます。今回は、チュートリアル3まで終わった段階のプログラムを移植します。できあがり例は、こちらのリンクに飛んでから、左上に表示される1～3の数字の3をクリックするとみることができるはずです。
　ビジュアルプログラミング形式のため、コードの形でここに記載することができないのですが、全体が収まる形のスクリーンショットも参考として掲載します。

K3Tunnelサイトより転載

　今回のケースでは、取りうる組み合わせが$4^3=64$通りであり、現実的な時間内ですべての組み合わせについて計算することが可能であるため、全数探索で条件に合致する組み合わせを見つけるアプローチになっています。

MakeCodeへの移植

　前節で紹介したプログラムをMakeCodeに移植します。K3TunnelとMakeCodeはどちらもGoogle Blockyをベースとするビジュアルプログラムで兄弟のような関係なのですが、実装が異なるため完全互換というわけにはいきません。そこで、パーツに分解しながら移植を進めていきます。

定数・変数の定義

　K3Tunnelのできあがり例は、選択する家電製品の価格や満足ポイントなどの定数の定義部分は省略されて（実装済みの状態になって）います。MakeCodeに移植する際には、この部分を明示的に定義しなおす必要があります。

　K3Tunnelのプログラムでは、「家電製品」というオブジェクトに、価格や満足度などの属性値が定義されているような雰囲気を感じますが、MakeCodeではオブジェクトを定義できないため、文字列型の配列として各種装備品の属性値を定義します。

index	格納する値
0	装備品の名称
1	たかしくん満足ポイント
2	おとうさん満足ポイント
3	おかあさん満足ポイント
4	値段

上のスクリーンショットでは見切れてしまっていますが、全部で12種類の装備品に対して各種値を設定します。

ループ

K3Tunnelのプログラムでは、購入対象の3種類の家電カテゴリに対応する3つのインデックス(i,j,k)を使うループを用いています。

　MakeCodeでも同様に3つのインデックスを用いますが、ループの表現が異なるため以下のようになります。

製品の選択

　製品を選択する部分は、K3Tunnelでは次のようになっています。

　ループのインデックスとなっている(i,j,k)を指定して、そうじ機のi番目の製品、クッションのj番目の製品、ホームベーカリーのk番目の製品を設定する形です。
同様の処理をMakeCodeで実装したいのですが、文字列型の配列である各種製品情報をさらに配列として扱うことができないようなので、以下のように関数用いて、(i,j,k)のインデックスを引数として与えたときに、対応する製品情報をヘルメット、チェストプレート、レギンズという変数に格納する処理を行うようにします。

　図中のヘルメット設定は、次のような関数として定義しています。チェストプレート設定、レギンズ設定も同様です。

満足ポイントの計算

　製品の組み合わせが定まったら、その組み合わせに対する満足ポイントを計算します。K3Tunnelでは以下のような処理になっています。

　選んだ組み合わせに対する、たかしくんの満足ポイント、おとうさんの満足ポイント、おかあさんの満足ポイントを計算し、最後に合算する形です。K3Tunnelではかごの番号と対象者（たかしくん、おとうさん、おかあさん）を指定することで、対象者に関する、かごに入れた3種類の製品の満足ポイントの和を返す形のブロックになっています。MakeCode側の実装では「かご」というオブジェクトを定義していないので、製品ごとの満足ポイントの和を直接計算する形にします。

合計金額の計算

　満足ポイントの次は合計金額です。K3Tunnelのブロックは満足ポイントと似たような形で、かご番号と製品カテゴリを指定することで、かごに入れた製品の値段を返す形となっています。

　MakeCodeでは以下のように実装しました。満足ポイントの場合と同様、かごの定義がないため、今選んでいる製品情報を格納している配列型の変数から、直接値段の値を参照しています。

条件判定

　ここまでの処理で、選んだ組み合わせに対する満足ポイントと合計金額が計算されました。ここからは予算の10万円以下に収まっているかどうかという判定と、満足ポイントが高い組み合わせの抽出を行います。予算の条件だけの場合、38通りの組み合わせが見つかりますが、最も満足ポイントが高くなる組み合わせを知りたいので、満足ポイントに関しても700という閾値を設けて、それ以上の満足ポイントになる組み合わせのみを抽出する処理になっています。

　K3Tunnelの実装では、グラフに描画する処理も含まれていますが、MakeCodeではグラフ化は省略し、チャットに条件に合致する組み合わせの情報を送信する処理にしています。

実行結果

　K3Tunnel、MakeCodeのそれぞれのプログラムの実行結果は以下のようになりました。

K3Tunnel

MakeCode

　家電製品と装備品の対応関係は、以下のようになっているので、同じ結果が得られていることがわかります。

家電買いかえ大作戦	装備買いかえ大作戦
ロボット型そうじ機	ダイヤモンドのヘルメット
高性能そうじ機	金のヘルメット
軽くてかっこういいそうじ機	鉄のヘルメット
旧型そうじ機	革の帽子
マッサージ機能付クッション	ダイヤモンドのチェストプレート
大きいくまさんクッション	金のチェストプレート
マイクロビーズクッション	鉄のチェストプレート
普通のシンプルクッション	胸当て
本格派具材自動投入HB	ネザライトのレギンズ
お手軽派HB ピザやチーズも	ダイヤモンドのレギンズ
ご飯でパンが焼けるHB	金のレギンズ
食パン焼くだけHB	革のズボン

マイクラ上に作った防具屋の仕掛けでの検算

　最後は、Part1で作成した防具屋の仕掛けでの検算です。プログラムで得られた組み合わせを防具立てに装着させて、満足ポイントと合計金額が同じ結果になるかを確認します。

　動画では計算結果のサイドバーが見づらくなってしまいましたが、以下のようにプログラムと同じ結果が得られました。

ダイヤモンドのヘルメット+鉄のチェストプレート+革のズボン

金のヘルメット+金のチェストプレート+革のズボン

金のヘルメット+鉄のチェストプレート+ダイヤモンドのレギンズ

金のヘルメット+鉄のチェストプレート+革のズボン

まとめ

　K3Tunnelの家電買いかえ大作戦のプログラミング部分を、MakeCodeで実装しなおし、Minecraft Education Edition上で計算できるようにしました。MakeCodeでの計算結果とPart1で作成したレッドストーン回路による計算結果を比較し、同じ結果が得られることを確認しました。
　MakeCodeでK3Tunnelと同様の結果が得られるプログラムを作ることができましたが、K3Tunnelの方が、問題の構造に合わせて、直感的にわかりやすい形でデータ構造が定義されていたり、コードブロックが提供されていたりした印象です。
　プログラミングの入り口に立つ方々にむけては、K3Tunnelのように問題に合わせてカスタマイズされたわかりやすいパーツの組み合わせで、うまく動くコードをくみ上げる体験を提供できることが大事なのかもしれませんね。

付録 Javascript版

　Minecraft Education Editionには、MakeCodeで作ったプログラムをJavaScriptに変換する機能があるので、今回作ったプログラムを変換してみました。

player.onChat("kaden", function () {
   player.say("計算開始")
   No = 1
   for (let i = 0; i <= 3; i++) {
       for (let j = 0; j <= 3; j++) {
           for (let k = 0; k <= 3; k++) {
               ヘルメット設定(i)
               チェストプレート設定(j)
               レギンズ設定(k)
               たかしくん満足ポイント = parseFloat(ヘルメット[1]) + (parseFloat(チェストプレート[1]) + parseFloat(レギンズ[1]))
               おとうさん満足ポイント = parseFloat(ヘルメット[2]) + (parseFloat(チェストプレート[2]) + parseFloat(レギンズ[2]))
               おかあさん満足ポイント = parseFloat(ヘルメット[3]) + (parseFloat(チェストプレート[3]) + parseFloat(レギンズ[3]))
               合計満足ポイント = たかしくん満足ポイント + (おとうさん満足ポイント + おかあさん満足ポイント)
               ヘルメット価格 = parseFloat(ヘルメット[4])
               チェストプレート価格 = parseFloat(チェストプレート[4])
               レギンズ価格 = parseFloat(レギンズ[4])
               合計金額 = ヘルメット価格 + (チェストプレート価格 + レギンズ価格)
               if (合計金額 <= 100000) {
                   if (合計満足ポイント >= 700) {
                       player.say("かごナンバー：" + No)
                       player.say("ヘルメット：" + ヘルメット[0])
                       player.say("チェストプレート：" + チェストプレート[0])
                       player.say("レギンズ：" + レギンズ[0])
                       player.say("合計満足ポイント：" + 合計満足ポイント)
                       player.say("合計金額：" + 合計金額)
                       player.say("--------------------")
                   }
               }
               No += 1
           }
       }
   }
})
function チェストプレート設定 (数値: number) {
   if (数値 == 0) {
       チェストプレート = ダイヤモンドのチェストプレート
   } else if (数値 == 1) {
       チェストプレート = 金のチェストプレート
   } else if (数値 == 2) {
       チェストプレート = 鉄のチェストプレート
   } else {
       チェストプレート = 胸当て
   }
}
function ヘルメット設定 (数値: number) {
   if (数値 == 0) {
       ヘルメット = ダイヤモンドのヘルメット
   } else if (数値 == 1) {
       ヘルメット = 金のヘルメット
   } else if (数値 == 2) {
       ヘルメット = 鉄のヘルメット
   } else {
       ヘルメット = 革の帽子
   }
}
function レギンズ設定 (数値: number) {
   if (数値 == 0) {
       レギンズ = ネザライトのレギンズ
   } else if (数値 == 1) {
       レギンズ = ダイヤモンドのレギンズ
   } else if (数値 == 2) {
       レギンズ = 金のレギンズ
   } else {
       レギンズ = 革のズボン
   }
}
let 合計金額 = 0
let レギンズ価格 = 0
let チェストプレート価格 = 0
let ヘルメット価格 = 0
let 合計満足ポイント = 0
let おかあさん満足ポイント = 0
let おとうさん満足ポイント = 0
let レギンズ: string[] = []
let チェストプレート: string[] = []
let ヘルメット: string[] = []
let たかしくん満足ポイント = 0
let No = 0
let 革のズボン: string[] = []
let 金のレギンズ: string[] = []
let ダイヤモンドのレギンズ: string[] = []
let ネザライトのレギンズ: string[] = []
let 胸当て: string[] = []
let 鉄のチェストプレート: string[] = []
let 金のチェストプレート: string[] = []
let ダイヤモンドのチェストプレート: string[] = []
let 革の帽子: string[] = []
let 鉄のヘルメット: string[] = []
let 金のヘルメット: string[] = []
let ダイヤモンドのヘルメット: string[] = []
ダイヤモンドのヘルメット = [
"ダイヤモンドのヘルメット",
"100",
"100",
"70",
"80000"
]
金のヘルメット = [
"金のヘルメット",
"100",
"80",
"90",
"60000"
]
鉄のヘルメット = [
"鉄のヘルメット",
"50",
"60",
"90",
"30000"
]
革の帽子 = [
"革の帽子",
"30",
"50",
"50",
"20000"
]
ダイヤモンドのチェストプレート = [
"ダイヤモンドのチェストプレート",
"50",
"100",
"60",
"50000"
]
金のチェストプレート = [
"金のチェストプレート",
"100",
"50",
"80",
"30000"
]
鉄のチェストプレート = [
"鉄のチェストプレート",
"70",
"70",
"80",
"10000"
]
胸当て = [
"胸当て",
"50",
"70",
"50",
"5000"
]
ネザライトのレギンズ = [
"ネザライトのレギンズ",
"100",
"70",
"50",
"40000"
]
ダイヤモンドのレギンズ = [
"ダイヤモンドのレギンズ",
"70",
"70",
"80",
"30000"
]
金のレギンズ = [
"金のレギンズ",
"60",
"50",
"80",
"20000"
]
革のズボン = [
"革のズボン",
"50",
"100",
"60",
"5000"
]