GREEDY_DEFEND.cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <chrono>
#include <filesystem>
#include <fstream>

using namespace std;

const int ROWS = 10;
const int COLS = 17;
const int TARGET = 10;

// GA로 찾은 파라미터
const float W_CELLS = 1.8766f;
const float W_STEAL = 3.5780f;
const float W_RISK  = 3.0015f;

ofstream g_log;
void log_init(){
    filesystem::create_directories("./logs");
    g_log.open("./logs/log.txt", ios::app);
    g_log << "===== 시작 =====\n";
    g_log.flush();
}
template<typename T>
void log(const T& msg){
    if(g_log.is_open()){ g_log << msg << "\n"; g_log.flush(); }
}

struct Move { int r1,c1,r2,c2; };

struct State {
    int board[ROWS][COLS];
    int ownership[ROWS][COLS];
    int prefix[ROWS+1][COLS+1];
    int scores[2];
    int passes;

    void build_prefix(){
        memset(prefix,0,sizeof(prefix));
        for(int r=0;r<ROWS;r++)
            for(int c=0;c<COLS;c++)
                prefix[r+1][c+1]=board[r][c]
                    +prefix[r][c+1]+prefix[r+1][c]-prefix[r][c];
    }
    int rect_sum(int r1,int c1,int r2,int c2) const {
        return prefix[r2+1][c2+1]-prefix[r1][c2+1]
              -prefix[r2+1][c1]+prefix[r1][c1];
    }
    bool check_edges(int r1,int c1,int r2,int c2) const {
        bool rf=false,rb=false,cf=false,cb=false;
        for(int r=r1;r<=r2;r++)
            for(int c=c1;c<=c2;c++)
                if(board[r][c]!=0){
                    if(r==r1) rf=true;
                    if(r==r2) rb=true;
                    if(c==c1) cf=true;
                    if(c==c2) cb=true;
                }
        return rf&&rb&&cf&&cb;
    }
    int get_moves(Move* out) const {
        int cnt=0;
        for(int r1=0;r1<ROWS;r1++)
        for(int r2=r1;r2<ROWS;r2++){
            int c1=0;
            for(int c2=0;c2<COLS;c2++){
                int s=rect_sum(r1,c1,r2,c2);
                while(s>TARGET&&c1<c2){c1++;s=rect_sum(r1,c1,r2,c2);}
                if(s==TARGET&&c1<=c2&&check_edges(r1,c1,r2,c2))
                    out[cnt++]={r1,c1,r2,c2};
            }
        }
        return cnt;
    }
    void apply(int r1,int c1,int r2,int c2,int player){
        for(int r=r1;r<=r2;r++)
            for(int c=c1;c<=c2;c++){
                int prev=ownership[r][c];
                if(prev!=0&&prev!=player) scores[prev-1]--;
                ownership[r][c]=player;
                board[r][c]=0;
            }
        scores[player-1]+=(r2-r1+1)*(c2-c1+1);
        build_prefix();
    }
    bool is_terminal() const { return passes>=2; }
};

// 상대 최선: 자기 칸 수 + 뺏는 칸 수 최대
Move opp_best(const State& s, int my_p){
    Move moves[500];
    int n=s.get_moves(moves);
    int best_score=INT_MIN;
    Move best_m={-1,-1,-1,-1};
    for(int i=0;i<n;i++){
        int cells=(moves[i].r2-moves[i].r1+1)*(moves[i].c2-moves[i].c1+1);
        int steal=0;
        for(int r=moves[i].r1;r<=moves[i].r2;r++)
            for(int c=moves[i].c1;c<=moves[i].c2;c++)
                if(s.ownership[r][c]==my_p) steal++;
        int score=cells+steal;
        if(score>best_score){best_score=score;best_m=moves[i];}
    }
    return best_m;
}

