CTF SECCON TOWERに挑んでみました

解けなかったのでwriteupじゃないです.感想です.


12/10 15:00~12/11 15:00までの間,「SECCON 2016 Online CTF」というセキュリティの大会が行われていました.

僕はセキュリティについてほとんど勉強をしたことがなかったのですが,とあるチームに入って参加してみました.

CTFとは

キャプチャー・ザ・フラッグ - Wikipedia

与えられた問題文,データから,プログラムの脆弱性を見つけるなどして隠されたFlagを手に入れろってルールです
例えば,暗号化された文章が用意されて,それを復号化するとか,
Webアプリケーションが用意されて,そこに不正アクセスするとか...
そんな感じのセキュリティの知識を競う大会です.

SECCON TOWER

まぁ,予想はしてたのですが,素人の僕がいきなり挑んで勝てる問題は殆ど無かったです.
でも面白そうな問題が1問,それがこの「SECCON TOWER」でした.

PNG over Telegraph

PNG over Telegraph
Analyze signal in this video.
You will able to get PNG, if you success to decode it.
https://youtu.be/Y6voaURtKlM

Youtubeの動画が与えられて,この動画からPNG画像を手に入れろという問題です
動画を再生してみると...
f:id:wgg00sh:20161211180044p:plain

なんかよくわからない機械がぐるぐる回ってます.50分間それが流れるだけの動画でした.

解いてみる

チームメイトと考えていたら,「動画初めに書かれている英文と動きが対応しているのでは?」と推測したので,
動画の0:12~1:10頃に書かれる英文と,動きを眺めてみると,「1つの姿勢=1つの文字」と対応しているっぽいことがわかりました.
動画内の全てのアルファベットと,動きを対応付けてみたら,下のようになりました.

f:id:wgg00sh:20161211181922p:plain

足りない文字がありますね...
でも近辺の文字から推測できそうです.
A~Hが子の腕が同じ姿勢で中心が45度回りの1つのグループ,
I~QのうちJを除いた8つが同じく1つのグループ,
R~Yも1つのグループっぽいです.

f:id:wgg00sh:20161211181940p:plain

Zは推測できませんでした...

動画から姿勢を抜き出す

流石に50分の動画を見続けるのは苦痛なので,プログラムで全ての動きを抽出してみました.
c++とopencv3.1を使用しています

void capture()
{
  VideoCapture video("SECCON TOWER 2016.mp4");

  const int OFFSET = 15;
  const int START_POS = 2250 + OFFSET;
  const double FPS = 29.97;
  video.set(CV_CAP_PROP_POS_FRAMES, START_POS);
  int i = 0;
  while (1)
  {
    Mat frame;
    i++;
    video >> frame;
    video.set(CV_CAP_PROP_POS_FRAMES, START_POS + i * FPS);
    if (frame.empty() || waitKey(30) >= 0 || video.get(CV_CAP_PROP_POS_AVI_RATIO) == 1) {
      break;
    }
    string fName = "image/"+to_string(i)+".jpg";
    imwrite(fName, frame);
  }
}

できあがったのがこれ↓
f:id:wgg00sh:20161211182930p:plain
3000枚近くの画像が生成されました.

自動で識別する

この3000枚の画像を手作業でアルファベットに置き換えていては時間が足りません.
そこで,画像を与えたらどの文字なのか返してくれる処理を作ります.
考え方としては,
「『入力画像』と『25種類のサンプル画像』を比較して,最も似ているものが,対応する文字」
と決めつけます.
まずは画像に無駄な部分が多すぎるので機械だけが映るようにトリミングします.
f:id:wgg00sh:20161211183459p:plain

そして,先に作った姿勢ー文字の対応表を見ながら25枚のサンプル画像を探し出します.
同じ文字であれば,別の画像でも殆ど同じように映ると予測しています.

類似度計算

入力画像,サンプル画像に対してそれぞれ,グレースケール化をした後に画像の類似度を計算します.
25枚のサンプル画像との類似度で最も高いものを選別します.

void convert1(Mat &mat)
{
  cvtColor(mat, mat, CV_BGR2GRAY);
}

