Python을 사용하여 Landlords의 최종 게임을 해결하는 요령을 가르쳐주세요.

零下一度
풀어 주다: 2017-07-02 10:47:21
원래의
2912명이 탐색했습니다.

Doudizhu는 모든 사람에게 친숙할 것입니다. 다음 기사에서는 Python을 사용하여 Doudizhu의 최종 게임을 해독하는 방법에 대한 관련 정보를 주로 공유합니다. 기사의 소개는 매우 자세하며 모든 사람에게 필요한 참고 자료와 학습 가치가 있습니다. 친구 여러분, 아래를 살펴보겠습니다.

머리말

모두가 집주인을 플레이해 본 적이 있을 것이라 생각하므로 규칙은 다시 도입되지 않습니다.

친구 서클에서 본 최종 게임 사진으로 바로 이동:

처음 이 질문을 봤을 때 농부의 승리 전략을 찾았다고 생각할 때마다 수동으로 해결하려고 했습니다. 결국 농민들은 탈출할 수 없다는 사실이 밝혀졌다. 수동 크래킹은 모든 가능성을 소진할 수 없으므로 이 문제를 해결하는 데 도움이 되는 코드만 사용할 수 있습니다.

이 기사에서는 코드를 통해 이러한 문제를 해결하는 방법을 간략하게 설명합니다. 마지막에는 엔드게임의 최종 결과가 발표되고 코드는 모두가 불평할 수 있도록 오픈 소스로 공개됩니다.

minimax

코드의 핵심 아이디어는 minimax입니다. 미니맥스(Minimax)는 미니(mini)와 최대(max) 두 부분으로 나눌 수 있는데, 이는 각각 최소와 최대를 뜻한다.

직관적 이해란 무엇인가요? A와 B 두 사람이 체스를 두는 것과 비슷합니다. A는 이제 N 포인트에서 체스를 움직일 수 있으며 A의 움직임에 대한 보드 평가 점수가 가장 높지만 B의 차례가 되면 확실히 그 방향으로 움직일 것입니다. A에게 가장 불리합니다. Go로 인해 A의 다음 단계는 B가 설정한 궤적을 따라야 하며 첫 번째 단계에서 A가 이 단계에서 추정한 가장 높은 보드 점수에 도달할 수 없습니다.

카드 게임에서도 마찬가지입니다. 집주인이 어떻게 처리해도 농부가 카드를 얻을 수 없다면 농부가 승리할 전략이 있다고 말할 수 있습니다. 그렇지 않으면 농부가 패하게 됩니다. .

핵심 논리

우리는 functionhand_out을 사용하여 사람의 카드 놀이 과정을 시뮬레이션할 수 있습니다. 실제 생활에서 어떤 사람이 카드를 플레이하려면 자신의 손에 있는 모든 카드(me_pokers)를 알아야 하며, 이전 손에 사용된 카드(last_hand)도 알아야 합니다. 이 기능을 사용하여 두 사람의 플레이를 시뮬레이션하려면 상대의 현재 카드인 적_포커도 모두 알아야 합니다.

함수의 반환 값은 my_pokers가 카드를 사용할 차례가 되었을 때 내가 이길 수 있는지 여부입니다. 승리할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.


def hand_out(me_pokers, enemy_pokers, last_hand)
로그인 후 복사

내 차례가 되었을 때 내 손에 있는 카드가 모두 나오면 내가 이겼다는 것을 즉시 알 수 있지만, 상대방의 카드가 모두 나오면 내가 승리했다고 가정해 보세요. 그렇지 않다면 나는 실패했습니다.


if not me_pokers:
 return True
if not enemy_pokers:
 return False
로그인 후 복사

이제 내가 카드를 쓸 차례이기 때문에 먼저 지금 할 수 있는 손 조합을 모두 알아야 해요. 참고: 이 조합에는 확인(즉, 플레이하지 않음) 전략이 포함됩니다.


all_hands = get_all_hands(me_pokers)
로그인 후 복사

이제 가능한 모든 손 조합을 반복해 보겠습니다.

우선 상대가 마지막 핸드에 어떤 카드를 썼는지 알아야 합니다.

  • 상대방이 이전 핸드에서 체크를 선택했거나 이전 핸드에 카드가 없었다면 이번 라운드에 체크를 해서는 안 되지만 어떤 카드든 플레이할 수 있습니다.

  • 상대가 다음 카드를 플레이한 경우 이전 패에 있는 카드를 사용하려면 그보다 더 큰 카드를 사용하거나 이번 라운드에서 카드를 직접 확인하도록 선택해야 합니다(카드를 사용하지 않고)

핵심은 카드를 사용하거나 선택한 후입니다. 카드를 확인하려면 재귀 호출을 사용하여 상대방의 다음 행동을 시뮬레이션해야 합니다. 상대방의 다음 카드 플레이가 이길 수 없다면 이번에는 내 카드 플레이가 확실히 이길 것입니다. 그렇지 않으면 내가 선택한 모든 카드 플레이에 대해 상대방이 이길 수 있다면 나는 패배할 것입니다.