// 내 최선: 순이득(내 칸 - 상대 뺏기 위험) 최대
// returns {best_score, best_move}
pair<int,Move> my_best(const State& s, int my_p){
    Move moves[500];
    int n=s.get_moves(moves);
    int opp=3-my_p;
    int best_score=INT_MIN;
    Move best_m={-1,-1,-1,-1};
    for(int i=0;i<n;i++){
        int cells=(moves[i].r2-moves[i].r1+1)*(moves[i].c2-moves[i].c1+1);
        State tmp=s;
        tmp.apply(moves[i].r1,moves[i].c1,moves[i].r2,moves[i].c2,my_p);
        Move om[500]; int on=tmp.get_moves(om);
        int risk=0;
        for(int j=0;j<on;j++){
            int steal=0;
            for(int r=om[j].r1;r<=om[j].r2;r++)
                for(int c=om[j].c1;c<=om[j].c2;c++)
                    if(tmp.ownership[r][c]==my_p) steal++;
            risk=max(risk,steal);
        }
        float score=W_CELLS*cells-W_RISK*risk;
        if(score>best_score){best_score=(int)score;best_m=moves[i];}
    }
    return {max(0,best_score), best_m};
}

// N수 lookahead: 재귀로 깊이 조절
// 내 턴: 순이득 최대 선택
// 상대 턴: 자기 칸 + 뺏기 최대 선택
// 반환: 현재 상태에서 my_p의 순이득 총합
int lookahead(const State& s, int /*player*/, int my_p, int depth, bool is_my_turn){
    if(depth==0 || s.is_terminal()) return 0;

    Move moves[500];
    int n=s.get_moves(moves);
    if(n==0) return 0;

    if(is_my_turn){
        // 내 턴: 순이득 + 앞으로의 lookahead 최대
        int best=INT_MIN;
        for(int i=0;i<n;i++){
            int cells=(moves[i].r2-moves[i].r1+1)*(moves[i].c2-moves[i].c1+1);
            State tmp=s;
            tmp.apply(moves[i].r1,moves[i].c1,moves[i].r2,moves[i].c2,my_p);
            // 상대 뺏기 위험
            Move om[500]; int on=tmp.get_moves(om);
            int risk=0;
            for(int j=0;j<on;j++){
                int steal=0;
                for(int r=om[j].r1;r<=om[j].r2;r++)
                    for(int c=om[j].c1;c<=om[j].c2;c++)
                        if(tmp.ownership[r][c]==my_p) steal++;
                risk=max(risk,steal);
            }
            int score=(int)(W_CELLS*cells-W_RISK*risk)+lookahead(tmp,3-my_p,my_p,depth-1,false);
            best=max(best,score);
        }
        return best==INT_MIN?0:best;
    } else {
        // 상대 턴: 상대 최선 1개만 (자기 칸 + 뺏기 최대)
        Move bm=opp_best(s,my_p);
        if(bm.r1<0) return 0;
        State tmp=s;
        tmp.apply(bm.r1,bm.c1,bm.r2,bm.c2,3-my_p);
        return lookahead(tmp,my_p,my_p,depth-1,true);
    }
}

class Game {
private:
    State st;
    bool first;
    bool passed;
    int turn_count;
    // DP 캐시
    Move predicted_opp={-2,-2,-2,-2};
    vector<pair<Move,int>> cached_scores;

    int my_player() const { return first?1:2; }
    int opp_player() const { return first?2:1; }

public:
    Game()=default;

    Game(const vector<vector<int>>& b, bool first)
        : first(first),passed(false),turn_count(0){
        memset(st.ownership,0,sizeof(st.ownership));
        st.scores[0]=st.scores[1]=0;
        st.passes=0;
        for(int r=0;r<ROWS;r++)
            for(int c=0;c<COLS;c++)
                st.board[r][c]=b[r][c];
        st.build_prefix();
        log("게임 시작: "+string(first?"FIRST":"SECOND"));
    }

