KMC活動ブログ

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

KMC部員がobniz記事を書いたようです。

先日株式会社obniz (オブナイズ)が主催する『obniz IoT コンテスト 2021』が開催されました。 elchika.com このコンテストに参加すると obniz Board 1Y を手に入れられるという情報が部内で拡散し、KMCからも6人が参加することになりました。以下では各々が投稿した記事の概要をまとめてみたいと思います。

KMCid:hiroakiの作品

elchika.com 時間になったら開くカーテンを作ったようですね。既設のカーテンレールにベルトを取り付けてうまく活用しています。モーターを駆動するモータードライバーが焼けるのではないかと心配されていましたが、トラブルなく順調に動作しているようです。本人曰く、このおかげで朝起きられるようになったとのことで、「早起きの会」を主宰されていました。

KMCid:polarisの作品

elchika.com 抵抗歪みゲージという力を検出するセンサをベッドに組み込んで、起床・就寝を mastodon に報告してくれるサービスを作ったようです。ほんの僅かな抵抗の変化を検知するため、ホイーストンブリッジを応用したそうです。polaris さんは現在電子工作勉強会を主催されていて、多数の部員が聴講しています。講座終了後には洗脳された部員たちが組み込み Rust で遊ぶ姿がきっと見られることでしょう。

KMCid:tak0kadaの作品

elchika.com ドットマトリックス LED をダイナミック点灯させて文字を表示しようとしたようです。遅延があって上手くいかなかったそうです。io.animationという api はネットワーク経由であっても高速・正確な IO の操作が行なえるそうで、それを使えば良かったかもしれません。投稿の締め切りを守るのも良いかと思われます。

KMCid:nanaの作品

elchika.com MH-Z19BというCO2センサを使って室内のCO2濃度を測定したようです。CO2センサは今だと秋月電子でMH-Z19Cが販売されていて気軽に購入できますが、ほんの少し前まではもっと高額な部品しか流通しておらず、MH-Z19Bも海外から調達する人が多かったようです。長時間自宅で活動せざるを得ない昨今、部屋の CO2 濃度が高いかモニタ出来ると良さそうです。

KMCid:strelkaの作品

elchika.com SHT31-Dという湿度センサを利用した自作の湿度測定モジュールを、格安のUSB加湿器に組み合わせてフィードバック制御したようです。USB端子の1ピンと4ピンが電源用のピンなのを利用してうまく工作されています。今回多数の部員がこのコンテストに参加したのは strelka さんが部内で情報を共有してくれたのがきっかけでした。strelkaさんはこの記事以外にもモーターやマイクロ波レーダーを利用した記事を紹介されているのでご覧ください。

KMCid:zekeの作品

elchika.com 最後に私の作品を紹介します。Slackのwebhooksを利用して、KMC部員なら誰でも自分の部屋のエアコンを操作できるようにしました。半分ネタです。JavaScriptを書くのは初めてだったので結構苦労しました。部員用Slack上でサービスを開発すると、他の部員がサービスに対して破壊的な入力を試みてくるため、デバッグに便利です。

KMCについて

KMCでは電子工作に興味がある部員を募集しています。興味のある方は是非下のリンクからどうぞ!! www.kmc.gr.jp

競技プログラミング練習会2021 Normal 第1回-第5回

ご挨拶

初めまして、競技プログラミング練習会2021 Normalの担当(の1人)のid:Flkanjin(KMCID: flkanjin)と申します。つい先日までGWでしたが、いかがお過ごしでしょうか? 昨年の前期はずっと自宅で授業で、今年は最初の2週間は対面授業も実施されましたが、殆どの科目が京大内の対応レベルの引き上げによりリモート授業となりました。私はというと、実験科目があるので、毎週大学に行っているのですが、定期を買った方が良いのか、ICチャージさせた方が良いのか...という感じで迷っています。

KMCの先輩と話しているときに「このブログ更新してみない?(意訳)」と言われましたので、活動ブログとして、今年のこれまでの競プロ練習会や、そもそも競プロとは何ぞやについて書きたいなと思います。

競技プログラミングって何?

