daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

FFT

アルゴリズム 物理

FFTについて教わったことをまとめる。

N=2^nとして、
\begin{eqnarray} \tilde{f}(y) = \sum_{x=0}^{N-1}\exp\left(\frac{2\pi xy}{N}i\right) f(x) \end{eqnarray}
(y = 0, 1, \dots N-1)を求める為の方法。

nbviewer.org

FFTによる導関数

物理においてFFTはこういう関数の微分を誤差が小さい方法で求めるときに使ったりする。


x,yを2進数展開したものを
x=\sum_{m=1}^{n} x_m 2^{n-m} =x_1 2^{n-1}+x_2 2^{n-2}+.....+x_n=x_1 x_2....x_n
y=\sum_{m=1}^{n} y_m 2^{n-m}=y_1 2^{n-1}+y_2 2^{n-2}+.....+y_n = y_1 y_2....y_n
のようにして書く記法をとる。
yの2進数展開をひっくり返した数列を Y_mとして書く。
y=\sum_{m=1}^{n} Y_m 2^{m-1}=Y_n Y_{n-1}....Y_1=y_1 y_2.... y_n

今後q 2^{-1}+r 2^{-2}+k 2^{-3}...を 0.qrk...と書くことにする。

2\piの整数倍は指数関数の中で意味はなくなるのでxy/Nの小数部分だけを考える.

\frac{xy}{N}=\frac{(x_1 x_2 ... x_n )(y_1 y_2 ... y_n)}{(2^n)}
=(x_1 x_2 ... x_n)(0.y_1 y_2...y_n)
=(x_1 2^{n-1}+x_2 2^{n-2}+.....+x_n)*(y_1 2^{-1}+y_2 2^{-2}+...+y_n 2^{-n})
=(Integer)+x_1 (0.y_n)+ x_2 (0.y_{n-1}y_n)+...+x_n(0.y_1...y_n)
=(Integer) +x_1(0.Y_1)+x_2(0.Y_1Y_2)+...+x_n(0.Y_n...Y_1)

関数 f(x), \tilde{f}(y)を f(x_1x_2 \dots x_n), \tilde{f}(y_1 y_2 \dots y_n)と書くことにすると、
\tilde{f}(y)は
\tilde{f}(y_1 y_2 \dots y_n) = \nonumber \\ \sum_{x_n=0}^1 e^{2\pi i(x_n\times 0.Y_{n}\dots Y_{1})} \dots \sum_{x_{2}=0}^1 e^{2\pi i(x_{2} \times 0.Y_2 Y_1)} \sum_{x_{1}=0}^1 e^{2\pi i(x_1\times 0.Y_1)} f(x_1 \dots x_n)
と x_mごとに分けて書くことが出来る。
各 x_mについて見ると、 x_mから Y_mへの2点フーリエ変換とみることが出来るので
各桁の2点フーリエ変換を繰り返すことで \tilde{f}(y)は求まる。
x_1について具体的に見ると
f_1(Y_1=0 x_2 \dots x_n) = f(x_1=0 x_2 \dots x_n) + f(x_1=1 x_2 \dots x_n) \\ f_1(Y_1=1 x_2 \dots x_n) = f(x_1=0 x_2 \dots x_n) - f(x_1=1 x_2 \dots x_n)
ここで e^{2\pi i\times (0.y_1)} = e^{\pi i\times y_1} = (-1)^{y_1}を用いた。

x_mについての和は
f_m(Y_1 \dots Y_{m-1} Y_m=0 x_{m+1} \dots x_n) = \\ f_{m-1}(Y_1 \dots Y_{m-1} x_m=0 x_{m+1} \dots x_n) + e^{2\pi i\times (0.0 Y_{m-1}\dots Y_1)} f_{m-1}(Y_1 \dots Y_{m-1} x_m=1 x_{m+1} \dots x_n)\\ f_m(Y_1,\dots Y_{m-1} Y_m=1 x_{m+1} \dots x_n) = \\ f_{m-1}(Y_1 \dots Y_{m-1} x_m=0 x_{m+1} \dots x_n) - e^{2\pi i\times (0.0 Y_{m-1} \dots Y_1)} f_{m-1}(Y_1 \dots Y_{m-1} x_m=1 x_{m+1} \dots x_n)\\

Y_1 \dots Y_{m-1} と x_{m+1} \dots x_nのパターンはたくさんある。

これをn番目まで繰り返すとf_n(Y_1\dots Y_n)が得られ、\tilde{f}(y)は
\tilde{f}(y) = f_n(y_n \dots y_1)
として求まる。

実装としては
y_1 y_2 \dots y_nをひっくり返すところをちゃんとするために
gを
g_m [y_{n-m+1} y_{n-m+2} \dots y_n x_{m+1}\dots x_n] = f_m[Y_1 \dots Y_m x_{m+1} \dots x_n]
とし,
g_m [ y_{n-m+1}=0 y_{n-m+2} \dots y_n x_{m+1} \dots x_n ] = \\ g_{m-1}[ y_{n-m+2} \dots y_n x_{m}=0 x_{m+1} \dots x_n ] + e^{2\pi i\times (0.0y_{n-m+2}\dots y_n)} g_{m-1}[ y_{n-m+2} \dots y_n x_{m}=1 x_{m+1} \dots x_n ] \\ g_m [ y_{n-m+1}=1 y_{n-m+2} \dots y_n x_{m+1} \dots x_n ] = \\ g_{m-1}[ y_{n-m+2} \dots y_n x_{m}=0 x_{m+1} \dots x_n ] - e^{2\pi i\times (0.0y_{n-m+2}\dots y_n)} g_{m-1}[ y_{n-m+2} \dots y_n x_{m}=1 x_{m+1} \dots x_n ]
と変換を繰り返す。
y_{n-m+2} \dots y_nと x_{m+1} \dots x_nをそれぞれ2進数とみなして
y_t= y_{n-m+2} \dots y_n
x_t= x_{m+1} \dots x_n
と書くことにすると、
g_m[y_t2^{n-m} + x_t ] = g_{m-1}[y_t 2^{n-m+1} + x_t] + e^{\frac{y_t}{2^{m-1}}\pi i} g_{m-1}[y_t 2^{n-m+1} + 2^{n-m} + x_t]\\ g_m[2^{n-1} + y_t2^{n-m} + x_t] = g_{m-1}[y_t 2^{n-m+1} + x_t] - e^{\frac{y_t}{2^{m-1}}\pi i} g_{m-1}[y_t 2^{n-m+1} + 2^{n-m} + x_t]
この変換を 0\le xt \le 2^{n-m}-1, 0\le yt \le 2^{m-1}-1の全ての値について計算すれば良い。

