KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

第二回おかし会を開催しました

こんにちは!!!!KMC4回生のkmcid:bu4です。

これはKMC Advent Calendar 2020の3日目の記事になります。昨日の記事はkmcid:prime(id:PrimeNumber)さんによる「フラグメントシェーダを用いて、VRChatのワールドで計算機を作る」でした。昨日は技術記事でしたが、今日はDTM?関連のお話となります。

adventar.org

primenumber.hatenadiary.jp

第二回おかし会を開催しました

第二回おかし会を開催しました。

おかし会ってなんやねんってお話ですが、KMCのDTMerたちが集って歌詞についてあーだこーだ言ったり言わなかったりする会のことです。第二回とありますが実は第一回は昨年度に行っていました。

第二回はオンラインでの実施となりました。

KMCの歌もの

最近KMCのDTMerでは歌ものがアツいです。それはもう。今まで書いていなかった人でも歌ものを書き連ねております。

さて、歌ものを書く際に必須となる作詞スキル。今までKMCではあまり歌ものの動きはそこまで活発でなかったので作詞の知見が枯渇していました。KMCのDTMがさらに幅広くなっていっているのが感じられます。嬉しいね。

内容

今回は参加者それぞれに歌詞についてお話をしていただきました。

例えば、kmcid:naka6さんは、歌詞だけでなくオケとも併せて世界観を作ることや、「テーマ」の重要性等々のお話を語ってくれました。

他にも、各自のメイキングを交えながら、情報量の調節、抽象と具体の使い分け、etc…、様々な知見や意見を聞くことができました。話せば話すほど作詞の難しさが感じられます。

これからの制作に活かしていきたいとモチベーションも上がりまくりです。みなさんも音楽を作っていきましょう。

f:id:kmc-log:20201203001734p:plain
naka6さんのスライドより抜粋

宣伝

KMC Advent Calendar 2020

明日のアドベントカレンダーはkmcid:nosさんによる記事になります。

adventar.org

KMC お絵描き Advent Calendar 2020

また、今年度も並行してお絵描きAdventCalendarが行われています。こちらもご覧ください。

adventar.org

KMC

そして、KMCでは作詞だけでなく、作曲、競技プログラミングwebサービス製作、お絵描き、ゲーム製作等も行っています!!!!!PCを使って何かしたい人々を募集しております。

www.kmc.gr.jp

KMC Slackのカスタム絵文字が3000個になりました!!

こんにちは。今年はコロナウイルス対策でリモートでのコミュニケーションを取る機会が多いですね(そうでない人もいるかもしれません)。

絵文字は言外でのコミュニケーション目的である場合とそうでない場合にとても便利です。KMCのチャンネルにはとてもたくさんのカスタム絵文字が登録されていて、複雑な、あるいは簡単な会話に日々役立てられています。この文章はつい昨日3000個目のカスタム絵文字が登録されたお祝いのためのものです。おめでとうございます。

記念すべき3000個目の絵文字は:btrfs:でした。

3000個目の絵文字として:btrfs:が登録されたときのスクリーンショット

Btrfs はとても使いやすくて高機能なファイルシステム(出典不要)で、部内にも多数(要出典)の愛好者が在籍していています。「今時Btrfsしか使っていない」、「もちろんBtrfsにいつもしている」、「Btrfsを使うのは何もしていないの一つ」など、とても良いファイルシステムとして推薦する声が確認されています。これを書いている人間もありがたく便利に使っています。Fedoraでも次のバージョン33からデフォルトになる*1そうですし、さらに気軽に使えるようになっていく未来が待ち遠しいですね。

ちなみに、2998個目の絵文字は「2998個目」でした。これが使われる日は来るのでしょうか…なお、2014年にサービス利用開始してから5年目の昨年1月に2000個目が登録されたそうで、この日から今日までは概ね1.6 個/日の速さで新たな絵文字が登録され続けているようです。

2998番目の絵文字として「2998個目」が登録されたときのスクリーンショット

KMC では有意義な絵文字あるいは有意義でない絵文字を登録したり、Btrfs を利用したり、それ以外のファイルシステムを利用する部員を募集しています。詳細は下記Webページを御覧下さい。

www.kmc.gr.jp

第65回コーディング大海を行いました

こんにちは、今回のポセイドン*1を担当させていただいたpolarisです。今日実施した第65回コーディング大海の実施結果を書こうと思います。

参加者の進捗報告