void similarly()
{
  const int FIRST = 3;
  const int LAST = 2982;
  const int CHARA = 25;

  int channels[] = { 0 };
  int dimNum = 1;
  int binNum = 64;
  int binNums[] = { binNum };
  float range[] = { 0,256 };
  const float *ranges[] = { range };

  int sampleNum[CHARA] =
  {16,11,271,252,634,4,
    570,652,12,1014,27,102,44,
    856,2059,514,41,2018,992,53,84,
    959,33,104,686,};
  MatND sampleHist[CHARA];
  for (int i = 0; i < CHARA; i++) {
    string fName = "resize/" + to_string(sampleNum[i]) + ".jpg";
    Mat mat = imread(fName);
    convert1(mat);
    calcHist(&mat, 1, channels, Mat(), sampleHist[i], dimNum, binNums, ranges);
  }

  for (int i = FIRST; i <= LAST; i++) {
    string fName = "resize/" + to_string(i) + ".jpg";
    Mat mat = imread(fName);
    MatND hist;
    double similarly;
    convert1(mat);
    calcHist(&mat, 1, channels, Mat(), hist, dimNum, binNums, ranges);

    int max = 0;
    int maxPos = -1;
    for (int j = 0; j < CHARA; j++) {
      similarly = compareHist(hist, sampleHist[j], CV_COMP_INTERSECT);
      if (max < similarly) {
        max = similarly;
        maxPos = j;
      }
    }

    char c = 'A' + maxPos;
    cout << c;
  }
  cout<<endl;
}

実行結果
f:id:wgg00sh:20161211184356p:plain

「目視したのと全然違う...」
どうやら計算誤差が発生して希望通りの符号を返してくれませんでした.

誤差の原因

動画の前半と後半の画像を見比べてみました

f:id:wgg00sh:20161211184831p:plainf:id:wgg00sh:20161211184840p:plain

↓横に並べます
f:id:wgg00sh:20161211184919p:plain

「なんかずれてる...」

もうダメぽ

というわけで,カメラの位置が時間経過で動くことに気づいて,それを補正するトリミングを実装する途中で時間切れになってしまいました...

敗因

一番大きいのは類似度計算に頼った点かもしれないですね
画像の状態が変化
すると敏感に反応するので
子の腕の黒色部分の位置と向きを入力画像から識別するマッチングが実装できれば結果は変わったかも...

腕木暗号

www.silex.jp
今回出題された問題は「腕木通信」と呼ばれる情報の伝達方法の一つらしいです.
あと正しく解読できればCTFおなじみのQRコードの画像が生成されたらしいですが,自分にはできませんでした...

おわりに

学校の授業でちょうど最近まで画像処理の実験をやっていたので,その成果を実践できる良い機会でした.
できれば正解してチームに貢献したかったのですが解けなくて悔しかったです.

初めてCTFに挑戦したのですがとても楽しかったのでまた機会があればやってみたいですね~

過去に接続した無線LANに自動で接続するPowerShell Script書いた

最近PowerShellで遊んでいます.




前置き

Windowsを使ってると,時々突然WiFiが切れてイラっとすることがありました.
もしくは,起動したときに普段使いの無線LANに繋がっていない時がありました.
再接続するにはタスクバーからインターネットアクセスを選んで,接続したいネットワークを選んで,接続ボタンを押す必要があります

f:id:wgg00sh:20161111130338p:plain
f:id:wgg00sh:20161111130501p:plain
f:id:wgg00sh:20161111130544p:plain

これって結構面倒じゃないですか?

コマンド入力するか,アイコンをダブルクリックするだけで勝手にWiFiに繋いでくれる,そんなことができたらいいな~って思ったのでちょっと書いてみました

完成したスクリプト

Windows無線LANの設定などを変更するので,.ps1ファイルで作成します

chcp 65001

$profiles
$lans
$i
$length
$result
$successMessage="Connection request was completed successfully."

netsh wlan disconnect
$profiles=(netsh wlan show profiles)
$length=$profiles.length

for($i=0; $i -lt $length;$i++)
{
    if($profiles[$i] -match ": ")
    {
        $lanName=$profiles[$i].Split(":")[1].Split(" ")
        echo($lanName[1])
        $result=(netsh wlan connect name=($lanName[1]))
        echo $result
        if($result -eq $successMessage)
        {
            echo(" `n` `n` Connection successed !!")
            exit
        }
        echo(" `n``n` Connection failed...")
    }
}

↑のコードを適当なファイルに記述して,拡張子.ps1で保存しPowerShellで実行すれば登録されている無線LANに自動で繋いでくれます

実行ポリシーの変更

...のですが,PowerShellはデフォルトではスクリプトを実行できません.セキュリティとかの問題ですね
僕が前に書いた記事とか↓に実行ポリシーを変更する方法が書いてあるので,必要に応じて変更してみてください
wgg.hatenablog.jp
qiita.com

まだアイコンダブルクリックで実行できない

