4目並べ https://github.com/sapporocpp/4moku のAI：「次の自分の手で勝ち確定なら必ず選ぶ」「次の相手の手で負け確定は必ず避ける」

kakutei.hpp

#include "4moku.hpp"

std::tuple<int,int> AI_FUNCTION(const Board& board,int player) {
    // ・自分が勝つことが確定するような置き場所があるならそこに置く。
    // ・自分が置くことで、次に相手が勝つことが確定する置き場所があるならそこは置かない。
    // ・そうでなければ、置ける場所に置く。
    
    const int num_players = 2;
    // プレイヤー総数。実際はboardから取れるようになる予定
    
    int nx,ny;
    std::tie(nx,ny) = board.size();
    std::tuple<int,int> random_choice;
    random_choice = std::make_tuple(-1, -1);
    
    static std::mt19937 mt(std::time(0));
    std::uniform_real_distribution<double> rnd(0.0, 1.0);
    
    int candidates = 0;
    for(int i = 0; i < nx; ++i){
        for(int j = 0; j < ny; ++j){
            if(!placeable(board, i, j)) continue;
            
            std::tuple<int,int> this_choice = std::make_tuple(i, j);
            
            // ランダム選択の場所が何も選ばれていない場合、選んでおく
            // （エラーにならないようにするため）
            if(std::get<0>(random_choice) == -1){
                random_choice = this_choice;
            }
            
            // そこに置くことで自分の勝ちが確定できるなら置く
            Board board_tmp(board);
            board_tmp(i, j) = player_id(player);
            if(finished(board_tmp)) return this_choice;
            
            // そこに置くことで、次に相手が置いて勝てる場所があるならそこに置かない
            // 相手が置く場所の候補を(p, q)とし、すべての置き場所について試している。
            bool lost = false;
            for(int p = 0; p < nx; ++p){
                for(int q = 0; q < ny; ++q){
                    if(!placeable(board_tmp, p, q)) continue;
                    
                    Board board_tmp2(board_tmp);
                    board_tmp2(p, q) = player_id((player+1) % num_players);
                    if(finished(board_tmp2)){
                        lost = true;
                        //std::cerr << "Placing at (" << i << ", " << j << ") lets the opponent win!" << std::endl;
                        break;
                    }
                }
                
                if(lost) break;
            }
            
            // そこに置いて負けが確定しない場合、ランダム選択の候補に加える。
            // 
            // ただし、置ける場所が何箇所あるかは最初からはわからないので、
            // 以下の方法で選択する。
            // ・1つ目に見つかった置ける場所については、確率1で選ぶ。
            // ・2つ目に見つかった置ける場所については、確率1/2で選ぶ。
            // ・3つ目に見つかった置ける場所については、確率1/3で選ぶ。
            //   :
            // いくつめの置ける場所であるかは、candidatesに保持している。
            if(!lost){
                ++candidates;
                if(rnd(mt) <= 1.0 / static_cast<double>(candidates)){
                    random_choice = this_choice;
                }
            }
        }
    }
    
    //std::cerr << "Random choice! "
    //    << std::get<0>(random_choice) << ", "
    //    << std::get<1>(random_choice) << std::endl;
    return random_choice;
}