polaris: 「自分のサーバの引っ越し(サーバ移管)作業がだいたい終わった」

inonoa, ten: 「Unity1週間ゲームジャムの進捗をした」

tron: 「載っていたコード進行を見ながら曲の耳コピをした」

tak0kada: 「AdaptiveCode9-11章くらい読んだ」

実施した感想

今回は部室が利用できない中での開催となったので夕方に進捗報告をするだけのイベントになってしまいましたが、前回(ブログには載っていない第64回)よりもたくさんの部員が参加し、各々良い感じの進捗が出せたようです。夏季休暇は始まったばかりですが最初のイベントの一つとしてまずまずのスタートを切れたのではないかと思います。夏季休暇中はさらに内容の濃いイベントが部内で開催されたら良いなと思います。

*1:コーディング大海の主催者のこと

「KMC Music Collection Vol.3」リリースのお知らせ

皆さんごきげんよう、KMC5回生のKMCid:tronです。

本日5月24日よりBoothにて音楽作品集「KMC Music Collection Vol.3」の販売を開始しました。

kmc-jp.booth.pm

こちらは試聴動画です。

youtu.be

収録曲には歌詞がついているものもあります。歌詞はBoothの商品画像をご覧ください。

KMCM

KMCではパソコンで何かしたい人々を募集しています!!

www.kmc.gr.jp

blog.kmc.gr.jp

ゲームAI作ってみた

こんにちは id:zekehamp (KMCid:zeke)です。この記事はKMCブログリレーの一環で書かれたものです。

blog.kmc.gr.jp

f:id:kmc-log:20200513030430p:plain
Tron Game

皆さん、ゲームはお好きですか?自分は好きです。 Hoi4というゲームが好きでよくやってます。

そんなことはどうでもよくて、今回紹介したいのはゲームAIです。

なにかAIという言葉を聞くと難しそうに聞こえるかもしれませんが、プログラミング言語の一つや二つを触ったことがあるならば、思ったより簡単に作ることができます。競プロなどをやっている人向けですが、競プロのマラソンに近いものがあると感じました。明確な解法があるというよりかは、いくつかの手法を組み合わせて徐々に改善していくという感じです。僕自身、いくつかの手法を試すことで

f:id:zekehamp:20200503232002p:plain
現在の順位 1212/5762 (2020/5/3)

上位1/4ぐらいの成績をとることができました。 この記事では、このゲームに対しての紹介と簡単な攻略を書いていきたいと思います。

Tron Game

今回ご紹介するのはCodinGameが提供しているTron battleです。CodinGameは初心者向けから上級者向けまでいろいろなプログラミング教材を提供しており、Tron Gameはこの教材の一つとなります。またC言語を始めとしてPython,Rustなどさまざまな言語に対応しているのもよいです。 簡単な登録を済ませれば、任意のゲームAIと試合を組ませることができたり、Submitすることで自動的に試合が組まれその成績によってランク付けがなされたりします。

今回紹介するゲームであるTron Battle のルールを説明していきます。

  • フィールドは20×30でプレイヤー数は2~4人
  • 各プレイヤーは手番になればフィールド上を動き回るが、今いるところから縦横4方向にしか進めない
  • プレイヤーは自他プレイヤーがすでに通ったところに進むことはできない
  • 進める場所がなくなったら負け、負けたプレイヤーの通った場所は再び通ることができる
  • 最後まで残っていたら勝ち
  • 各ターン100ms以内に次の手をうつこと

ルール自体はとてもシンプルです。

参考までに入出力は

入力
N P
X0 Y0 X1 Y1
X0 Y0 X1 Y1
…
N-プレイヤー数
P-自分のプレイヤー番号
以下各プレイヤーの情報が続く
(X0,Y0)初期座標
(X1,Y1)今いる座標
出力
UP DOWN LEFT RIGHT のどれか

です。

競プロでいうインタラクティブ問題ですね。

それじゃ早速動くものを作ってみよう!

兎にも角にも、とりあえず動かしてみましょう!

まず最初のコードとしてこんなものがあります。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    // game loop
    while (1) {
        int N;  // total number of players (2 to 4).
        int P;  // your player number (0 to 3).
        cin >> N >> P;
        vector<int> X0(4),Y0(4),X1(4),Y1(4);
        for (int i = 0; i < N; i++) {
            cin >> X0[i] >> Y0[i] >> X1[i] >> Y1[i];//各プレイヤー情報
        }
        cout<<"LEFT"<<endl;//ただ左に進むだけ
    }
}

