CodeVS Reborn 参戦記

公開日:2019-05-21
最終更新:2019-05-23

概要

https://codevs.jp/
最終成績 26位/112人 予選敗退
それにしてもレベル高かった...疲れた...

最終的な戦略

連鎖の探索

  • 幅1、深さ15で通称chokudai searchにて、
    • 連鎖は多く
    • 発火は早く
      となる評価値で最良の手を探す
  • 次の深さに残す探索用の評価値と、実際に打つことになる手としての評価値は別々で作る
    • 探索用の評価値は実際に空きマス8近傍を消してみて発生した連鎖数
  • 通常は5ターンおきに5秒程度時間をかけて読み直す
    • このため 5ターンに1度は思考時間が長くなる、それ以外のターンでは高速に手が決定される
  • 次の場合は5ターンおきじゃなくても読み直す
    • 想定していない量のお邪魔が降ってきた時(相手が発火した)
    • 自分が連鎖の探索に従った結果、発火した次のターン
    • それ以外で自分が連鎖の探索で読んだ手と違う手を打った時 (後述)

発火タイミング

  • 通常は上で探しておいた手を打つが、次の場合はその手以外でも打つ
    • 相手が発火したときに、重要な発火点が潰されてしまう時。→予定より早いが今発火してしまう
    • 今発火すると相手の重要な発火点を潰せる時→予定より早いが今発火してしまう
    • 相手が発火したときに、自分は次のターン以降に発火したほうが明らかに大きな連鎖で返すことができる時→予定より遅いがあとで発火する
  • ただ、たぶん不具合で上記アルゴリズムがきちんと動いてるのか怪しい...

ビットフィールドの設計

  • 1マスを4ビットで表現する。ただし4ビットを詰めていくのではなく、1桁ずつ別の変数に入れる
  • 縦1列が uint32_t で表現されて、横に10個並べて1セット。これを4セット。
  • つまり一盤面は uint32[10][4]
入力 0bit 1bit 2bit 3bit
0(empty) 0 0 0 0
1 0 1 0 0
2 0 1 0 1
3 0 1 1 0
4 0 1 1 1
5 1 1 1 1
6 1 0 1 1
7 1 0 1 0
8 1 0 0 1
9 1 0 0 0
11(ojama) 0 0 1 1
  • 消去判定は桁ごとのビット演算でできる。具体的には2つのブロックについて、以下を満たせばOK
    • 3,4ビット目を xor したときに 00 となる
    • 1,2ビット目について
      • 1つ目ブロックの1ビット目 == 2つ目ブロックの2ビット目 かつ
      • 2つ目ブロックの1ビット目 == 1つ目ブロックの2ビット目
  • 落下処理はpext
  • 普通に配列で実装するより2倍~3倍くらい早くなった。(もっと早くする余地はありそう)
  • https://mayah.booth.pm/ をめっちゃ参考にした

自分向けKPT

Keep

  • pext, pdep, pocnt の Intel拡張命令を初めて使ってみた。普通に使えた。今後もハード構成次第では積極的に使ってく
  • 探索アルゴリズムのクラスで、探索の処理と、探索の結果や詳細を取得するのを分ける設計がうまくいった。具体的には、アルゴリズムを扱うクラスを作ってしまい、calcで計算、あとからgetterなどで詳細を取得する。
class AlphaBeta {  
public:   
    AlphaBeta(const Board& board);  
    void calc(); //処理する関数  
    Move getBestMove(); //アルゴリズムで最良と判定した手  
    void getDetail(); //アルゴリズムの詳細、必要な情報に応じて追加するなど  
}  
  • この設計のメリットとして、アルゴリズムの差し替えに強い。例えばcalc関数やgetBestMove関数を必須の関数として他のアルゴリズムクラスにも実装する。BestFirstSearchでもBeamSearchでもSimulatedAnnealingでも、同じインターフェースの関数を実装してしまえば簡単に差し替えられる。色々と試すフェーズでは使い勝手がいい。
    • BestFirstSearchとBeamSearchで、次に調べたいノードを決める関数と、最終的にベストな手をを決める関数を分けて考えることができた。今まであまり消化できてなかった考え方ができた。具体的には以下。