atc001.contest.atcoder.jp
一応ACとれたのであってるはず。微妙だが。

        #include <vector> 
        #include <list> 
        #include <map>
        #include <set>
        #include <deque>
        #include <stack>
        #include <bitset>
        #include <algorithm>
        #include <functional>
        #include <numeric>
        #include <utility>
        #include <sstream>
        #include <iostream>
        #include <iomanip>
        #include <cstdio>
        #include <cmath>
        #include <cstdlib>
        #include <cctype>
        #include <string>
        #include <cstring>
        #include <ctime>
        #include <queue>
        #include <complex>
        using namespace std;
        
        //conversion
        //------------------------------------------
        inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
        template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
        
        //math
        //-------------------------------------------
        template<class T> inline T sqr(T x) { return x * x; }
        
        //typedef
        //------------------------------------------
        typedef vector<int> VI;
        typedef vector<VI> VVI;
        typedef vector<string> VS;
        typedef pair<int, int> PII;
        typedef long long LL;
        
        //container util
        //------------------------------------------
        #define ALL(a)  (a).begin(),(a).end()
        #define RALL(a) (a).rbegin(), (a).rend()
        #define PB push_back
        #define MP make_pair
        #define SZ(a) int((a).size())
        #define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
        #define EXIST(s,e) ((s).find(e)!=(s).end())
        #define SORT(c) sort((c).begin(),(c).end())
        
        //repetition
        //------------------------------------------
        #define FOR(i,a,b) for(int i=(a);i<(b);++i)
        #define REP(i,n)  FOR(i,0,n)
        
        //constant
        //--------------------------------------------
        const double EPS = 1e-10;
        const double PI = acos(-1.0);
        
        //clear memory
        #define CLR(a) memset((a), 0 ,sizeof(a))
        
        //debug
        #define dump(x)  cerr << #x << '=' << (x) << endl;
        #define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;
        
        typedef complex<double> Comp;
        const Comp img = Comp(0, 1);
        
        void FFT(vector<Comp>& f, int n) {
            int N = 1 << n;
            vector<Comp> g(N);
         
            for (int m = 1; m <= n; m++) {//どこのbitに着目しているか　m番目のbitに着目している
                int max_xt = (1 << (n - m)) - 1;//これはxtの値の取りうる範囲 2^{n-m}
                int max_yt = (1 << (m - 1)) - 1;//これはytの値の取りうる範囲 2^{m-1}
         
                int start_yt = (1 << (n - m + 1));
         
                Comp a, b;
                //xt ytの取りうるすべての値を列挙
                for (int xt = 0; xt <= max_xt; xt++)for (int yt = 0; yt <= max_yt; yt++) {
                    a = f[yt*start_yt/*---yt 2^{n-m+1}---*/ + xt];//x_m==0の場合
                    b = f[yt*start_yt + (1 << (n - m)) + xt] * exp(PI*img*double(yt) / double(1 << (m - 1)));//x_m==1の場合
         
                    g[(yt << (n - m))/*---yt 2^{n-m}---*/ + xt] = a + b;//Y_m==0の場合
                    g[(1 << (n - 1))/*2^{n-1}*/ + (yt << (n - m))/*yt 2^{n-m}*/ + xt] = a - b;//Y_m==1の場合 
        
                }
                f = g;//次のループはこのgをfとして扱う
            }
        }
         
        //逆フーリエ変換をする
        //ζnをinverse(ζn)に変換(複素共益を取る)　してFFTし最後にNで割るだけ
        void iFFT(vector<Comp>& f, int n) {
            int N = 1 << n;
            vector<Comp> g(N);
            for (int m = 1; m <= n; m++) {
                int max_xt = (1 << (n - m)) - 1;
                int max_yt = (1 << (m - 1)) - 1;
         
                int start_yt = (1 << (n - m + 1));
         
                Comp a, b;
                for (int xt = 0; xt <= max_xt; xt++)for (int yt = 0; yt <= max_yt; yt++) {
                    a = f[yt*start_yt + xt];
                    b = f[yt*start_yt + (1 << (n - m)) + xt] * exp(PI*(-img)*double(yt) / double(1 << (m - 1)));
         
                    g[(yt << (n - m)) + xt] = a + b;
                    g[(1 << (n - 1)) + (yt << (n - m)) + xt] = a - b;
                }
                f = g;
            }
         
            REP(i, N) {
                f[i] /= (double)N;
            }
        }
        #if 0
        int main() {
         
            const int n = 3;
            int N = 1 << n;
            vector<Comp> f(N);
            const double k = 3.0;
            REP(x, N) {
                f[x] = exp(-2 * PI*img*k*double(x) / double(N));
            }
            cout << "f=" << endl;
         
            REP(i, N) {
                cout << f[i] << " ";
            }
            cout << endl;
         
            auto a = FFT(f, n);
         
            cout << "FFT=" << endl;
            REP(i, N) {
                cout << a[i] << " ";
            }
            cout << endl;
        }
        #else
        int main() {
            int n;
            cin >> n;
            int a = 1;
            while (true) {
                if ((1 << a)>2 * n) { break; }
                a++;
            }
            
            int N = 1 << a;
            vector<Comp> A(N);
            vector<Comp> B(N);
         
            FOR(i, 0, n) {
                int x, y;
                cin >> x >> y;
                A[i] = Comp(x, 0), B[i] = Comp(y, 0);
            }
         
            FFT(A, a);
            FFT(B, a);
            REP(i, N) {
                A[i] *= B[i];
            }
            iFFT(A, a);
            cout << 0 << endl;
            FOR(i, 0, 2 * n - 1) {
                cout << (int)round(A[i].real()) << endl;
            }
        }
        #endif

■

ポエム