ただただ左に進むだけ…!こんなコードでもちゃんと動きます。ただめちゃくちゃ弱いですが。

まず気づくのが自殺してしまうことですね。

壁にぶつかったり、プレイヤーがすでに通った場所を通ったり…

とりあえず自殺しないコードを

int main()
{
    vector<vector<bool>> have(20,vector<bool>(30,true));
    while (1) {
        int N; 
        int P; 
        cin >> N >> P;
        vector<int> X0(4),Y0(4),X1(4),Y1(4);
        for (int i = 0; i < N; i++) {
            cin >> X0[i] >> Y0[i] >> X1[i] >> Y1[i];
            have[Y1[i]][X1[i]]=false;
        }
        int dx[]={0,-1,0,1};
        int dy[]={1,0,-1,0};
        string order[]={"DOWN","LEFT","UP","RIGHT"};
        for(int i=0;i<4;i++){
            int nowx=X1[P]+dx[i];
            int nowy=Y1[P]+dy[i];
            if(nowx>=0&&nowx<30&&nowy>=0&&nowy<20&&have[nowy][nowx]){
                cout<<order[i]<<endl;
                break;
            }
        }
    }
}

書きました。

これで自殺しなくなりますね!

f:id:zekehamp:20200503234859p:plain
自殺しないゲームAI

ちょっと先読みをしよう!

これだと以下のような場合でよく負けてしまいます。

f:id:zekehamp:20200504190716j:plain
よくある負け方
そこで

このようにすることで、袋小路に突っ込むことがなくなります!

f:id:zekehamp:20200504190759j:plain
幅優先探索を使う
残り手数が一番多い方向へ進めばよいです。

残り手数を数え上げるには、幅優先探索(BFS)や深さ優先探索(DFS)を実装してやります。この二つは所謂、全探索アルゴリズムでそこまで難しくはありません。

int bfs(int y, int x, vector<vector<bool>>& dis,
                   vector<vector<int>>& inter) {  //全探索用BFS中身
//開始座標ともう行ったかどうかの配列と開始座標からの距離を入れる配列を渡す
    int tempcnt = 0;
    dis[y][x] = false;
    inter[y][x] = 0;
    queue<vector<int>> q;
    q.push({y, x, 0});//開始地点を入れてあげます
    int path_cnt = 0;
    while (!q.empty()) {
        vector<int> temp = q.front();
        q.pop();
        path_cnt++;
        int nowy = temp[0];
        int nowx = temp[1];
        int depth = temp[2];
        inter[nowy][nowx] = depth;
        tempcnt ++;
        for (int j = 0; j < 4; j++) {
            int disty = nowy + dy[j];
            int distx = nowx + dx[j];
            if (disty >= 0 && disty < 20 && distx >= 0 && distx < 30) {
                if (dis[disty][distx]) {
                    dis[disty][distx] = false;
                    q.push({disty, distx, depth + 1});
                }
            }
        }
    }
    return tempcnt;
}

このようにBFS関数を実装してあげます。

するとこれだけでもかなり順位を伸ばすことができました。

さらに改善する

正直ここまで実装した後、いろんな手法を試したのですが、実行制限時間に間に合わなかったり、それほど効果がみられなかったりと苦戦を強いられました。

結果いろいろ小細工をすることで少々記録を伸ばすことができたので下に方法を記します

死んだプレイヤーの通ったところを再び通れるようにする

ルールにある通り死んだプレイヤーの通ったところは通れるようにします。だれがどこを通ったかを記録しておけば容易に実装できるはずです。

ちなみにSilver League以上だとプレイヤー数が3人以上になります。

敵プレイヤーとフィールドを共有しているかどうか

もし敵とさえぎられていたら、余計なことはせず最大限今いけるところを塗るようにするのがよさそうです。

端っこは通らないようにする

対戦記録を見ると端っこで押しつぶされて負けいるのがよくあったので…

逆に相手をつぶしてみる

f:id:zekehamp:20200504193728j:plain
敵を殺す

上のような状態だと、多少自分の行き場所が減っても相手を即死させられるほうが良い手と言えるでしょう。

そこで2手先ぐらい進めてやることで相手の行き場所が劇的に少なくなった手を優先的に取るようにします。

具体的には自分の手を2手先ほど進めながら、自分と敵プレイヤーの残り手数を数え上げ、もともとの手数との比率を計算してあげることにより、相手の行き場所をなくすような手を取ることができます。