double searchNodeScore(Node& node)  
{  
    return nodeの探索する価値;  
}  
double bestMoveScore(Node& node)  
{  
    return nodeがゲーム中に打つ手としての良さ;  
}  
void search(){  
    Node{  
        Board mBoard; //盤面  
        Move mPrevMove; //このノードに至るときに打った手  
        Node* mpPrevNode; //このノードの手前の盤面を持つノード  
    }  
    Node root;  
    Queue<Node> queue;  
    queue.push(&root);  
    while(時間や回数のリミットを迎えてない)  
    {  
        Node* pNode = queue.top();  
        queue.pop();  
        double ms = bestMoveScore(pNext);  
        if(ms > bestScore){  
            //ノードが打ちたい手(到達したい盤面)として高い価値なら記録  
            bestNode = pNext;  
        }  
        //pNodeから展開可能な手を打って次の盤面を作りノードとする  
        forEachMove(pNode, [pNode](const Move& move){  
            Node* pNext = new Node(generateNextBoard(pNode->mBoard, move)));  
            double ss = searchNodeScore(pNext);  
            queue.push(pNext, ss);    //探索用のスコアで優先度付きキューイング  
        });  
    }  
}  
  • この作戦は、今回の連鎖構築みたいに、いいノードとそこに至るまでのノードの評価が違うパターンで有効となる。今回は次のように評価が違っていた。
    • 最終的には連鎖を打ちたい(連鎖数が大きいほうがいい評価)
    • しかし途中で連鎖を打ってしまうと連鎖数が大きくならない
  • もちろん評価関数の設計次第ということも言えるけど。
    • よく理解しているつもりのオセロや囲碁みたいなゲームでは、いい盤面(勝率が高い)にはいい盤面(勝率が高い)を通るような前提で評価関数を作ることが大半だったので、評価関数を分ける経験はあまりなかった。

Problem & Try

Problem: イマイチ的を得た考察ができてなかった

  • 探索木的に、大きい連鎖を打てるノードの近くには大きい連鎖を打てるノードが多いに違いない→特にそんなことなかった。
  • 連鎖よりもいつ発火するかのタイミングが重要に違いない → 大きい連鎖を打てる状況が発火タイミングを選べるほど多くなかった。素直に連鎖を少しでも早く多く打てるようにして、最低限(死にそうなら打つ、相手をこのターンで殺せるなら打つ、お邪魔が降ってきそうならそれを前提に読み直す)の発火タイミング制御のほうが強そう
  • 発火タイミングを選びやすく、連鎖速度も落とさないような探索方法を編み出せなかったというだけかも

Try: 新しく試すときは速やかに可視化を考える。

  • 戦わせて勝率を見る、ということをまずしたくなるけど、推測した内容が正しいかどうかを根拠にしないと、思い込みに気が付かないままチューニングしたり、実装を疑ったり、無駄な時間を過ごしがち

Problem: 同時着手の2手以上先を考慮した探索をうまく作れなかった

  • 交互着手ならαβ系一度なんだけど、同時着手はいつもよくわからない
  • 今回は同時着手ゲームの典型的な、常に最良な手があるとは限らない(相手の選択次第でよくも悪くもなる)というゲームであることはわかった
  • CRFが意識にはあったけど、試さなかった
  • αβを2手読むはやってみたけど、いい結果にはならなかった。ただ、なぜいい結果にならないのかは完全に理解できず、うまく採用できなかった

Try: 丁寧に評価値を出力して比較する作業をサボらない。

  • そういう作業は後半ほど近視眼的になってやれなくなってくる。性格的に(?)
  • コンテスト序盤でやる。

Problem: いいかげん典型的なアルゴリズムはライブラリ化するべき

  • アルファベータの実装がバグってないか考えるの無駄すぎる

Try: やるべき

  • いいインターフェースも今回思いついたことだし、コピペで使いやすい形を目指して作るべき

Problem: 計算力のためにPC新調まではしないとしても、なぜ8コア使って計算しなかった

Try: 自前のPCで計算できるという意味を理解してなかった。どうすればこういうの見落とさなくできるのか...

  • 頭が固くなる前の序盤の時点でTODOを考えてしまう?

感想

  • 悔しいけど自分の実力ではこんなものだなあ
  • 機械学習とか始まる前はできたらいいと思ってたけど、案の定準備ができてなくてできなかった。普段から勉強して準備しましょう。
記事が少しでもいいなと思ったらクラップを送ってみよう!
4
+1
論文紹介、知った技術、競技プログラミング参戦記書いていきます

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする