본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 대26. 돌아온 틱택토(Tic-Tac-Toe) 게임
수학동아 2019.02.01

 

틱택토(Tic-Tac-Toe) 게임은 가로세로 3칸씩 총 9칸으로 이뤄진 사각형 판에서 두 사람이 하는 게임이다. 두 플레이어는 번갈아가며 한 사람은 검은색, 다른 한 사람은 흰색 돌을 빈 칸에 놓고, 행과 열 또는 대각선에 자기 돌 3개를 놓으면 승리하고 경기를 멈춘다. 회전하거나 대칭했을 때 진행이 같아도 다른 경기로 생각한다. 

 

 

 

 

[문제]

 

1 두 플레이어가 돌을 무작위로 놓을 때 가능한 경기의 수를 구하여라.  

2 위 문제에서 처음 시작한 플레이어가 이긴 경기의 수를 구하여라.   

3 두 플레이어가 최선의 수를 두어 진행할 때, 진행 수순을 구하여라.

 

 

※알립니다※

muse 친구의 풀이가 최종 정답으로 확인되면서

26번 문제도 '해결'입니다!

 

  •  
    EulerD Lv.1 2019.02.01

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

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

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

    댓글 작성하기 좋아요0 댓글수3
    •  
      muse Lv.1 2019.02.01

      글쎄요. 제가 생각할 때는 

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

      2. 같은 틱택토라도 순서가 다르면 다른 것으로 취급.

       

      인 것 같습니다.

      좋아요0
    •  
      muse Lv.1 2019.02.01

      수학동아에서 정확한 정의를 알려주지 않는 한은 풀기 힘들 것 같습니다.

      좋아요0
    •  
      승민짱 Lv.1 2019.03.19

      네 EulerD님 해석이 맞는거 같네요 

      (회전하거나 대칭했을 때 진행이 같아도 다른 경기로 생각한다) 부분에서 다른 돌리거나 뒤집어서 다르면 다른 경기라네요

      그리고 누가 먼저 하는지는 상관이 없나요???

      좋아요1
  •  
    EulerD Lv.1 2019.02.01

    #1

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

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

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

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

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

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

     

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

    댓글 작성하기 좋아요0 댓글수2
    •  
      EulerD Lv.1 2019.02.01

      계산을 어떻게 할 지 계획해보겠습니다.

      각각의 case에 대해 고려해야 할 상황은 나머지 말들(제가 올린 사진에서는 일부 말들만 그려져 있습니다)과, 회전, 돌 놓는 순서입니다.

      아직 문제에서 회전을 어떻게 처리해야하는지 잘 모르겠습니다.(문제 이해가 잘 안됩니다)

      일단은 회전, 대칭했을때 같은것은 같은 배치로 고려하는게 조금 더 편할 지도 모르겠습니다.

      좋아요0
    •  
      EulerD Lv.1 2019.02.01

      이 방법으로 계산하면 2번도 동시에 해결할 수 있겠지요??

      좋아요0
  •  
    EulerD Lv.1 2019.02.01

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

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

    댓글 작성하기 좋아요0 댓글수3
    •  
      EulerD Lv.1 2019.02.01

      일단 알려진 바로는 시작플레이어가 귀에 놓는 것이 유리하고

      그다음 플레이어는 중앙에 놓는 것이 유리하다고 알고있습니다.

      좋아요0
    •  
      EulerD Lv.1 2019.02.01

      참고할 만한 사진들입니다.(출처: Wikimedia)

      좋아요1
    •  
      가u스 Lv.5 2019.02.02

      이것들이 다 뭔가여??

      좋아요0
  •  
    muse Lv.1 2019.02.01

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

    댓글 작성하기 좋아요0 댓글수4
    •  
      muse Lv.1 2019.02.01

      문제가 상당히 모호하여서 무엇을 의미하는지 정확히 모르겠습니다.

      돌리거나 뒤집어서 같은 것을 서로 다른 보드라고 보았을 때:

      1) 두 플레이어가 무작위로 돌을 놓을 때 경기 중 가능한 배치의 개수(초기 상태 포함): 549946

      2) 두 플레이어가 무작위로 돌을 놓아 경기가 종료되었을 때 가능한 배치의 개수: 255168

      3) A가 이긴 경우의 수: 131184

      4) B가 이긴 경우의 수: 77904 

      5) 무승부인 경우의 수: 46080

       

      돌리거나 뒤집어서 같은 것을 서로 같은 보드라고 보았을 때:

      1) 68752

      2) 31896

      3) 16398

      4) 9738

      5) 5760

       

      이 안에 문제 출제자가 의도한 답이 있겠죠?

      좋아요0
    •  
      muse Lv.1 2019.02.01 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      EulerD Lv.1 2019.02.01

      프로그래밍으로 푸신건가요?

      좋아요0
    •  
      muse Lv.1 2019.02.01

      네.

      좋아요0
  •  
    muse Lv.1 2019.02.01

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

    댓글 작성하기 좋아요0 댓글수1
    •  
      EulerD Lv.1 2019.02.01

      어떤 수 이후에 무작위로 두었을때 이길 확률이 가장 높은 것???

      좋아요0
  •  
    인천 오일러 Lv.1 2019.02.01

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    muse Lv.1 2019.02.01

    답은 아래와 같습니다.

    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)

     

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

     

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    김우현 기자 Lv.4 2019.02.01

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    muse Lv.1 2019.02.01

    흥미롭군요.

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

    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;
    }
     

    댓글 작성하기 좋아요0 댓글수1
    •  
      인천 오일러 Lv.1 2019.02.01

       가정이 굉장히 흥미롭습니다. 저도 다른 흥미로운 가정을 세워보고 싶네요.

      좋아요0
  •  
    아인수타인 Lv.6 2019.02.02

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

    댓글 작성하기 좋아요1 댓글수0
  •  
    김우현 기자 Lv.4 2019.02.02

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

    댓글 작성하기 좋아요0 댓글수4
    •  
      3dasdd Lv.1 2019.02.08

      김우현 기자님 수학동아 오류 제보를 어디에다 해야 될지 모르겠어서 여기 올리겠습니다 이제서야 봤는데 2019년 2월호 83p에 3번째 시어핀스키 카펫이 잘못 나와있는 것 같아요 한번 확인해주실수 있나요? 감사합니다

      좋아요0
    •  
      아인수타인 Lv.6 2019.02.09

      어? 그러네요? 3단계에 한가운데가 파란색으로 꽉 채워야 하지 않나요?

      좋아요0
    •  
      김우현 기자 Lv.4 2019.02.09

      제보 감사합니다.

      담당 기자에게 연락해 확인해 보겠습니다!  

      좋아요0
    •  
      최기자 Lv.3 2019.02.12

      안녕하세요!

      확인해 보았습니다. 그림이 잘못 그려진 것 맞네요~. 죄송합니다. 한 가운데가 크게 파란색으로 칠해진 것이 맞습니다. 정정하겠습니다~!

      좋아요0
  •  
    21세기오일러 Lv.6 2019.02.02

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    muse Lv.1 2019.02.02

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    아인수타인 Lv.6 2019.02.04

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    Cantor Lv.1 2019.02.11

           

    1 9 6

    4 2 5

    7 8 3

    댓글 작성하기 좋아요0 댓글수0
  •  
    김우현 기자 Lv.4 2019.02.12

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

    댓글 작성하기 좋아요0 댓글수2
    •  
      sincostan Lv.5 2019.02.28

      그런데 확인하는 거 맞나요? 왜 이렇게 오래 걸리지?

      좋아요0
    •  
      김우현 기자 Lv.4 2019.02.28

      멘토님이 일부 풀이는 교수님께서 판단할 필요가 있다는 의견을 보내왔습니다. 

      고로 교수님께 확인 요청 드릴게요~smiley

      좋아요0
  •  
    sincostan Lv.5 2019.02.12

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    김우현 기자 Lv.4 2019.03.04

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    muse Lv.1 2019.03.21

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

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

    댓글 작성하기 좋아요0 댓글수4
    •  
      code Lv.1 2019.03.22

      (바쁘신가 봐요)

      좋아요1
    •  
      김우현 기자 Lv.4 2019.03.25

      검토가 늦어져 죄송합니다. 다시 한 번 요청 드렸어요!

      새학기가 시작되서 그런지 교수님께서 무척 바쁘신 것 같아요.crying

      좋아요0
    •  
      김우현 기자 Lv.4 2019.04.14

      다음 주 중에 최종 정답 여부가 나올 예정! 오래 기다려줘서 고마워요!!crying

      좋아요0
    •  
      김우현 기자 Lv.4 2019.04.15

      마침내 검토가 끝났습니다~. muse 친구가 교수님의 의도하신대로 프로그래밍을 이용해 잘 풀어줬네요. 

      대한수학회 26번 문제도 '해결'입니다!

      좋아요0