これを実装すると順位が600ほど上がりました

やばそうなところにはいかないようにする

下のような場合はどうでしょう?

f:id:zekehamp:20200504194304j:plain
やばそうな手

BFSしても残り手数は上に行っても左に行っても変わりませんが、明らかに左に行ったほうが敵につぶされる可能性が高そうです。

そこで、50手(この値は適当です)以内で行けるマスを数えてあげて、そのマスの数が多いほうを選んであげるということを実装しました。

すると順位が200~400ほど上がったりしました。

こんな感じで

実装を進めていくとSilver Leagueの186位につけることができました!

もっと順位をあげるためには?

こっちが知りたいぐらいですが、コンテストのフォーラムを眺めていると以下のような手法が有効らしいです。

これらをうまいこと実装してあげたら上のリーグへと行けそうです

感想

自分自身ゲームAIなどは作ったことはなかったのですが、いろんな知見を得ることができました。 Tron Gameは単純なルールのゲームなのに、すごく奥が深いです。

また、このゲームAIはヴィジュアル化されているので実装したアルゴリズムの効果が分かりやすかったり、対戦要素があるので知っている人とやることもできるので、すごく楽しいと思います。

最後に

ゲームAI楽しいよ!って話がしたかっただけです。自分自身プログラミングを始めて1年ぐらいということもあり、かなり拙いコードになっているので後半はコードをお見せすることができませんでした… ハードルは低いので、気になった方は気軽に始めてみてはいかがでしょうか?

ところで今度こんなイベントがあります!現在進行形で開催中です!自分はzeke8080で参戦しています。個人のほかに大学単位で順位なども出るそうです。是非参加してみませんか?対戦お待ちしています。

KMCM

KMCではパソコンで何かしたい人々を募集しています!!

www.kmc.gr.jp

blog.kmc.gr.jp

Google のロケーション履歴をエラー除きつつ GPX にする

こんにちは id:nonylene です。この記事はKMCブログリレーの一環で書かれたものです。

blog.kmc.gr.jp

ロケーション履歴を GIS ソフトで見よう

Google のロケーション履歴は便利ですが、平均速度や獲得標高といった細かい値が見たくなります、なりますよね?

実は、ロケーション履歴のエクスポート機能を使うと、数十秒間隔で記録された自分の経緯度・高度を取得することが出来ます。それを使ってお好みの GIS ソフトウェアで見れるようにする話です。

エクスポート

https://takeout.google.com/ から「ロケーション履歴」を選択してエクスポートします。このとき、フォーマットは KML にします*1

KML から GPX に変換する

GPX のほうが色んなソフトで見れる上、ライブラリも揃っているので GPX に変換します。

GPSBabel という GPS 関係の様々なデータを変換するソフトウェアを使います。GUI もあるようですが、今回は CLI でやります。

$ sudo apt install gpsbabel
$ gpsbabel -t -i kml -f location.kml -x "track,start=201909171200,stop=201909171900" -o gpx -F location.gpx

-x で様々なフィルターができます。今回は日付(UTC)を指定して抽出しています。詳細は GPSBabel development:Chapter 4. Data Filters を参照してください。

ちなみに、フィルターの設定は入力パスと出力パスの間に挟まないとフィルタが動かないので気をつけてください。

エラーを取り除く

出力された GPX を見ると分かるのですが、たまに精度が悪いデータがあります。

Google Maps で青い円が大きくなるあのタイミングです。

これをそのまま GSI ソフトに入れてしまうと、速度が突然 13000km/h になったり獲得標高が 100m/s になってしまいます。

f:id:nonylene:20200511184918p:plain
ある日の淡路島のログ。速度別に色分けしている。
地理院タイルにGPSログを追記して作成。

悲しいので適当にフィルタリングします。簡単にフィルタリングする手段としては

  • 前回の点から一定以上の距離になっていれば除く
  • 前回の点から一定以上の速度になっていれば除く
  • 計測時のメタデータを用いる

といったものが考えられます。

このうち距離と一部のメタデータHDOP))については GPSbabel で省けるのですが、

  • Google ロケーション履歴は取得間隔がマチマチなので正常でも距離が大きく飛ぶことがある
  • Google ロケーション履歴には GPSbabel で省けるメタデータ(HDOP)が入っていない*2

といった理由により今回は使わずに、速度によってフィルタリングするスクリプトを自分で書きました。