妖怪だよ。
人間の死体を食べているのは妖怪。
日本の人間は死んだら火葬場に持って行かれる。
火葬場で働く人間は妖怪などが入り込まないように御札や結界を用意しているが狡猾な妖怪はそんなものには引っかからない。
妖怪は死体が火葬炉に入った瞬間を狙う。そして妖怪の糞を固めて人間の骸状にしたものと死体とを交換するんだ。このときついでに腹に溜まった糞を出していくお茶目な奴もいる。
そして人間は火葬炉から出てきた妖怪の糞の塊を大事に箸で丁寧に拾い上げていく。
自分の出した糞を喉仏がどうこう言いながら丁寧に骨壷にしまっていく様は妖怪にとってさぞかし愉快なことだろう。
態々入り込みにくい火葬場で死体を狙わなくても葬式や死んだ直後を狙えばいいと思うかもしれないが
そんなことをしたら妖怪の存在がおおっぴらになってしまう。まあおおっぴらまでは行かないとしても妖怪の存在は確信的になってしまう。そいつはご法度だ。
普段は妖怪なんていないと思わせておいて、たまに存在を仄めかすぐらいが人間にとっても妖怪にとってもちょうどいいのだ。

経験を積んだ妖怪はその死体がどんな人間だったか大体見て分かるらしい。
昔は気に入った人間がいたらそいつは食べずに妖怪にして子分にしたらしいが、最近は妖怪の住みやすい土地も減ってきたことから妖怪数の管理が厳しく、あんまり子分を増やそうとはしないという噂を聞いたことがある。


まあ私は生憎、妖怪に好かれるような人間ではないだろうし関係ないな。私も死んだら妖怪に食べられるんだ。

スプライン補完

ゲーム製作 アルゴリズム

シューティングで敵に複雑な動きをさせたい時ありますよね...ありませんか？
こんな感じで

ぐるりんっ


x(t),とy(t)を求めてやればこのように動かすための関数が求まるため、このような動きを実現できることがわかります。
今回はスプライン補完を使ってこのような曲線を求めてみましょう

www.yamamo10.jp
3次スプライン補完の場合
(x_i,t_i)から(x_i+1,t_i+1)までの範囲を1次微分と2次微分が連続的になるようにしながら3次多項式で近似してやろうという感じです
xj(t)=aj(x-xj)**3+bj(x-xj)**2+cj(x-xj)+dj
の係数a,b,c,dはxj''(tj)を使って表現できるので
xj''(tj)を求めればよくそれは連立方程式を解けばよいという感じです

実装してみたらこんな感じで動くようになりました

コードを貼ろうかと思ったんですけどライセンスとかややこしいですよね...ライセンスどうするか決めたら貼ります
(2018,8/17)ソースは自由に使ってもらって構いませんがこれを利用したことによるいかなる損害や不利益に対する責任や賠償は一切とらないものとします。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;


static public class Fundation  {


  

    delegate float D2(int i);


