폴리매스

1. 돌리거나 뒤집어서 같은 두 틱택토는 다른것으로 취급.

2. 같은 틱택토라도 돌을 놓는 순서가 다르다면 다른 틱택토로 취급

제 해석이 맞는 것인지 모르겠네요..

#1

이 문제의 핵심은 틱택토에서 승리한 경우 더이상 말을 놓지 않는다는 것입니다.

그러니까, 돌이 단 5개만 놓일수도, 9개 전부 놓일수도 있습니다.

어느사람이 몇번째 말을 놓았을때 승리하는지에 따라 case를 나누었습니다.

참고로 검은색 말이 먼저하는 사람, 흰색이 나중에 하는 사람입니다.

그리고 그 안에서 어느 위치에 3개가 연달아 있어 승리하는지와 누가 승리하는지에 따라 또 case를 나눕니다.

마지막으로, 끝까지 끝나지 않는 경우는 흰색의 위치 4개만 승리하는 사람이 없도록 정하고 나머지 위치에 검은색 말이 있다고 생각하면 됩니다.

풀이가 노가다성이 다분한 풀이일테니 좀 끊어서 올리겠습니다.

3번은 틱택토는 무조건 비기는 것으로 알려져 있기 때문에...........왠만한 경우 비기게 둘 수는 있지만,

이 문제에서 요구하는 최선을 다하는 수순은 각 말을 놓은 후의 수순들을 무작위로 했을때 가장 이길 확률이 높은 수순을 고려하라는 것 같습니다.

우선 돌리거나 뒤집었을 때 같은 두 틱택토를 다르다고 놓고 풀어 보겠습니다.

틱택토 게임의 경우 두 플레이어가 최선으로 플레이하면 무승부라는 것이 알려져 있는데 이 문제에서 최선의 수라는 것이 무엇을 의미하는 것인가요? 단순히 최선으로 했을 때를 구하라면 다양한 가짓수가 나올 것 같은데요.

 (3번 문제)가능한 경우 몇몇을 검토해 보았습니다. 비슷한 결과가 나오는 과정들은 생략하였습니다. 보아하니 처음에 귀퉁이에 놓으면 다음 사람이 임의로 돌을 놓을 때 의 확률로 이기네요.

1-4와 같은 경우까지 합치면 확률이 더 올라갑니다. 두 명 다 최선을 다하고 몇수 앞을 보는 알파고들 이라고 하면 1-2 ,1-3 ,1-5 ,1-6 중 하나로 전개 될 것으로 예상됩니다.  두 명이 다 최선을 다하면 다 비깁니다. /resources/comment/2019/02/34bfff4e455cf37a92890e49937f8846.show

답은 아래와 같습니다.

X1 -> Y5 -> X9 -> Y2 -> X8 -> Y7 -> X3 -> Y6 -> X4

X1 -> Y5 -> X6 -> Y2 -> X8 -> Y7 -> X3 -> Y9 -> X4

X1 -> Y5 -> X6 -> Y2 -> X8 -> Y9 -> X4 (7) ->　Y7 (4) -> X3

X1 -> Y5 -> X6 -> Y3 -> X7 -> Y4 -> X8 (9) -> Y9 (8) -> X2

X1 -> Y5 -> X6 -> Y8 -> X2 -> Y3 -> X7 -> Y4 -> X9

X1 -> Y5 -> X6 -> Y9 -> X2 -> Y3 -> X7 -> Y4 -> X8

X1 -> Y5 -> X6 -> Y9 -> X3 -> Y2 -> X8 -> Y4 (7) -> X7 (4)

X1 -> Y5 -> X6 -> Y9 -> X7 -> Y4 -> X2 (3) -> Y3 (2) -> X8

X1 -> Y5 -> X6 -> Y9 -> X8 -> Y2(3, 7, 8) -> X4/7(4/7,  2/3,  2/3) -> Y(7/4,  3/2,  3/2) ->　X3(2, 8, 7)

결과는 모두 무승부입니다.

 풀이 (왼쪽 링크를 누르세요)

문제를 풀 때 필요한 조건이 불충분했군요.

친구들이 남긴 의문을 교수님께 전달드렸으니 조금만 기다려주세요!

흥미롭군요.

게임을 하는 사람이 상대방은 완전히 무작위로 돌을 둔다고 보고 모든 수를 둘 확률이 같다고 볼 때, 이길 확률이 가장 큰 움직임을 하게 만들어 봤습니다.

1: X5
2: Y1
3: X3
4: Y4
5: X7

의 결과가 나왔습니다.