スクリプト

github.com

normalizer という名前は、取得間隔がマチマチなのを適当に補間することでプレイバックを分かりやすくしようと思っていたことに由来します*3。結局カシミール3DGoogle Earth では取得間隔がバラバラでもいい感じにプレイバックしてくれることが分かったので、フィルタリングするだけになりました。

gpxpy というライブラリがとても強力だったので特に難しいことは無かったです。

結果

ということで、先程の淡路島のログに対してフィルタリングをかけて、200km/h を超える点を省きます。

$ poetry run python3 main.py -i location.gpx -o location_filtered.gpx -s 200

f:id:nonylene:20200511192007p:plain
地理院タイルにGPSログを追記して作成。

全く別の地点に飛んでいたところが綺麗に無くなりました。最高です。

KMCM

KMCではパソコンで何かしたい人々を募集しています!!

www.kmc.gr.jp

blog.kmc.gr.jp

*1:JSON を選ぶと GeoJSON ではなく独自の形式で降ってくる

*2:JSON で取得した場合 accuracy におおよその精度 (m) が入っているのだけど、これは信用できるんだろうか?

*3:というがそれがメインの機能となる予定だった

Lambdaでもnginx_omniauth_adapterを使いたい!

こんにちは

菜々(id:nna774)です。 たまたま趣味のコードを書き終えたら、KMCブログリレーが行なわれていたので、にぎやかしに書きます。

blog.kmc.gr.jp

みなさんはnginx_omniauth_adapterを使っていますか? KMCではinside.kmc.gr.jpの認証のバックエンドに使っているので、部員のみなさんは間接的に使っています。 雑にnginxで認証したい みたいな時に便利です。 個人的にも使っています。 みなさんもきっと使っていることでしょう*1

みなさんはAWS Lambdaは使っていますか? 私は便利cgi-binとして1枚のlambdaをよく書きます。

ある日

Lambda, API Gatewayのdocumentを読んでいると、contextをうまく扱えばGoでhttp Handlerを書けば動くものができるのではないか という気持ちになり、書いてみようかと思ったのですが、書く前にGoogle検索をしたところ、akrylysov/algnhsaが既に存在していました。 よさそうです。

これを使ってappを書いてみるのですが、ある所で認証機能が欲しくなってきます。 API Gatewayにはオーソライザという機能があります。 その中の1種類としてLambdaオーソライザというものがあり、一言で言うとLambdaの返り値で認証成功か失敗を返せる機能です。

認証はいつも使っているnginx_omniauth_adapterの機構に乗せたいという気持ちになりました。

つまり、nginx_omniauth_adapterに対応した挙動をするLambdaオーソライザを書けば良いのでは という気がしてきます。

というわけでできたのがこちらです。

github.com

くわしく

nginxの行うinternal requestに相当することをしてやれば良いだけです。 以下は設定例を見ながら読んでください。

auth_request /_auth/challenge 相当のことがAPI GatewayのAuthorizersの働きなので、auth_adapter/testへリクエストを送り、認証が成功した場合はユーザの情報を返し、失敗した際はerror_page 401 = /_auth/initiate;相当のレスポンスを返します。 つまり、認証ページにリダイレクトします。

GatewayResponsesをセットしますが、ACCESS_DENIEDな時は普通にやればいいのですが、API Gatewayくん、AuthorizersIdentityHeaders Cookieの設定を入れている時にcookieのついていないリクエストが飛んでくるとLambda オーサライザまでリクエストが渡らずに401が返るような挙動をしている気がするんですが?? これどうなってるんですか?? 詳しい人教えてください!!!

気をとりなおして/_auth/callback ですが、これはinternal requestではないので、認証を受ける側のappに生やす必要があります。これはほとんど定形なので、用意しておきました。

というわけでめでたくLambdaでnginx_omniauth_adapterの認証を使えるようになりました! 詳しく知りたい人はレポジトリのREADMEやソースコードを読んでください。

で、正気?

動いたけど、正気か……?

GCPのApp Engineに出してIAPとかで認証したほうがいいと思います*2

でも書けそうな気がしたので書いてみました。是非御活用ください。

いかがでしたか?

最後まで見てくれてありがとうございます! チャンネル登録高評価、よろしくお願いします! 関連動画も是非!

*1:oauth2-proxyとかのほうが使われてるとこよく見る気もしますが……。

*2:一部だけ認証とかはできないけど……。