    public static void MakeSprine(float[] ts, float[] xs, float[] ys,
             ref float[] ax, ref float[] bx, ref float[] cx, ref float[] dx,
               ref float[] ay, ref float[] by, ref float[] cy, ref float[] dy
            )
    {
        D2 h = (j) => { return ts[j + 1] - ts[j]; };
        D2 vy = (j) => { return 6.0f* ((ys[j + 1] - ys[j]) / h(j) - (ys[j] - ys[j - 1]) / h(j - 1)); };
        D2 vx = (j) => { return 6.0f * ((xs[j + 1] - xs[j]) / h(j) - (xs[j] - xs[j - 1]) / h(j - 1)); };
        //float[] xs;
        //float[] ys;
        //float[] ts;
        float[,] Ax_, Ay_;
        float[] bx_, by_;

        int N = ts.Length - 1;
        Debug.Assert(N == xs.Length - 1 && N == ys.Length - 1);
        //xについて
        Ax_ = new float[N - 1, N - 1];
        bx_ = new float[N - 1];
        for (int i = 0; i < N - 1; i++)
        {
            //Console.WriteLine(i);
            Ax_[i, i] = 2 * (h(i) + h(i + 1));
            if (i - 1 >= 0) { Ax_[i, i - 1] = (h(i)); }
            if (i + 1 < N - 1) { Ax_[i, i + 1] = (h(i + 1)); }

            bx_[i] = vx(i + 1);
        }
        Ay_ = new float[N - 1, N - 1];
        by_ = new float[N - 1];
        for (int i = 0; i < N - 1; i++)
        {
           // Console.WriteLine(i);
            Ay_[i, i] = 2 * (h(i) + h(i + 1));
            if (i - 1 >= 0) { Ay_[i, i - 1] = (h(i)); }
            if (i + 1 < N - 1) { Ay_[i, i + 1] = (h(i + 1)); }

            by_[i] = vy(i + 1);
        }
        //ちぇっく



        List<float> us = Gauss_Jordan(Ax_, bx_);
        //u0=0、un=0の条件を用いなければならない
        us.Insert(0, 0);
        us.Add(0);

        ax = new float[N]; bx = new float[N]; cx = new float[N]; dx = new float[N];
        ay = new float[N]; by = new float[N]; cy = new float[N]; dy = new float[N];


        for (int i = 0; i < N; i++)
        {
            bx[i] = us[i] / 2.0f;
            dx[i] = xs[i];
            ax[i] = (us[i + 1] - us[i]) / (6f * (ts[i + 1] - ts[i]));
            cx[i] = (xs[i + 1] - xs[i]) / (ts[i + 1] - ts[i]) - (ts[i + 1] - ts[i]) * (2f * us[i] + us[i + 1]) / 6.0f;
        }
        //for (int i = 0; i < N; i++)
        //{
        //    Console.WriteLine(ax[i].ToString() + " " + bx[i].ToString() + " " + cx[i].ToString() + " " + dx[i].ToString());
        //}
        us = Gauss_Jordan(Ay_, by_);
        us.Insert(0, 0);
        us.Add(0);
        for (int i = 0; i < N; i++)
        {
            by[i] = us[i] / 2.0f;
            dy[i] = ys[i];
            ay[i] = (us[i + 1] - us[i]) / (6f * (ts[i + 1] - ts[i]));
            cy[i] = (ys[i + 1] - ys[i]) / (ts[i + 1] - ts[i]) - (ts[i + 1] - ts[i]) * (2f * us[i] + us[i + 1]) / 6.0f;
        }
        //for (int i = 0; i < N; i++)
        //{
        //    Console.WriteLine(ay[i].ToString() + " " + by[i].ToString() + " " + cy[i].ToString() + " " + dy[i].ToString());
        //}
    }

    //ガウスジョルダン　行列計算
    static List<float> Gauss_Jordan(float[,] A, float[] b)
    {

        float EPS = 1e-10f;
        int n = b.Length;
        //Console.Write(n.ToString());
        //Debug.Assert(n==A[0);
        Debug.Assert(n == b.Length);

        //Aの後ろにbをつけたのをBとする
        float[,] B = new float[n, n + 1];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                B[i, j] = A[i, j];
            }
        }
        for (int i = 0; i < n; i++)
        {
            B[i, n] = b[i];
        }

        for (int i = 0; i < n; i++)
        {

            int pivot = i;

            for (int j = i; j < n; j++)
            {
                if (Mathf.Abs(B[i, j]) > Mathf.Abs(B[pivot, i])) { pivot = j; }
            }
            //Swap(B[i],B[pivot]);
            for (int kk = 0; kk < n + 1; kk++)
            {
                float t = B[i, kk];
                B[i, kk] = B[pivot, kk];
                B[pivot, kk] = t;
            }
            if (Mathf.Abs(B[i, i]) < EPS) { return new List<float>(); }

            for (int j = i + 1; j < n + 1; j++) { B[i, j] /= B[i, i]; }

            for (int j = 0; j < n; j++)
            {
                if (j != i)
                {
                    for (int k = i + 1; k < n + 1; k++)
                    {
                        B[j, k] -= B[j, i] * B[i, k];
                    }
                }
            }
        }
        List<float> x = new List<float>();
        for (int i = 0; i < n; i++)
        {
            x.Add(B[i, n]);
        }

        return x;
    }


}

Codingame_Amadeusチャレンジにっき

Codingame Amadeusチャレンジ