코드는 아래와 같습니다.

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int rows[8][3] = {
    0, 1, 2,
    3, 4, 5,
    6, 7, 8,
    0, 3, 6,
    1, 4, 7,
    2, 5, 8,
    0, 4, 8,
    2, 4, 6
};

struct tictactoe{ /// 틱택토 구조체를 만듭니다.
    /// 3x3 사이즈의 보드를 만드는데, 돌이 없으면 0, 돌이 있으면 몇 번째로 놓인 돌인지를 씁니다.
    /// 이때 A가 처음 시작합니다.
    /// 일차원 배열로 보드를 만드는 법.
    /// [0] [1] [2]
    /// [3] [4] [5]
    /// [6] [7] [8]
    vector<int> board;

    /// 이 상황에서 말을 더 놓았을 때 a가 이기는 경우의 수, b가 이기는 경우의 수, 전체 경우의 수(무승부 포함).
    int a_win = 0;
    int b_win = 0;
    int all_cnt = 0;

    /// 지나간 턴 수입니다.
    int turns;

    /// 현재 상황에서 말을 하나 더 놓았을 때 진행할 수 있는 틱택토 판의 모임입니다.
    tictactoe* child[9];

    tictactoe(){ /// 0-틱택토 생성자.
        board.assign(9, 0);
        turns = 0;
    }

    ~tictactoe(){ /// 틱택토 소멸자.
        for(int i=0; i<9; i++){
            if(child[i]){
                delete child[i];
            }
        }
    }

    tictactoe(vector<int> board): board(board){ /// 틱택토 생성자.
//        printf("made tictactoe:");
//        for(int i=0; i<9; i++) printf(" %d", board[i]);
//        puts("");
        turns = 0;
        for(int i=0; i<9; i++){ /// 지나간 턴 수 체크.
            if(board[i]) turns++;
        }
        for(int i=0; i<8; i++){ /// 이긴 사람이 있는지 체크.
            if(board[rows[i][0]]%2 == board[rows[i][1]]%2 &&
               board[rows[i][1]]%2 == board[rows[i][2]]%2 &&
               board[rows[i][0]] && board[rows[i][1]] && board[rows[i][2]]){
                if((board[rows[i][0]]&1) == 1) a_win = 1;
                else b_win = 1;
                all_cnt = 1;
                break;
            }
        }
        if(turns == 9) all_cnt = 1;
    }

    void make(){ /// 모든 경우의 수를 만듭니다.
        if(a_win || b_win) return;
        for(int i=0; i<9; i++){
            if(board[i] == 0){
                board[i] = turns+1;
                child[i] = new tictactoe(board);
                child[i] -> make();
                board[i] = 0;
                a_win += child[i] -> a_win;
                b_win += child[i] -> b_win;
                all_cnt += child[i] -> all_cnt;
            }
        }
    }

    void find_way(){
        if(turns == 9) return;
        double max_possibility = -0.1;
        int idx = -1;
        for(int i=0; i<9; i++){
            if(child[i] == 0) continue;
            double tmp = (double)((turns&1)?(child[i] -> b_win): (child[i] -> a_win))
                                                                / (child[i] -> all_cnt);
            if(max_possibility < tmp){
                max_possibility = tmp;
                idx = i;
            }
        }
        if(idx == -1) return;
        printf("%d: %c%d\n", turns+1, (turns&1)?'Y':'X', idx+1);
        child[idx] -> find_way();
    }
};

int main(){
    /// 0-tictactoe를 만듭니다. 초기 상태 틱택토로, 0-벡터와 비슷한 개념입니다.
    tictactoe* zero_tictactoe = new tictactoe();
    zero_tictactoe -> make();
    zero_tictactoe -> find_way();
    delete zero_tictactoe;
}
 

허얼... 하루만에 21개 실화임...

문제와 질문의 표현을 일부 수정했습니다. 배열보단 '진행'에 초점을 맞춰 풀어보세요!

3번에서 양쪽다 최선의 수를 두면 다음수순이 되는것 같습니다.

물론 저모양을 돌린 모양도 나오지요.

그럼 1번은 255168, 2번은 131184입니다.

(제 생각엔) 추가문제 나올 것도 같네요.

1 9 6

4 2 5

7 8 3

현재까지 올라온 풀이는 현재 멘토님이 확인 중!

처음엔 댓글이 많이 달려오다가 갑자기 확 주네요~

현재 교수님께서 풀이를 검토 중입니다! 조금만 더 기다려주세요!!

풀이를 제출한 지 2달이 다 되어 가는데 아직도 정답 여부를 알지 못하고 있습니다.

검토 결과가 언제쯤 나오나요?