U E D R , A S I H C RSS

ProjectD/설계문서

  • 2~4인이 함께 즐길 수 있는 보드게임이다.
  • 0~11, 조커(-) 가 적힌 각 13개의 블록이, 흰색과 검정색 총 26개가 있다.
  • 처음 게임을 시작하면 블록을 뒤집어 둔 채, 랜덤하게 4개씩 가져간다. (단, 4 인 플레이에서는 3개씩)
  • 자신에게만 블록의 숫자가 보이게 세워놓되, 블록을 정렬하는 규칙이 있다.
    • 본인 시점으로, 왼쪽에서 오른쪽으로 숫자가 점점 커져야 한다.
    • 같은 숫자라면, 검정색이 흰색의 왼쪽에 온다.
    • 조커는 어떤 자리에도 올 수 있다.
  • 블록 정렬을 마치면, 턴의 순서를 정한 후 게임을 시작한다.
  • 본인의 턴이 시작되면 남아있는 블록 중에서 한 개를 가져오고, 정렬하는 규칙 에 맞게 배치한다.
  • 주어진 정보들을 이용해 상대방의 블록의 숫자를 추측한다. 위치와 숫자를 정확 하게 맞혀야 한다.
  • 상대방의 블록 숫자를 맞혔다면, 해당 블록을 모두에게 오픈시킨다.
  • 최소 한 번은 추측을 해야 하며, 이 때 두 가지 경우가 생긴다.
    • 추측이 틀렸다면, 턴이 시작할 때 가져왔던 자신의 블록을 오픈시키고 다음 사람에게 턴을 넘긴다.
    • 추측이 맞았다면, 횟수에 제한 없이 계속해서 맞히거나, 턴을 넘길 수 있다. 물론 맞혀나가다가 한 번이라도 틀린다면 자신의 블록을 오픈시켜야 한다.
  • 한 사람을 제외한 모든 플레이어의 블록이 오픈될 때까지 진행한다.

알고리즘

  • 4개의 블록을 받아서 배치
    • 만약 블록 class(혹은 struct)를 사용해 index와 color를 분리한다면 일 반적인 정렬 알고리즘으로는 정렬이 힘들다. (검정/하양의 숫자가 같기 때문)
      • 본인의 블록 개수가 8개로 고정된 前다빈치코드에서는 블록 생성과 배분을 동시에 했기에 가능했지만, 블록 개수가 가변적인 新다빈치코드는 많은 생 각이 필요할 것으로 생각됨.
    • idea 1 : inx = (index*10) + (bool)isWhite; 라면
      inx/10 == index \\ inx%2 == color 가 됨.
  • 본인 차례에 패를 뽑아 맞는 자리에 배치
    • 배치 자체는 위에서 정할 알고리즘을 재실행한다면 문제가 되지 않음.
    • 중요한 점 1 : 뽑은 패의 중요성
      • 상대방의 패를 맞힐 때 계속 맞힐 지의 여부가, 상대방의 패를 맞힐 확률과 뽑은 패의 중요성을 양 쪽 다 고려해야 하기 때문.
      • ex) 흰색 10이 오픈된 상태에서 흰색 11을 뽑았을 때, 사실상 이 패는 모두가 추측할 수 있는 패이므로 아무리 상대방의 패를 맞힐 확률이 낮아 도 질러보는 것이 나음.
      • 중요하지 않은 패 : 오픈된 블록과 틀렸던 블록의 정보만으로도 100% 숫 자를 유추해 낼 수 있는 패
        • 중요하지 않은 패일 경우 확률이 낮아도 질러 봄.
        • 자리로 중요성 판단 : 간단하게 구현 완료
          • 오픈된 블록 & 틀렸던 블록의 정보를 통한 판단은 구현 필요
      • 중요한 패 : 일반적으로 조커 + 만약 오픈되면 다른 패들까지도 줄줄이 오픈되는 위험한 패. (ex) 흰색 0 1 2 가 있는 상태에서 흰색 3)
        • 이에 대한 알고리즘은 더 생각해 보도록 함.
        • 중요한 패일 경우 상대방의 패를 맞힐 확률이 일정 확률을 넘는 것이 아 니면 진행하지 않음.
    • 중요한 점 2 : 조커를 뽑았을 때의 배치
      • 일반적으로는 이웃한 블록 값의 차가 가장 큰 지점에 배치.
      • 적당히 구현 완료
  • 상대방의 패를 유추
    • 기본적인 알고리즘은 前다빈치코드에서 인용하도록 한다. (추측판 사용)
      • 자신의 패에 의한 제거
      • 블록 위치에 의한 제거
        • 블록 개수에 따라 가변적으로 식이 변해야 함.
      • 이미 틀렸던 정보에 의한 제거
      • 블록 색깔에 의한 제거
      • 최소 수에 의한 제거
      • 오픈된 블록에 의한 제거
      • 조커 유추
        • 추가된 부분
    • 다빈치 코드는 확률 게임이다.
      • 어떤 자리에 3과 조커 두 개만이 들어갈 수 있다고 해서 3이 들어갈 확률 이 50%가 되지는 않는다. 조커는 다른 자리에도 들어갈 수 있기 때문.
        블록별 확률 가중치를 잘 계산해야 좋은 AI가 나올 것.
      • idea : 조커가 들어갈 수 있는 모든 불록 수를 찾는다.
        예를 들어 10개라고 가정하면, 조커일 확률은 10%로 설정하고, 아까와 같 은 상황에서 3이 나올 확률은 90%로 한다.
      • 실제로 게임을 플레이하면서 느낀 점은 조커에 그렇게까지 큰 가중치를 두 지 않는다는 것. 어떤 블록 중 100% 조커가 있다! (ex) 흰색 3과 흰색 5 사이에 흰색 블록이 2개가 있는 상황) 라는 상황만 아니라면 조커는 사 실상 이론적인 ‘가능성’ 으로만 존재할 뿐이다.
        • 이 ‘어떤 블록 중 100% 조커가 있다!’ 라는 상황을 판별하는 알고리즘 이 조커와 관련된 알고리즘 중 가장 중요하지 않을까 하는 생각.

추가사항

  • 블록이 100% 랜덤으로 배정되는 것이 아니라, 색깔은 선택할 수 있으므로 이 부분에 대한 고려 필요.

기타사항

  • Block의 배열을 링크드리스트로 하는 것이 어떨까요... 블록 삽입이 쉬워서 괜찮을 듯 합니다 - 최다인
  • 이 기회에 머신 러닝를 배워보는것도 나쁘지 않을듯 합니다. 계속해서 컴퓨터와 싸울수록 사용자의 패턴을 파악하여 대응하거나 더 나은 전략을 배워가는 AI를 만드는것도 나쁘지 않을것 같네요. - 안혁준
    • 상상 속으로만 생각해보고 불가능할 거라고 생각했는데 머신 러닝이라는 분야가 있었군요 ㅎㄷㄷ 마침 연관된 자료 받은 게 약간 있으니 공부해봐야겠어요. 감사합니다 - 최다인


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:24:04
Processing time 0.0326 sec