PowerShellスクリプトは,アイコンをダブルクリックしてもメモ帳などのエディタが開くだけで実行してくれません.
ですが,従来のコマンドプロンプトのbatファイルはダブルクリックで実行できます
そこで作成したPoweShellスクリプトを実行するためのコマンドプロンプトのバッチファイルを作ります

@echo off
powershell -Command "***.ps1"
.ps1に作成したPowerShellスクリプトのパスを渡します

拡張子を.batで保存すれば,そのbatファイルをダブルクリックするだけでPowerShellスクリプトが実行できるようになります
アイコンからじゃなくコマンドで実行したいって場合は環境変数弄るとできます

コードの説明

batファイルの方はPowerShellを起動して,引数のスクリプトを実行しているだけなので省略します

chcp 65001

文字コードの設定です
実行する環境によって文字コードが違った場合,実行したコマンドの返り値が変わったり文字化けしたりする場合があります
なので,どこでも同じように実行するために環境の統一ですね

次の6行は変数宣言です
一部無くても大丈夫ですが,一応

netsh wlan disconnect

無線LANの接続を終了します
この後で接続するので,一旦切りますね

$profiles=(netsh wlan show profiles)

(netsh wlan show profiles)の実行結果を変数$profilesに代入します
(netsh wlan show profiles)のみ実行すると,実行結果が出力されます
PowerShellScriptでは,コマンドの実行結果は返り値として扱われるので,変数に代入することで実行結果を保存することができます
f:id:wgg00sh:20161111150758p:plain
↑こんな感じで,右下の隠し部分に登録済みのネットワークが表示されます
また,変数$profilesにはこの出力結果が配列として1行ずつ格納されます.

for($i=0; $i -lt $length;$i++)

c言語とかで書くなら

for(i=0;i<length;i++)

になるいつものfor文です
$profilesを1行ずつ操作していきます.

if($profiles[$i] -match ": ")

(netsh wlan show profiles)の実行結果から,セミコロン+空白(: )の右に無線LANの名前が書かれていることが分かったので,それを含む行に対してのみ次の処理を行います

$lanName=$profiles[$i].Split(":")[1].Split(" ")

1行毎に,セミコロンで区切った後,その後ろ側を空白で再度区切ります
かなり雑に作ってるので,もっとスマートな書き方がありそうです
しかもこの書き方だと無線LANの名前に空白が含まれていたらそこも分割してしまいます.
これを実行すると,$lanNameには
$lanName[0]=" " (空白スペース1つのみ)
$lanName[1]="***" (ネットワークの名前)
となるので,$lanName[1]を利用して,次に接続要求を行います

$echoはいわゆるprintfなので省略

$result=(netsh wlan connect name=($lanName[1]))

(netsh wlan connect name= STR)でSTRに対して接続要求を行います
$result=...としているので,その実行結果を変数$resultに格納します
これは,成功したか失敗したかを判定するのに使用します

if($result -eq $successMessage)
  • eqは == です,同一かどうか判定しています.

実行結果が成功時に出力される文字列なら接続に成功したとみなして処理を終了,
失敗していたらforのカウントを進めて次のネットワークで再接続します

終わりに

こんな感じで,使うかわからないスクリプトを作成することができました.
自分の環境でしか試していないのでもしかしたら不具合起きるかもしれません.
というか自分の環境でも接続できないはずのネットワークに対して成功時のメッセージが出たりと,不具合が出ることがありました

あとは,このコードだと登録順に接続するので,あまり使いたくないネットワークに勝手に接続してしまうかもしれません
その場合は,$profilesを手書きして,優先度の高いネットワークから順に書くなどすると良いかもしれませんね
また,この方法だけだと,公共のWiFiによくあるWebページを開いて,そこで再度認証するタイプに対応できないので,必要ならそこも対応する必要がありますね

Bash on Ubuntu on Windows を使ってみたのと,環境構築

 

メモ書きに近い内容です.

Bash on Ubuntu on Windowsの使用感想と設定書き綴り

(以下,Linux初心者の発言)

 

はじめに

Bash on Ubuntu on Windows(BoW) という機能が今年の8月にWindows 10に実装されました.どうやらWindows上でLinuxbashが実行できるようです.ということで今回これを少し触ってみました.

 

経緯

僕の通っている大学の授業でプログラムを書く場合は,基本的にLinux(CentOS)で行っています.大学には生徒が自由に使用できるCentOSの入ったマシンがあるのですが,自宅で大学と同環境を用意する場合,大学のサーバに接続する(重い)か,仮想マシンを構築するなどをしなくてはなりません.また,大学のアカウントはユーザに与えられる容量が非常に少ない(ブラウザのキャッシュなど含めて100Mb)です.以前はVirtual Boxを使っていたのですが,最近挙動が重くなってきたので,BoWを試してみることにしました.

 