전체 코드는 다음과 같습니다.


def hand_out(me_pokers, enemy_pokers, last_hand, cache):
 if not me_pokers:
  # 我全部过牌,直接获胜
  return True
 if not enemy_pokers:
  # 对手全部过牌,我失败
  return False
 # 获取我当前可以出的所有手牌组合,包括过牌
 all_hands = get_all_hands(me_pokers)
 # 遍历我的所有出牌组合,进行模拟出牌
 for hand in all_hands:
  # 如果上一轮对手出了牌,则这一轮我必须要出比对手更大的牌 或者 对手上一轮选择过牌,那么我只需出任意牌,但是不能过牌
  if (last_hand and can_comb2_beat_comb1(last_hand, hand)) or (not last_hand and hand['type'] != COMB_TYPE.PASS):
   # 模拟对手出牌,如果对手不能取胜,则我必胜
   if not hand_out(enemy_pokers, make_hand(me_pokers, hand), hand, cache):
    return True
  # 如果上一轮对手出了牌,但我这一轮选择过牌
  elif last_hand and hand['type'] == COMB_TYPE.PASS:
   # 模拟对手出牌,如果对手不能取胜,则我必胜
   if not hand_out(enemy_pokers, me_pokers, None, cache):
    return True
 # 如果之前的所有出牌组合均不能必胜,则我必败
 return False
로그인 후 복사

Build

위의 핵심 로직이 명확해지면 크래커를 만드는 것은 매우 간단해집니다.

우선 카드의 크기를 나타내기 위해 숫자를 사용해야 합니다. 여기서는 3을 나타내기 위해 3을 사용하고, J를 나타내기 위해 11을 사용하고, Q를 나타내기 위해 12를 사용하는 등...

두 번째로, 우리는 다음과 같이 해야 합니다. 손에 있는 모든 카드 조합을 찾으려면 여기에 get_all_hands 함수가 필요합니다. 구체적인 구현은 비교적 복잡하지만 매우 간단하므로 여기서는 자세히 설명하지 않겠습니다. get_all_hands函数,具体实现比较繁琐但是很简单,就不在此赘述。

然后,我们还需要一个牌力判断函数can_comb2_beat_comb1(comb1, comb2) ,这个函数用于比较两组手牌的牌力,看是否comb2可以击败comb1。唯一需要注意的一点,在斗地主的规则中,除了炸弹外,其他所有牌力均等,只有牌型一样时才能去比较。

最后,我们需要一个模拟出牌函数make_hand(pokers, hand)

그런 다음 카드 강도 판단 기능 can_comb2_beat_comb1(comb1,comb2)도 필요합니다. 이 기능은 빗2가 빗1을 이길 수 있는지 확인하기 위해 두 세트의 손의 카드 강도를 비교하는 데 사용됩니다. 주의해야 할 유일한 점은 Landlord의 규칙에서 폭탄을 제외한 다른 모든 카드는 동일한 유형의 카드만 비교할 수 있다는 것입니다. 🎜🎜마지막으로 포커를 손에 들고 패를 플레이한 후 남은 패를 알아내는 데 사용되는 시뮬레이션된 카드 플레이 함수 make_hand(pokers, hand)가 필요합니다. 구현도 매우 간단합니다. 사용된 카드를 제거하기만 하면 됩니다. 🎜

효율성

카드 한 벌에 가능한 손의 수가 엄청나게 많기 때문에 재귀 분기의 수도 엄청납니다. 따라서 시간 오버헤드는 매우 커서 팩토리얼 수준 O(N!)입니다. 스털링의 공식에 따르면 대략 O(N^N)입니다.

반복되는 카드가 많아 반복 재귀 호출이 많아질 수 있기 때문입니다. 따라서 캐시를 추가하면 효율성이 크게 향상될 수 있습니다.

즉, 우리 패, 적 패, 이전 라운드 패의 설명(str(me_pokers)+str(enemy_pokers)+str(last_hand))이 핵심이고, 그 결과가 캐시 사전에 저장됩니다. 다음에 동일한 상황이 발생하면 다시 계산을 반복할 필요 없이 캐시 사전에서 직접 검색할 수 있습니다. 시간 복잡도는 지수 O(C^N)으로 최적화됩니다.

Result

코드 계산 결과, 농민에게는 승리 전략이 없습니다. 즉, 집주인이 노는 방법을 아는 한 농민은 이길 수 없습니다. 클래스 결속이 벌써 이렇게 된 건지...

오픈 소스

코드는 Github: doudizhu_solver에 있거나 MIT 라이선스에 따라 로컬로 다운로드하여 원하는 대로 플레이할 수 있습니다.

위 내용은 Python을 사용하여 Landlords의 최종 게임을 해결하는 요령을 가르쳐주세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