ルール

目的：ゲーム終了時に相手よりも多くの惑星をコントロールする。
ーーーーーーーーーーーーゲーム

このゲームは、惑星を頂点としたグラフ上で行われます。
両方のプレイヤーはできるだけ多くの惑星を支配しようとします。
プレイヤーが相手よりも惑星に多くのユニットを送っている場合、惑星はそのプレイヤーの色の星に変換され、
その支配下にあるとみなされます。
各プレイヤーは、グラフの反対側にあるそれぞれの支配下にある惑星にから出発します。

ーーーーーーーーーーーーユニット
毎ターン：
あなたは5人のユニットに命令をする必要があります
すでに少なくとも一人のユニットのいる惑星とあなたがコントロールしている惑星の隣にユニットを送れます
あなたは隣接の惑星の数に関係なく、任意の惑星にいる5人のユニットを選んで犠牲にし1人のユニットをその惑星の隣に生成することが出来ますユニットスプレッドと呼ばれます（良く分からん）

ーーーーーーーーーーーー
一つの惑星には各プレイヤー5回だけしかユニットを送る操作が出来ません.
許容値はユニットスプレッドの影響を受けません。

ーーーーーーーーーーーー
近隣の惑星に自分がコントロールしている惑星よりも相手がコントロールしている惑星のほうが多い場合
その惑星のユニットは一人失われます

ーーーーーーーーーーーー制約
16<= planetCount <=90
10<= edgeCount <=200
最初のターンの応答時間<= 1000ms
1ターンあたりの応答時間<=50ms
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
研究室の後輩がプログラムのコンテストに興味を持ったらしく
とりあえずCodingameを勧めた。
人にこういうの勧めるのあんまり良くないなと思っていて。
自分が他人に何か勧められても「はいはいそれでマウント取りたいだけでしょ。絶対やんねー」ぐらいにしか思わないので。
その後輩に今回のコンテストを教えた結果、「出ます！」とのこと。他人に勧めておいて自分が出ないのはゴミなのでとりあえず出る

~~~~1日目

とりあえずサンプルを動かしてみてゲームの性質を眺める。
こんな感じのボードになっていた。
f:id:daruma3940:20180723222204p:plain

なるほど
緑のノードを取られてしまうとそこから下は相手のものになってしまうのか。
重要なノードがあるんでそこを死守しなければならないって感じのゲームですか。

とりあえず惑星に重要度をつける。
重要度はその惑星を取り除いたときにどれだけ到達できる惑星の数が変化するか+alphaでつけた。（alphaが何だったのかもう覚えていない...）
ページランクアルゴリズムはどうだったんでしょうね。

これで重要な惑星は絶対死守するプログラムを書いたが、
盤面には次のような盤面も含まれていた。
重要なノードをとってる間にもっと大きな空間で優勢を取られるケース。
f:id:daruma3940:20180723222710p:plain
直線的になっていて重要なノードだと認識してしまうノードばかりになってしまうケース。
f:id:daruma3940:20180723222720p:plain
なるほど。

こういうのと前線を守ったりするのを適当なifelseで処理(どんな処理だったのかもう思い出せない..)したらsilverランクに上がれた。

とりあえず探索をしたいんですよね。したいんだけど愚直な探索では50msという制約ではTLEするだろう
できないところはあきらめながらでもなんとか50msで探索できる効率的な方法はないか？？？

そこで思いついたのが指し手GA Softmax

ーーーーーーーーーーーー
最初の指し手生成
貪欲手法を３つ用意する

自分の領土を出来る限り広げようとする

自分の領土を出来る限り守ろうとする

重要な惑星を出来る限り確保しようとする



これら３つの貪欲手法にしたがって複数の自分の指し手を作成しそれらの指し手を評価する

ーーーーーーーーーーーー指し手の評価方法

それぞれの自分の指し手に対して
相手の指し手を３つの貪欲手法にしたがって複数用意する。

それらの動きで盤を更新してそれぞれに対して自分が支配している惑星の数を数える。

自分の支配している惑星の数の最小をこの自分の手の評価にする
しかしこれで重要なノードをちゃんとまもろうとするのか怪しいので評価関数はその辺考慮していじくる必要はありそう