競技プログラミングとは与えられた問題について、それを解くための適切なアルゴリズムを速く正確に書くことを競う競技です。競技プログラミングという名前は少し長いのでよく競プロと呼ばれます。数学やパズルのような要素があり、そのようなものが好きな競プロerは多いですが、そうでない競プロerもたくさんいます。

また、数学などの試験のような形式だけでなく、長時間(ものによっては1ヶ月など)でおこなうマラソンという形式のコンテストも存在します。こちらは与えられた問題に対してなるべく良い解をとれるようなぷトグラムを作り、その点数を競うものです。こちらの記事のゲームAI系と近いものがあります。

KMCでの競技プログラミング練習会について

KMCでは競プロ練習会としてNormal(未経験、初心者向け)とAdvanced(上級者向け)の二種類が開催されています。

Normalでは主に初めての方向けにC++というプログラミング言語アルゴリズムの基礎についての講座を行い、その内容に関する(バーチャル)コンテストを行います。初心者向けというのもあって質問対応なども丁寧に行っているつもりです。Advancedの方では毎回コンテストを行い、いくつかの解では講座も行っているようです。

今年のこれまでの軌跡(Normal)

去年から続くコロナ禍のため、例年の通りの部室での活動ができないため、Discordを用いてオンラインで行っています。今年は講座の担当を奇数回は私(KMCID:flkanjin)が、偶数回はKMCID:replica君が担当しています。コンテストは基本的にはAtCoderの過去問やAOJに存在する問題を用いて開催しています。

第1回(2021/04/09(金)) 担当: flkanjin

初回であったため、簡単に競プロとは何かということを話し、いくつかのオンラインコンパイラを紹介、自前での環境構築について少し触れたのち、C++の基礎(コメント、変数、入出力、if, while, for)についての講座を行いました。 コンテストでは今回の講座の内容だけで解くことのできるAからD問題(ただし、CDは難易度高め)と経験者向けのEからK問題を出題しました。難易度的には後半の問題は特に難しいものを集めていたので、解ける人いるだろうか、みたいにドキドキしていていたところはあります。 f:id:Flkanjin:20210509155401p:plain

第2回(2021/04/16(金)) 担当: replica

2回目は1回目に引き続きC++の基礎(型についての詳しい説明、配列(vector)、関数(再帰も))についてやったのち、競プロにおいて重要な概念である計算量と一番単純なアルゴリズムである貪欲法について学びました。コンテストは少し難易度が高めでABでWA(不正解)などを出している人が結構いたなという印象でした(AもBもペナルティなしで正解した人が1人ずつでした)。この回からコンテストの内容は講座の内容にリンクしたものになっています。

第3回(2021/04/23(金)) 担当: flkanjin

この回のテーマは累積和で、派生してimos法や尺取り法も取り扱いました。今回からのアルゴリズムは基本的に高速化するためのもので、コンテストも素直な実装では間に合わないという問題が多くなっていますが、殆どの参加者か解け形るようで安心しました。

第4回(2021/04/30(金)) 担当: replica

ソートや二分探索、そしてSTLのデータ構造についての講座でした。pairのソートについて少し複雑だったかもしれません。二分探索について慣れていってほしいなと感じました。

第5回(2021/05/07(金)) 担当: flkanjin

今回は全探索回でした。線形、順列、DFS、BFS、bit全探索(とそれに必要なbit演算)についても勉強しました。ちょっと講座部分が長かったかもしれないです。線形探索や順列探索は単純なものでしたがその他のものは少し複雑でとっつきにくいものだったかもしれません。分かり易い説明を考えないとなぁと感じさせられました。

感想

人に何かを教えるというのは難しいなぁ、と感じさせられます。特にリモートで行っていると顔が見えなかったり、どこで困っているのかが見えにくく、早く部室でできるようになってほしいなと思います。

6回目やります

翌週の05/14(金)に競プロ練習会Normal第6回を行います。この記事を読んで興味を持った方やこの春に何かしら新しいことを始めたいと思った方など、奮ってご参加ください。

参加方法

KMCのTwitterメールまでご連絡ください。

KMC自体の宣伝

KMCではパソコンでゲームを作ったり、音楽を書いたり、お絵描きしたり、競プロをしたりしています。興味のある方は是非下のリンクからどうぞ!! www.kmc.gr.jp

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

こんにちは!!!!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