ということで,大体以下の事をやってみました

  1. BoWの導入
  2. GUIの導入
  3. 日本語入力の対応

この記事ではbashを実行する際にコマンドプロンプトではなく,PowerShellを使用しています

 

参考にしたサイト

Bash on Ubuntu on Windowsをインストールしてみよう! - Qiita

Bash on Ubuntu on Windows + XmingによるGUI - Qiita

pc.casey.jp » Ubuntu で日本語が表示されない・文字化け

Bash on Ubuntu on Windows とX Windowの組み合わせで日本語表示と日本語入力: tonopぶらり

about_Execution_Policies

Windows PowerShell プロファイル

PowerShell で Profile を利用して スクリプトの自動読み込みをしてみよう - tech.guitarrapc.cóm

 

1.BoWの導入

まずはBoWを実行できるようにしないといけません. Windows10をアップデートしても,デフォルトではBashは使用できないようです.

[コントロールパネル]→[プログラム]→[プログラムと機能]→[Windowsの機能の有効化または無効化]で機能のチェックリストを開いて,"Windows Subsystem for Linux(Beta)"をチェックして,インストール,再起動

再起動後,ストアアプリの[設定]を開き,[更新とセキュリティ]→[開発者向け]から"開発者モード"にチェック.

 

あとは,PowerShellとかからbashと入力すると起動できます.初回時はユーザー名とパスワードの入力を要求されます.

 

2.GUIの導入

ここまでで,一応bashが動くようになったのですが,まだ問題があります.僕は現在,大学の実験で画像処理をしています.今のままでは画像処理を行うプログラムのコーディングと実行はできても,実行結果の画像を表示することができないのです.そこで,調べたところXmingを使用するとBoWからGUIが起動できると書いてありました.

Xmingの導入

ダウンロードファイル一覧 - Xming X Server for Windows - OSDN

↑公式サイトからXmingと,Xming-fontsをダウンロードしてきます.

Xmingを起動した後,bash上で以下のコマンドを実行します

$ export DISPLAY=localhost:0.0

これで,GUIを開く場合はXmingを通して実行できるようになりました.

ImageMagickもちゃんと開けます()

f:id:wgg00sh:20161022164434p:plain

これGUIの導入ができたと思っていたのですが,実は問題点がありました.日本語表示ができませんでした.Sublime Textを開いて実験のソースコードを確認してみると,日本語コメントが全て文字化けではなく,文字コード(?)で表示されていました.FireFoxも開いてみましたが,同じように日本語の記事は全て読めませんでした.

 

日本語表示を可能にする

調べたところ,unifontをインストールすることで解決するみたいです.

bash上で以下のコマンドを実行すると日本語が表示できるようになりました.

↓僕のブログもちゃんと日本語で表示されています

f:id:wgg00sh:20161022165020p:plain

 

実行時に自動でGUIを使用可能にする

さて,GUI環境は整ったわけですが,今のままではXmingの起動,bashの起動,DISPLAYのパス設定と,起動するたびに余計な作業を行う必要があります.bashコマンドでbashを開くと,すぐにGUIが使えるようにしたいので,そのあたりを自動化してみました.

バッチファイルの作成(Windows側)

まず,Xmingを起動する必要があるのですが,面倒です.シェルでbashと打つだけで,Xmingを起動しながらbashを実行するようにしたいです.というわけで,バッチファイルを作成しましょう.

[コントロールパネル]→[システムとセキュリティ]→[システム]→[システムの詳細設定]→[環境変数]→○○(ユーザー名)のユーザ環境変数の一覧から,"path"を選択→[編集]→[新規]で,バッチファイルを保存するディレクトリを登録します.これで,そのフォルダの中にある"○○.bat"と書かれたバッチファイルは全て"○○"と入力するだけで実行できるようになります.

 

次に,pathに指定したフォルダの中にXmingのショートカットを作成します.バッチファイルと同様にpath内に存在するショートカットファイルは"○○.lnk"と入力すると実行することができます.

次にバッチファイルを作ります.

pathで指定したフォルダ内に,"好きな名前(既存のコマンドと被っているものはダメ).bat"という名前のファイルを作成します.今回は仮にmybash.batとでもしておきました.

mybash.batを好きなエディタ(meryおすすめやで)で開いて以下の内容を記述します.

 @echo off