ーーーーーーーーーーーー新しい指し手の生成

次にこのleafに訪れた場合
一番スコアの良い指し手を突然変異させる、または交配させることによって新しい指し手を作ってその指し手を評価し、
最善スコアを超えるかどうかをする。

もし指し手の数が一定に達した場合は最善だった指し手と相手の応手を用いて盤面を更新してツリーを深化させる。


ーーーーーーーーーーーーnodeの選び方

ノードの選び方は末端の評価値に末端までの遠さの割引項をかけて確率的に選択する（ボルツマン分布的）


なんかかっこよく聞こえるしうまくいきそうじゃない？

最初の貪欲指し手生成で強い指し手を生成できたほうがもちろん良いのでifelseベースの行動で強いのを作れないといけないし、まだユニットスプレッドを理解していないのでそれもちゃんと把握しないといけない
大変だなぁ。
まあ明日からやっていこうかなと思ったところで1日目終わり

~~~~2日目
後輩氏は進捗発表と院試の勉強で忙しいらしく参加は厳しいらしい。
まあそうですよね。私も研究あるしゲーム作る機運が高まっていたので終了(は?)。


ーーーーー感想戦（初日しか参加してないが）



にゃるほど

コドゲは相手の戦略が見えるので対策を立てられてしまうため強い人は潜伏する傾向が強いみたいですね




にゃるほど

ykawano.hatenablog.com


にゃるほどしか感想がでないのかよ

今日の音楽の勉強２

一夜漬け音楽理論
みんなここが詳しいのでここを読もうね（これでいい気がしてきた）

ようやく作曲における禁則（っぽいもの）が出てきて何をどうしていけばいいか地に足がついた感じがするっすね

今日の音楽のお勉強

今日の音楽のお弁当
音が1オクターブ上がると周波数が2倍になる
つまり　130Hz 260 Hz, 520Hzは全てド
メジャーコード（ドミソなど)
周波数の比が綺麗（小さい整数の比で表せる）な音を同時にならすことで心地良い響きが生まれるらしい
マイナーコード　(レファラなど)
周波数の比が綺麗でない音を混ぜることでうなりが生じて不安感のある音が生まれるらしい


平均律
ド 1:1 261.63 Hz
ド# 1:1.06 277.18 Hz
レ 8:8.98 293.66 Hz
レ# 1:1.19 311.13 Hz
ミ 4:5.04 329.63 Hz
ファ 3:4.00 349.23 Hz
ファ# 1:1.41 370.00 Hz
ソ 2:3.00 392.00 Hz
ソ# 1:1.59 415.30 Hz
ラ 3:5.05 440.00 Hz
ラ# 1:1.78 466.16 Hz
シ 8:15.10 493.88 Hz

また別の調律法
ド 1:1 264 Hz
レ 8:9 297 Hz
ミ 4:5 330 Hz
ファ 　　3:4 　　　352 Hz
ソ 2:3 396 Hz
ラ 3:5 440 Hz
シ 8:15 495 Hz

pyてょんでグラフを書いてみた
平均律
ドミソ
f:id:daruma3940:20180623172344p:plain
レファラ
f:id:daruma3940:20180623172355p:plain
下の調律
ドミソ
f:id:daruma3940:20180623172411p:plain
レファラ
f:id:daruma3940:20180623172421p:plain
グラフを見ると
上の音階の定義（平均律）ではドミソでもうなってるじゃん
下の調律法ではドミソではうなりがないっすね

まあ平均律ではうなってはいるもののうなりの周期が長いのでそこまで問題にはならないということなのかも知らん

良く分からんがこの平均律という調律法を使う理由は
下の調律法ではどの音を基準として音階を作るかによって音階が変わってきてしまうので
ハ長調（ドの音を基準とした作った音階のこと？良く分かってないが）で調律したピアノはハ長調専用となり
途中で転調をするような曲は演奏不可能になってしまう。
そこでオクターブを12分割してしまう方法で音階を定義する（これが平均律）と転調も自由になるらしい。
なので多くの音楽ではこの平均律が使われているらしい

