“20 질문”알고리즘을 어떻게 구현할 수 있습니까? 20Q 전자 게임이 어떻게 작동 했는지

어린 시절부터 20Q 전자 게임이 어떻게 작동 했는지 궁금 했습니다. 대상, 사물 또는 동물 (예 : 감자 또는 당나귀 )을 생각합니다. 그런 다음 장치는 다음과 같은 일련의 질문을합니다.

  • 빵 한 덩어리보다 큽니까?
  • 야외에서 발견됩니까?
  • 레크리에이션에 사용됩니까?

각 질문에 대해 yes , no , maybe 또는 unknown에 대답 할 수 있습니다 . 나는 항상 그것이 거대한 중첩 조건 ( if-statements)으로 작동한다고 상상했습니다 . 그러나 프로그래머에게는 복잡하기 때문에 설명이 될 것 같지 않습니다.

그러한 시스템을 어떻게 구현할 수 있습니까?

답변

나는 20Q가 그것을 어떻게 구체적으로했는지 모르지만 20 개의 질문으로 구성된 게임을 구현하는 방법에 대한 많은 정보가 있습니다 .

이 문제를 해결하는 방법에는 여러 가지가 있지만 한 가지 방법을 설명하겠습니다. 이러한 게임은 일종의 의사 결정 트리를 구현할 수 있습니다 . 20Q와 같은 전자 게임의 경우이 트리는 사전 계산되어 트래버스하기가 매우 쉽습니다. 학습 결정 트리 를 사용 하여 사용자가 요구하는 것을 추측 할 수없는 경우 게임이 질문 끝에 새로운 객체를 받아 들일 수있는 방법이 있습니다 .

질문이 일련의 예 또는 대답이 아닌 경우 이진 트리가 생깁니다. 각 노드는 질문이며 잎은 답입니다. 알 수 없거나 확실하지 않은 질문에 대답하면 하위 노드를 결합하고 질문에 대한 일련의 질문을 작성하여 가능한 답변을 더 많이 제거 할 수 있습니다.

여기에 이미지 설명을 입력하십시오

기본적으로 이것은 프로세스입니다.

  1. 전체 객체 목록으로 시작하십시오. 이것들은 모두 똑같이 시작될 수 있거나 테스트에서 객체가 선택되었을 가능성에 따라 정렬 될 수 있습니다.
  2. 의사 결정 트리의 첫 번째 질문부터 시작하십시오. 질문 대기열로 밀어 넣습니다.
  3. 대기열 상단에 질문하십시오.
  4. 프로세스 응답 :
    1. 예 / 아니오 답변은 질문에 따라 각 답변에서 미리 결정된 확률을 제거 / 추가합니다.
    2. “아마도”대답은 미리 결정된 양의 “예”의 일부를 제거 / 추가합니다.
    3. “알 수 없음”은 확률을 변경하지 않습니다
  5. “알 수 없음”또는 “아마도”응답은 다음 노드 질문 모두를 질문 대기열로 푸시합니다. “예”또는 “아니오”응답은 각 예 / 아니오 노드를 질문 대기열에 추가합니다.
  6. 질문이 없거나 단일 답변의 확률이 사전 정의 된 “확실성”임계 값을 초과 할 때까지 3 단계로 이동하십시오.
  7. 가장 가능성이 높은 답변을 제공하십시오.

트리 생성은 아마도 다른 질문의 주제 일 것입니다. 그러나 기본적으로 답변을 가능한 많이 나누는 질문을 선택합니다. 가장 많은 수의 질문을 가장 빨리 다룰 수 있도록 처음에 가장 똑같이 질문을 나누는 질문을 넣으십시오.

답변

간단한 대답은 휴대용 게임 20Q가 http://20Q.net에 있는 인공 지능으로 만들어 졌다는 것 입니다. 20Q.net에서는 게임이 모든 게임에서 배운다는 점을 제외하고는 장난감과 유사하게 20 가지 질문 게임의 다른 버전을 재생할 수 있습니다. 핸드 헬드 장난감은 동일한 신경망 알고리즘을 사용합니다. 신경망은 질문뿐만 아니라 추측 할 질문을 선택합니다. 이 접근법은 AI가 배운 것과는 다른 질문에 대답하더라도 AI가 종종 올바르게 추측 할 수 있음을 의미합니다. 또 다른 장점은 동일한 것을 생각하더라도 게임이 매 게임마다 다르게 질문을한다는 것입니다.

고전 영어 게임 (동물, 야채, 미네랄)의 알고리즘과 신경망은 1988 년 Robin Burgener에 의해 만들어졌습니다. . . 나를.

질문 주셔서 감사합니다.

답변

“20q code”를 봤는데 이것을 찾았습니다 : http://mosaic.cnfolio.com/B142LCW2008A197

이 버전은 동물만을위한 것이지만 실제 20 가지 질문은 아마도 비슷한 알고리즘을 가지고있을 것입니다.

다음은 내가 링크 한 코드에 대한 간략한 개요입니다
. 프로그램에 하드 코딩 된 여러 가지 답변이 있습니다. 그런 다음 몇 가지 TRUE 또는 FALSE 속성이 할당됩니다.

#define ANIMALS_LIST      "daddylonglegs bee penguin eagle giraffe octopus tiger elephant jellyfish bull \nparrot dolphin python crocodile cat leopard monkey zebra sheep rat \nowl spider frog polarbear snail tortoise rabbit salmon rhino fox"
#define MAMMALS                    "0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1"
#define FLYING_ANIMALS             "1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
#define WATER_ANIMALS              "0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0"
#define BEAK                       "0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0"
...

보시다시피 꿀벌은 포유류가 아니지만 날아갑니다.

각 그룹마다 배열이 있습니다 :

int   mammals[ TOTAL_ANIMALS ] = { 0 };
int   flying_animals[ TOTAL_ANIMALS ] = { 0 };
int   water_animals[ TOTAL_ANIMALS ] = { 0 };
...

각 질문을 할 때 :

  askUserQuestion( guesses, "\nQuestion %d: Is your animal a mammal? \n", mammals );

이 프로그램은 적절한 범주의 정의를 검토하고 TRUE 또는 FALSE 값과 질문에 대한 입력 된 예 또는 아니요 대답을 기반으로 생각할 가능성이 가장 높은 동물을 추적합니다.

이것은 다음에서 수행됩니다.

void askUserQuestion( int guessNumber, char* question, int* animalData );

답변

거대한 의사 결정 트리 또는 하드 코딩 된 if / else 문이 아닙니다. 발명가 인 Robin Burgener 는 그의 2005 년 특허 출원에서 자신의 알고리즘 을 완전히 문서화했습니다 . 독창적으로 간단합니다.

답변