    vector<int> calculateMove(int myTime, int){
        auto t_start=chrono::high_resolution_clock::now();
        int my_p=my_player();

        Move moves[500];
        int n=st.get_moves(moves);

        // DP 캐시 확인: 상대가 예측한 수를 뒀는지
        bool cache_hit = cache_valid && !cached_scores.empty();
        cache_valid = false; // 다음 턴을 위해 초기화

        int best_idx=-1;
        int best_score=INT_MIN;

        if(cache_hit){
            // 캐시 사용: 이미 계산된 점수로 바로 선택
            for(auto& [m,sc]:cached_scores){
                if(sc>best_score){
                    best_score=sc;
                    // 인덱스 찾기
                    for(int i=0;i<n;i++){
                        if(moves[i].r1==m.r1&&moves[i].c1==m.c1&&
                           moves[i].r2==m.r2&&moves[i].c2==m.c2){
                            best_idx=i; break;
                        }
                    }
                }
            }
        }

        if(!cache_hit || best_idx<0){
            // 먼저 안전한 수(risk=0) 탐색
            int safe_best_idx=-1;
            float safe_best_score=-1e9f;
            for(int i=0;i<n;i++){
                int cells=(moves[i].r2-moves[i].r1+1)*(moves[i].c2-moves[i].c1+1);
                State tmp=st;
                tmp.apply(moves[i].r1,moves[i].c1,moves[i].r2,moves[i].c2,my_p);
                Move om[500]; int on=tmp.get_moves(om);
                int risk=0;
                int my_steal=0;
                for(int j=0;j<on;j++){
                    int steal=0;
                    for(int r=om[j].r1;r<=om[j].r2;r++)
                        for(int c=om[j].c1;c<=om[j].c2;c++)
                            if(tmp.ownership[r][c]==my_p) steal++;
                    risk=max(risk,steal);
                }
                // 내가 뺏는 칸
                for(int r=moves[i].r1;r<=moves[i].r2;r++)
                    for(int c=moves[i].c1;c<=moves[i].c2;c++)
                        if(st.ownership[r][c]==3-my_p) my_steal++;
                if(risk==0){
                    float score=W_CELLS*cells+W_STEAL*my_steal;
                    if(score>safe_best_score){safe_best_score=score;safe_best_idx=i;}
                }
            }

            if(safe_best_idx>=0){
                // 안전한 수가 있으면 그 중 최선 선택
                best_idx=safe_best_idx;
                best_score=(int)safe_best_score;
            } else {
                // 안전한 수 없으면 깊이 2 lookahead
                for(int i=0;i<n;i++){
                    int cells=(moves[i].r2-moves[i].r1+1)*(moves[i].c2-moves[i].c1+1);
                    State tmp=st;
                    tmp.apply(moves[i].r1,moves[i].c1,moves[i].r2,moves[i].c2,my_p);
                    Move om[500]; int on=tmp.get_moves(om);
                    int risk=0;
                    for(int j=0;j<on;j++){
                        int steal=0;
                        for(int r=om[j].r1;r<=om[j].r2;r++)
                            for(int c=om[j].c1;c<=om[j].c2;c++)
                                if(tmp.ownership[r][c]==my_p) steal++;
                        risk=max(risk,steal);
                    }
                    int score=(int)(W_CELLS*cells-W_RISK*risk)+lookahead(tmp,3-my_p,my_p,1,false);
                    if(score>best_score){best_score=score;best_idx=i;}
                }
            }
        }

        // 다음 턴을 위한 DP 사전 계산
        // 1) 내 수 적용
        // 2) 상대 예측 수 계산
        // 3) 그 상태에서 내 후보 수 점수 미리 계산
        cached_scores.clear();
        predicted_opp={-2,-2,-2,-2};
        if(best_idx>=0){
            State s1=st;
            s1.apply(moves[best_idx].r1,moves[best_idx].c1,
                     moves[best_idx].r2,moves[best_idx].c2,my_p);
            predicted_opp=opp_best(s1,my_p);
            if(predicted_opp.r1>=0){
                State s2=s1;
                s2.apply(predicted_opp.r1,predicted_opp.c1,
                         predicted_opp.r2,predicted_opp.c2,3-my_p);
                Move next_moves[500];
                int nn=s2.get_moves(next_moves);
                for(int i=0;i<nn;i++){
                    int cells=(next_moves[i].r2-next_moves[i].r1+1)*(next_moves[i].c2-next_moves[i].c1+1);
                    State tmp=s2;
                    tmp.apply(next_moves[i].r1,next_moves[i].c1,
                              next_moves[i].r2,next_moves[i].c2,my_p);
                    Move om[500]; int on=tmp.get_moves(om);
                    int risk=0;
                    for(int j=0;j<on;j++){
                        int steal=0;
                        for(int r=om[j].r1;r<=om[j].r2;r++)
                            for(int c=om[j].c1;c<=om[j].c2;c++)
                                if(tmp.ownership[r][c]==my_p) steal++;
                        risk=max(risk,steal);
                    }
                    int sc=(int)(W_CELLS*cells-W_RISK*risk)+lookahead(tmp,3-my_p,my_p,1,false);
                    cached_scores.push_back({next_moves[i],sc});
                }
            }
        }
        int best_depth=2;

        auto t_end=chrono::high_resolution_clock::now();
        int ms=(int)chrono::duration<double,milli>(t_end-t_start).count();

        vector<int> result={-1,-1,-1,-1};
        if(best_idx>=0)
            result={moves[best_idx].r1,moves[best_idx].c1,
                    moves[best_idx].r2,moves[best_idx].c2};

        turn_count++;
        int cells=best_idx>=0?
            (moves[best_idx].r2-moves[best_idx].r1+1)*(moves[best_idx].c2-moves[best_idx].c1+1):0;
        log("[턴"+to_string(turn_count)+"] "
            +to_string(ms)+"ms, 깊이:"+to_string(best_depth)
            +", 선택: ("+to_string(result[0])+","+to_string(result[1])
            +"~"+to_string(result[2])+","+to_string(result[3])+")"
            +"="+to_string(cells)+"칸 점수:"+to_string(best_score)
            +", 남은: "+to_string(myTime)+"ms"
            +", 스코어 내:"+to_string(st.scores[my_p-1])
            +" 상대:"+to_string(st.scores[2-my_p]));

        return result;
    }