[参考]
https://yaritakunai.hatenablog.com/entry/2016/05/16/221000
http://ch.nicovideo.jp/ponponpopoponpopopopopopopon/blomaga/ar842757
http://www007.upp.so-net.ne.jp/einstein/hamaji/ichou.htm

カナダ行った時の話

昔　2週間ぐらいカナダに行ったことあるんですよ。
大学の春季留学みたいな感じのやつで。
まあ留学って言っても授業っぽいのはなくて遊びに行ったようなものなんだけど。
別に「人生経験云々～語学力云々～」みたいな意識高い理由ではなく、単純に行ってみたかったから行ってみたって感じなんですが。
まあ僕の他に行った人たちはそういう意識高い感じの理由で参加した人が多くてちょっと馴染めなかったりもしましたね。

あとホストファミリーとも全く馴染めなくて毎日「日本に帰りたい...」と思ってましたね。
Twitterとかで「外国に比べて日本ガー！」みたいなことを言ってる日本人いるじゃないですか。
あれを外国人にやられたわけです。
あとホストファミリーは割と活発な感じのするおじいちゃんとおばあちゃんだったのですが
僕に注意をするときまずホストマザーが来て僕にそのことを注意するわけです。
そして一通り注意を終えたら、今度はそれをホストファザーに伝えに行くわけです。
そしたら今度はホストファーザーが僕のところに来て同じ内容をするわけです。めんどくさかったですね。
まあどこの国にもこういう人はいます。

ホストの家の近くにちょっとした山があってそこの山頂は眺めがよくてそこの看板に"こっちの方角がアメリカ","こっちの方向が太平洋"とか書いてあるんですよね。
太平洋の方角を向きながら日本に思いを馳せてました。（実はちょっと泣いていたが恥ずかしいのでそのことは言わない）
よく漫画とかゲームで「やっぱり故郷が恋しいのじゃ」みたいなことをいう爺いるじゃないですか。
いままで全くその気持ちがわからなかったのですがわかりましたね。「これがその感情か...」みたいな。
日本に帰った夢を見たカナダの朝。絶望は半端ではなかったですね。
というか街のにおいからすでに日本とは全然違うんですよ。
日本は醤油っぽいにおいがしますが、カナダはメープルっぽいにおいがしましたね。

あと面白かったのがカナダのショッピングモールのフードコートでライスボウルセットを頼んでみた時の話で。
ライスボウルということはおにぎりじゃないですか。なので日本のおにぎりみたいなものを想像してたんですけど
店員さんが大きな炊飯ジャーをパカっと開いてアイスクリーム掬うやつでガッとご飯を掬ってドカッとプレートに乗せて私に差し出してきたんですよ。
確かにライスがボウル型になってるけどライスボウルってのはそんな雑なもんじゃねぇんだよ...!という感情がこみ上げてきましたね。

あと私が行ったところには日本食屋さんがいっぱいあって大体どこでもTeriyaki味があって。人気みたいですね。
私も食べてみましたが照り焼きではなくてすき焼きの味がしました。

あと大体どこのお店も夕方5時ぐらいに締まりますね。非常に健全な労働環境ですね。
でもまあ私のような利用者からしてみれば5時にお店が閉まってしまうのは大変不便なわけで。しかしこの不便さを受け入れることが出来なければみんなが健全に働ける社会というのはできないんだろうなぁ。

あとカナダのコンビニでは日本だとおにぎりが置いてあるところにおにぎりが置いてないのコンビニにはおにぎりが置いてあるものだということに過学習してしまった僕は大変びっくりしましたね。
代わりにベジタリアン向けのフルーツとかサラダとか置いてあるわけです。


あとお店でノリのいい店員さんに
「お前日本人か?!」
「ジャッキーチェン知ってるだろ？あちょー！」ということをされたんですが
ジャッキーチェンは中国人ですよね...
確かにジャッキーチェンはキャノンボールランという映画でゲーム好きの日本人の役を演じてましたが。
まあカナダ人から見たら日本人も中国人も変わらないということでしょう。
日本人の僕もカナダ人とアメリカ人の区別つかないし。


僕のホストファミリーはキリスト教徒でとても信心深い人でそのことについて書きたかったんだけれども眠くなってきた。
まあ大した内容ではないので期待しないで。