半自動決定木学習
概要
ゲームなどの答えが Yes/No の問題に対し、必要そうな特徴量を見繕って片っ端から決定木に放り込み学習させます。
決定木は C++ 用のものを ChatGPT に書かせました。
例題
解答
まず局面を表す型を決めます。
列 $ A を表すリストと値が集合 $ S に属するか否かを表すリストでいいでしょう。
code:POS.cpp
using POS = pair<vi, vi>; // (A, inS)
次に局面 p から遷移可能な局面のリスト nps を返す関数を実装します。
ゲームのルールをそのまま実装するだけで構いません。
code:get_next_poss.cpp
vector<POS> get_next_poss(const POS& p) {
vector<POS> nps;
int n = sz(a);
bool end = true;
rep(i, n) if (bi == 0) end = false; if (end) return nps;
rep(i, n) {
auto na(a);
auto nb(b);
nps.push_back({ na, nb });
}
return nps;
}
次に局面 p の特徴ベクトル vec を返す関数を実装します。
ここだけは頭を働かせて実装する必要があります。
試しに A の長さ、パス可能回数、残る偶数の個数、残る奇数の個数を入れてみましょう。
あとゲームの問題では偶奇が大事がちなので 2 で割った余りも放り込んでおきます。
code:feature_extraction.cpp
vi feature_extraction(const POS& p) {
vi vec;
int n = sz(a);
vi A; int rem = 0;
rep(i, n) {
}
else {
}
}
int N = sz(A);
vi cnt(2);
vec.push_back(N);
vec.push_back(rem);
vec.push_back(rem % 2);
return vec;
}
最後に調べたい局面のリスト ps を返す関数を実装します。
適当に乱択で小さめの局面を 1000 個選ぶことにします。
code:create_positions.cpp
vector<POS> create_positions() {
vector<POS> ps;
mt19937_64 mt((int)time(NULL));
uniform_int_distribution<ll> rnd(0, (ll)1e18);
rep(hoge, 1000) {
int len = rnd(mt) % 7 + 1;
vi a; vi b(len);
rep(fuga, len) a.push_back(rnd(mt) % 6 + 1);
ps.push_back({ a, b });
}
return ps;
}
局面の勝敗は自動で決定してくれるので正解ラベルを付ける必要はありません。
この設定で学習させてみると、次のような決定木が出力されました：
code:output.cpp
int predict(vi x) {
if (x0 < 1)return 0; else if (x0 < 2)return 1; else if (x4 < 1)if (x6 < 1)if (x2 < 2)if (x2 < 1)return 0; else if (x0 < 5)return 1; else return 0; else return 0; else if (x0 < 3)return 0; else return 1; else if (x6 < 1)return 1; else if (x0 < 4)if (x2 < 1)return 0; else return 1; else return 0; }
これをソースコードに貼り付けて提出することで AC が得られます。
提出
他の使用例
ゲームではない多クラス分類ですが、愚直解が書ければ同様にして解けます。
元ポスト