    bool cache_valid = false;  // 캐시 유효 여부

    void updateOpponentAction(const vector<int>& action,int){
        // 실제 상대 수가 예측과 같은지 확인
        int r1=action[0],c1=action[1],r2=action[2],c2=action[3];
        if(predicted_opp.r1==r1 && predicted_opp.c1==c1 &&
           predicted_opp.r2==r2 && predicted_opp.c2==c2){
            cache_valid=true;
        } else {
            cache_valid=false;
            cached_scores.clear();
        }
        updateMove(r1,c1,r2,c2,false);
    }
    void updateMove(int r1,int c1,int r2,int c2,bool isMyMove){
        if(r1==-1&&c1==-1&&r2==-1&&c2==-1){passed=true;return;}
        int player=isMyMove?my_player():opp_player();
        st.apply(r1,c1,r2,c2,player);
        st.passes=0;
        passed=false;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    log_init();

    Game game;
    bool first=false;

    while(true){
        string line;
        getline(cin,line);
        istringstream iss(line);
        string command;
        if(!(iss>>command)) continue;

        if(command=="READY"){
            string turn; iss>>turn;
            first=(turn=="FIRST");
            cout<<"OK"<<endl;
        } else if(command=="INIT"){
            vector<vector<int>> board;
            string row;
            while(iss>>row){
                vector<int> br;
                for(char c:row) br.push_back(c-'0');
                board.push_back(br);
            }
            game=Game(board,first);
        } else if(command=="TIME"){
            int myTime,oppTime; iss>>myTime>>oppTime;
            vector<int> ret=game.calculateMove(myTime,oppTime);
            game.updateMove(ret[0],ret[1],ret[2],ret[3],true);
            cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<" "<<ret[3]<<endl;
        } else if(command=="OPP"){
            int r1,c1,r2,c2,t; iss>>r1>>c1>>r2>>c2>>t;
            game.updateOpponentAction({r1,c1,r2,c2},t);
        } else if(command=="FINISH"){
            log("===== 종료 =====");
            break;
        }
    }
    return 0;
}