start xming.lnk

bash

taskkill /im Xming.exe /F

1行目:実行したコマンドを表示しないようにします

2行目:Xmingを起動します,.lnk以左は作成したショートカットの名前

3行目:bashの起動

4行目:bashが終了した時点で実行されます.Xmingを終了します.なぜか/Fで強制終了モードにしないと終了できなかった

 

これで,bashコマンドの代わりにmybashコマンドを入力すると,Xmingを同時に起動してくれるようになりました.

ですが,さっきも書いたようにbashコマンドでXmingを同時に実行したいのです.

ということで,次はプロファイルの設定をします

PowerShellでは,起動時に特定のコマンドを実行するプロファイルを設定できます.

C:\Users\(ユーザー名)\Documents\WindowsPowerShell\Microsoft.PowerShell_profile.ps1

がプロファイルのファイルです.存在しない場合は作成しましょう.

そのファイルの中に,コマンドを入力すると,PowerShell起動時に自動的に実行されます.このファイルの中で,以下を記述して,起動時にbashコマンドをmybashコマンドにすり替えるようにしましょう

set-alias bash mybash

set-aliasはコマンドをコマンドを別の名前にしたエイリアスを作成します

エイリアスで作成したコマンドのほうが,bashコマンドなどよりも優先されるようなので,これでbashコマンドがXmingを起動しながらbashを起動するようになりました!(パチパチ

 

あとは,プロファイルを実行できるようにします.

Windows10はデフォルトではps1ファイルの自動実行が制限されているようです.一旦PowerShellを管理者権限で実行して,次のコマンドを入力し,実行権限を変更します.

set-executionpolicy -executionpolicy remotesigned 

 これで,次回からは起動時にprofileが自動で読み込まれ,bashコマンドがすり替えられます.

 

bash起動時の設定(bash側)

Xmingを通してGUIを開くまでの手順の中に,bash側で行う操作もありました.

$ export DISPLAY=localhost:0.0

 

です.

これをbash起動時に実行するようにしましょう.

bashから~/.bashrcを適当なエディタで開きます. 末尾あたりに先のコマンドをそのまま書き込みます.

これでbash起動時にexportコマンドが実行されるので,bash側でのコマンド入力も不要になります.

 

よって,PoweShellからbashコマンドを入力するだけで,GUIを開く準備ができた状態でbashを起動するようになりました(疲れた

 

3.日本語入力の対応

ここはまだできたとは言えない状態です.

どうも通常のshell,コマンドプロンプトからは日本語入力ができなかったので,ターミナルエミュレータを使用するのがよさそうでした.

Bash on Ubuntu on Windows とX Windowの組み合わせで日本語表示と日本語入力: tonopぶらり

まず,uim-fepuim-anthyをインストールします

$ sudo apt-get install uim-fep uim-anthy 

 次に,xtermをインストールします(多分他のソフトでもいけるんじゃないですかね)

$ sudo apt-get install xterm 

uimの設定をします.~/.uimを適当なエディタで開き,以下を記述

 (define default-im-name 'anthy)
(define-key generic-on-key? '("<Control> " "`"))
(define-key generic-off-key? '("<Control> " "`"))

 反映するために一旦bashを再起動します.

再起動後xtermを実行し,xterm上で

 $ uim-fep

 を実行,左下に"anthy[An-  R]"みたいなのが出てきます.この状態で,Ctrl+Spaceを押すと,"anthy[AnあR]"と変わり,日本語入力モードになります.これでターミナル上での日本語入力が実現できました.vimとか使って日本語のレポートも書けますね

 

まだできていないのが,任意のGUIアプリケーション上で日本語を入力することなのですが,これはどうやったらいいんでしょう...?わかりませんでした.

 

 

終わりに

というわけで,BoWを使ってみたのと,自分が試してみた設定でした.

正直仮想マシンとほぼ同じ感覚で使用できるので,あとはGUI上で日本語入力ができればもう仮想はいらない(?)かもって感じです.僕がまだBoWの不具合とかあまり知らないのかもしれませんが.PowerShellコマンドプロンプトからbash開いた時点では,日本語が存在するだけでカーソル位置とかがずれたりしますね.

あとここで書いたことは一応権限の変更とか色々インストールしてるので,念のため,自己責任でお願いします.

 

2017/2/10:追記

3.日本語入力の対応について
コマンドプロンプトなど,純正でWindowsから提供されている環境でbashを起動した場合,日本語入力ができません.

この記事ではそれの解決策として,xtermというLinux用の端末を起動して,その中でuim-anthyで日本語入力を可能にしています.

wsl-terminal(https://github.com/goreliu/wsl-terminal)というものを教えてもらい,こちらならWindowsから起動したそのままの状態で日本語入力ができるようです.

github.com

 

 

ProcessingをMeryでコーディングから実行までできるようにした

お久しぶりです,エディタ戦争にはあまり興味のないWGGです

 

ちょっとProcessingをMeryで開発できるようにしてみました.

(この記事はMeryが実行できるWindows向けの内容です)

          f:id:wgg00sh:20160821174746p:plain

 

あらすじ

  1. ちょっとProcessingの勉強してる
  2. メモ帳代わりにテキストエディタはMery使ってる
  3. 最近Processingのエディタにちょっと不満感じてた
  4. Meryってどうやらプラグインとかでプログラミング用の補完機能とか色々機能追加できるらしい
  5. じゃあProcesingをMeryで開発できるようにしよう!←今ここ
続きを読む

4次元空間でプレイするテトリスとそれを自動プレイするAIの話

前に作ったゲームの解説的なお話です.

 

↓過去の記事

wgg.hatenablog.jp

↓プレイ動画

www.youtube.com

はじめに

丁度2か月ほど前に,時間が空いていて,更にサークルで成果物発表会があったので,それに合わせてゲームを1つ作りました.

それが上の頭おかしい「4次元テトリス Tetris Dim.4」です.

DLはこちら↓

https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip

この記事は,4次元テトリスのルール解説と,AIの実装方法についての解説記事です.

 

f:id:wgg00sh:20160514185110p:plain

 

4次元テトリスのルール

一般的なテトリスは「10×20」のフィールドで,「7」種類のブロックを回転させて1列全て埋めてラインを消すことを目的とします.

 

4次元テトリスでは,上記ルールをそのまま次数を2つ上げただけです.

細かい数字まで言うと,

「5×5×5×10」のフィールドで,「7」種類のブロックを「6」つの回転軸で回転させて「5×5×5」の空間を埋めて消すことを目的とします.

次数と,移動方向・回転軸・ブロックの種類の対応表は以下の通りです.

 

f:id:wgg00sh:20160713224515p:plain

 

『なんで3次元の方が4次元よりブロックの種類が多いんだ?』

って疑問が出ると思います.

各次数のブロックを描いてみました

 

2次元

f:id:wgg00sh:20160713224809p:plain

3次元
f:id:wgg00sh:20160713224825p:plain
4次元(少し強引な可視化)

f:id:wgg00sh:20160713224852p:plain

 

 

2→3次元

まず,2次元から3次元でブロックが1つ増える点についてみて見ます

f:id:wgg00sh:20160713225120p:plain

f:id:wgg00sh:20160713225113p:plain

上の画像に描かれている3つのブロックは2次元空間では表現できない為,3つ増えます

ところが下の画像ではそれぞれ2次元で2種類だったブロックが3次元になることで1つに統一できます.これは回転軸が増えたためです.

 

3個の増加と,2この減少,結果的に1つ増えて8種類になります.

 

3→4次元

では,3次元から4次元ではどうなるのでしょうか.

f:id:wgg00sh:20160713225608p:plain

 

3次元から4次元になっても,新しい形のブロックパターンが増えることはありません.何故なら,4次元でしか表現できないパターンを作るには,ある1マスから別々の4つの軸の方向へ隣接するブロックが存在する必要があります.2次元から3次元にした時は,これが存在しましたが,3次元から4次元では存在しません.そもそも1つのパターンを構成するブロックの数が4なので,4方向に伸ばすためには構成するブロックが最低5つ必要になります.

対して,3次元で存在していた2つのパターンが4次元で増えた回転によって,同一視できるようになります.

結果,3次元と比べて,1つパターンが減り,合計7種類になります.

 

回転

上の表では4次元の場合,回転軸が6つと書いていました.

任意の次元数 n次元空間において,2つの軸からなる平面で回転する回転軸は(n-2)!個です.

 

有名なアレ

f:id:wgg00sh:20160713230612p:plain

数学の教科書にも出てくるアレです(2次元版)

 

4次元では↓の様になります.この中で,sin,cosを使用する軸を2つ選ぶのですが,その組み合わせが6通り存在します.

f:id:wgg00sh:20160713230647p:plain

 

という訳で,ここまでで一応4次元の動きについて軽く説明が終わりました(疲れた

 

 

 こっからAI

さて,ここからAIの実装についてです.

といっても,適当にネットから参考になりそうな記事を拾ってきて4次元テトリスに対応させた程度の事しかしていないのですが...

↓参考にした記事たち

nanamb.blog25.fc2.com

コンピュータにテトリスをプレイさせる AIテトリス

GitHub - takuma7/tetris-ai-generator: This program is to seek strong tetris AI with the power of GA

Future AI Tetris Page

 

AIの基本的な考え方

今回作成したAIは「評価関数」を用いています

計算手順は以下の感じです

  1. ブロックを置くことができる場所を全て探す
  2. 1で見つけた場所全てに対して,ブロックを置いた後の状態を複数の観点から評価する
  3. 最も評価の合計点が高い場所が,「置くべき場所」

 

まぁ凄く単純です.単純ですが4次元にしたことでいくつか問題が浮上しました.

 

1.ブロックを置くことができる場所を全て探す

コンピュータの計算速度を利用して,全てのパターンをシミュレートします.

そのためには何パターン置くことができるか調べなくてはいけません.

 

ブロックの置く場所は「移動量」「回転角度」で決定します.

 

移動量は非常にシンプルです.フィールドサイズが「5×5×5×10」で,10は落下にあたるので,それ以外の「5×5×5」=125通りが上限です.当然,ブロックの形によってこれより少なくなることもあります.

 

ところが回転は,回転軸が6つと書いたのですが,回転順序が関わってきます.

例として,6つの回転軸をA~Fとすると,Aで90°→Bで90°回した形と,Bで90°→Aで90°回した形は同じになるとは限りません.これは行列の積が順番を変えると結果が変わるのと同じですね.

 

全ての回転後の姿勢を求めるには,(書く回転軸の角度パターン)^(回転軸の個数)×(回転順序の組み合わせ総数)で求められます.

つまり, (4の6乗)×(6の階乗)=2,949,120通りです(絶望

 

これに移動量の上限125を掛けるので......1手ごとにシミュレートすべきパターン総数は

 

368,640,000 通り(最大)

 

になります。無理です.計算しきれませんでした()

 

という訳で,大幅な妥協をすることにしました.

移動を妥協したら特定のマスにブロック置けなくなるので,こっちはスルーで,回転パターンを大幅に制限しました.

「6つの回転軸を好きな順番で回す」→「ある決められた3つの回転軸を指定した順番で回す」へと変更しました.

4次元のパズルが活かせていないかもしれませんが...やむを得ずそうしました.

これで2,949,120通り存在した回転パターンは64通りまで減りました(少なっ

 

移動と合わせても合計で,最大8,000パターンです

 

 

2.1で見つけた場所全てに対して,ブロックを置いた後の状態を複数の観点から評価する

ここが「評価」にあたる部分です.1で8000種類置くべき場所を見つけたので,それら全てを以下の判断基準から評価していきます.

 

  1. 最もブロックで埋まっている段のブロックの数
  2. 消した段の数
  3. Z(落下)座標が上から4マス以内に存在するブロックの数
  4. ホールの数
  5. 落下位置のZ座標
  6. 最大高度

 

まあこのぐらいにしました.これらに対して,「重み」をつけることで,AIの性格を表現することができるようになります.

 

1つずつ説明していきます.

 

1.最もブロックで埋まっている段のブロックの数

4次元テトリスでは1段消すのに125個のブロックが必要です(2次元なら10個)

これを効率よく積んでいくために,最もブロックで埋まっている段を調べて,その数を評価値にします.ブロックを平らに積んで,消すスピードが向上すると考えられます.

 

2.消した段の数

言うまでもないですね.ブロックを消すことがこのゲームのメインなので.

ここを,4段消せるとき以外は評価を低めに設定したりすると,4段消し(テトリス)を決めやすいAIをつくったりすることができます.

 

3.Z(落下)座標が上かrあ4マス以内に存在するブロックの数

これは少しわかりづらいですが,ブロックを高く積みすぎると,移動可能な領域が減り,難易度が大幅に向上します.そのため,ある程度高く積むことに対して,負の重みをつけることで可能な限り回避します.

 

4.ホールの数

ブロックの下に空いているマスがあると,その段を消すためには上の段を消さなければいけません.2次元なら10個のブロックで消すことができますが,この4次元テトリスでは125個必要で,非常に負担がかかります.正直言うと一度ホールをつくったら,それを修復するのはほぼ不可能です.そこで,ホールを作ることに対して負の重みをつけて,回避します.

 

5.落下位置のZ座標

1と3があるのでこれは無くてもよかったかもしれません.より平らに積んでもらうために,低いところに置くと評価が高くなるようにしています.

 

6.最大高度

同じく,不要だったかもしれません.これも平らに積むための評価基準です.

 

 

これらの評価を用いて,「最も評価の高い移動場所」を決定します.

 

3.最も評価の合計点が高い場所が,「置くべき場所」

あとは簡単です.2で決めた場所に対してブロックを移動させるだけです.

 

 

おわり

以上,4次元テトリスのルールとAIの作成方法についてのメモ兼説明でした.

良かったらプレイしてみてくださいね

 DLリンク↓

https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip

 

 

 

 

4次元空間でプレイするテトリス「TetrisDim.4」を作りました

ちょっとゲーム作ったので公開します

f:id:wgg00sh:20160514185110p:plain

4次元空間でテトリスをプレイする「TetrisDim.4」というゲームです

Dxライブラリを使用して制作しました

まだ未完成ですが,公開します

ダウンロードはこちら↓

https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip

 

ルール

基本的にはテトリスと同じです

ですが,4次元にするにあたって一部改変されています

描画自体は3Dテトリス複数並べる形式なので,あまり4次元らしさは出ていないかもしれませんが...

移動方向が8方向に

X,Y,Z,W4つの軸があり,そのそれぞれが+-に移動できます

十分に思考できるように,自動落下は存在しません

回転が6種類

4次元空間で回転を行う場合,二つの軸からなる平面での回転は全部で6種類存在するので,6種類(逆回転を含めると12)の回転が行えます

落下するブロックの種類が変更

4次元空間内で4つ繋がった形状のブロックが落下してきます

総数は7個と,従来の2次元テトリスと同一ですが,形状が変わっています

 

 

自動プレイモードもあります

恐らく初めてプレイする方は操作難易度が高く,まともにプレイできないと思いますので,自動プレイする人工知能を作成してみました

よければ積み込みの参考にしてみてください(参考にならないかも

 

注意事項

 ・Windows用です

ゲームパッドはXInput形式のみ対応しています

・画面サイズ:1600×900 今後変更可能にする予定です

 

一応,ソースコードも公開しています(多分かなり汚い

https://bitbucket.org/WGGSH/tetrisdim4/src

 

よければ,プレイしてみてください!

「量産ロケット」を遊んだ感想とか

なんかまたスマホゲームの記事です.

 

「量産ロケット!~やはり宇宙は甘くない~」っていうアプリが面白かったので,ちょっと感想書きます.

アプリのシェアばっかりしてますが,別に怪しい目的があってこういう事やってるわけでもなく,単純に自分が気に入ったゲームを広めたいってだけなので^^

このゲーム自体は去年の12月末ごろにプレイし始めて,TA含めて3週間弱はハマってたかな?

この記事を書いてる今はプレイしてた当時から結構経ってます.

 

----以下宣伝----

Twitterで#MPRocketで検索するとスクショとか結構見られると思います

#MPRocket - Twitter検索

IOS

 Android

play.google.com

----------------

 

概要

ロケットを操作してゴールを目指すアクションゲームです.

画面の2か所をタップするだけの非常に簡単な操作のゲームです.

ステージ数も結構多くて(100ちょっと)楽しめました.

 

グラフィックとか

このゲーム,グラフィックがとても綺麗です.

無料ゲームとかって,軽く遊んでなんか操作し辛かったり,UIが見辛かったりすると内容が良くてもそれだけでプレイしなくなることも多いのですが,このゲームは非常に操作しやすくて,アニメーションなどの動きが丁寧に作られてます.

 

作者様が重視して作られたようで,(僕としては)非常にプレイしてて楽しかったです.

というよりも,ゲーム制作のテクニックとして非常に参考になりました.(Unityの勉強しなきゃ...)

 

難易度

僕はアクションゲームはそこまで得意な方ではないのですが,ちょっと難しいかなー?と感じました.

ロケットの操作に慣れるまではすぐ近くにあるゴールに辿り着くのも苦労しましたw

後半になると当然ステージの難易度も上がるわけですが,自分のテクニックも併せて上がるので,「ステージ○○がずっとクリアできないっ!怒」みたいなことにはなりませんでした.まぁ各ステージ結構な回数をこなしたのですが...

 

タイムアタック

f:id:wgg00sh:20160505173914p:plain

今の成績です

確かTotal RankがやっとSになったってぐらいだったかな?

各ランクの個数で見ると

S...83

A...13

B...6

C...7

です

オールS目指したいですねー

 

 

こんな感じかなー

楽しかったので良ければプレイしてみてください