정보가 불완전한 카드 게임에 대한 미니맥스 검색 사용
https://stackoverflow.com//questions/12666119
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 컴퓨터 프로그램이 카드 게임을 하도록 만들기 위해 minimax 검색(알파-베타 가지치기 포함) 또는 오히려 negamax 검색을 사용하고 싶습니다.
카드 게임은 실제로 4명의 플레이어로 구성됩니다.그래서 미니맥스 등을 사용할 수 있도록 게임을 '나'와 '타인'으로 단순화합니다.각 "이동" 후에는 게임 자체에서 현재 상태의 평가를 객관적으로 읽을 수 있습니다.4명의 플레이어가 모두 카드를 배치하면 가장 높은 사람이 모두 승리하며 카드의 가치도 계산됩니다.
다른 3명의 플레이어 간의 카드 분배가 정확히 어떻게 이루어지는지 모르기 때문에 자신의 카드가 아닌 카드를 사용하여 가능한 모든 분배("세계")를 시뮬레이션해야 한다고 생각했습니다.당신은 12장의 카드를 가지고 있고 나머지 3명의 플레이어는 총 36장의 카드를 가지고 있습니다.
그래서 내 접근 방식은 이 알고리즘입니다. player 프로그램이 움직임을 찾아야 할 세 대의 컴퓨터 플레이어를 상징하는 1에서 3 사이의 숫자입니다.그리고 -player 상대방, 즉 다른 세 명의 플레이어가 모두 함께 있음을 나타냅니다.
private Card computerPickCard(GameState state, ArrayList<Card> cards) {
int bestScore = Integer.MIN_VALUE;
Card bestMove = null;
int nCards = cards.size();
for (int i = 0; i < nCards; i++) {
if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
int score;
GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
if (score > bestScore) {
bestScore = score;
bestMove = cards.get(i);
}
}
}
// now bestMove is the card to place
}
private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
ArrayList<Card> cards;
if (player >= 1 && player <= 3) {
cards = state.getCards(player);
}
else {
if (player == -1) {
cards = state.getCards(0);
cards.addAll(state.getCards(2));
cards.addAll(state.getCards(3));
}
else if (player == -2) {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(3));
}
else {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(2));
}
}
if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
if (player >= 1 && player <= 3) {
return state.getCurrentPoints(player); // player's points as a positive value (for self)
}
else {
return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
}
}
else {
int score;
int nCards = cards.size();
if (player > 0) { // make one move (it's player's turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // wenn Zug gültig ist
score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
return alpha;
}
else { // make three moves (it's the others' turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // if move is valid
for (int k = 0; k < nCards; k++) {
if (k != i) {
GameState futureStateLevel2 = futureState.testMove(cards.get(k));
if (futureStateLevel2 != null) { // if move is valid
for (int m = 0; m < nCards; m++) {
if (m != i && m != k) {
GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
if (futureStateLevel3 != null) { // if move is valid
score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
}
}
}
}
}
}
return alpha;
}
}
}
이것은 잘 작동하는 것처럼 보이지만 깊이가 1(depthLeft=1), 프로그램은 이미 평균 50,000개의 이동(배치된 카드)을 계산해야 합니다.물론 이것은 너무 많습니다!
그래서 내 질문은 다음과 같습니다
- 구현이 전혀 정확합니까?이런 게임을 시뮬레이션할 수 있나요?특히 불완전한 정보에 관해서는?
- 속도와 작업 부하 측면에서 알고리즘을 어떻게 개선할 수 있습니까?
- 예를 들어, 좋은 결과를 유지하면서 속도를 향상시키기 위해 가능한 이동 세트를 50%의 무작위 세트로 줄일 수 있습니까?
- 나는 찾았다 UCT 알고리즘 좋은 해결책이 될 것입니다 (아마도).이 알고리즘을 아시나요?구현하는 데 도움을 주실 수 있나요?
해결책
구현한 Minimax 검색은 불확실성이 너무 많은 게임에 대한 잘못된 접근 방식입니다.다른 플레이어 간의 카드 배포를 모르기 때문에 실제 카드 배포에서는 발생할 수 없는 게임을 검색하는 데 기하급수적인 시간이 소요됩니다.
내 생각에 더 나은 접근 방식은 다른 플레이어의 패에 대한 정보가 거의 또는 전혀 없을 때 좋은 플레이 규칙부터 시작하는 것입니다.같은 것들:
- 라운드에서 먼저 플레이하는 경우 라운드에서 승리할 가능성이 거의 없으므로 가장 낮은 카드를 사용합니다.
- 라운드에서 마지막으로 플레이하는 경우 라운드에서 승리할 가장 낮은 카드를 사용합니다.라운드에서 이길 수 없다면 가장 낮은 카드를 사용하세요.
프로그램이 처음에는 검색에 신경 쓰지 않고 다음 규칙을 따르도록 하세요. 다른 모든 플레이어도 이러한 경험적 방법을 사용할 것이라고 가정합니다. 프로그램은 각 라운드의 첫 번째와 마지막 플레이어가 어떤 카드를 사용하는지 관찰하면서 각 플레이어가 보유할 가능성이 있는 카드에 대한 정보 테이블을 구축할 수 있습니다.예:9가 이번 라운드에서 승리했을 수 있지만 플레이어 3은 해당 라운드를 플레이하지 않았으므로 9 이상의 카드가 없어야 합니다.각 플레이어의 손에 대한 정보가 수집됨에 따라 검색 공간은 결국 가능한 게임의 최소 최대 검색이 다음에 플레이할 카드에 대한 유용한 정보를 생성할 수 있는 지점으로 제한됩니다.
다른 팁
허용되는 답변이 실제로 포함되지 않는 세부 사항을 명확히하고 싶습니다.
많은 카드 게임에서는 카드를 모두 생성하는 대신 상대가 가질 수 있는 알려지지 않은 카드를 샘플링할 수 있습니다.가능한 각 핸드의 가능성에 가중치를 부여하기 위해 이 샘플링을 수행할 때 짧은 정장과 지금까지의 플레이에서 특정 카드를 보유할 확률과 같은 정보를 고려할 수 있습니다(각 핸드는 우리가 독립적으로 해결할 수 있는 세계입니다).그런 다음 완벽한 정보 검색을 사용하여 각 핸드를 해결합니다.이 모든 세계에서 가장 좋은 움직임은 종종 전체적으로 가장 좋은 움직임입니다. 몇 가지 주의 사항이 있습니다.
포커와 같은 게임에서는 이것이 잘 작동하지 않습니다. 게임은 숨겨진 정보에 관한 것입니다.손에 대한 정보를 숨기려면 행동의 균형을 정확하게 유지해야 합니다.
그러나 트릭 기반 카드 게임과 같은 게임에서는 이는 꽤 잘 작동합니다. 특히 새로운 정보가 항상 공개되기 때문입니다.정말 좋은 선수들은 모두가 갖고 있는 것이 무엇인지에 대한 좋은 생각을 가지고 있습니다.따라서 합리적으로 강력한 Skat 및 Bridge 프로그램은 이러한 아이디어를 기반으로 했습니다.
기본 세계를 완전히 해결할 수 있다면 그것이 가장 좋지만, 그렇게 할 수 없다면 minimax 또는 UCT를 사용하여 각 세계에서 가장 좋은 수를 선택할 수 있습니다.이 프로세스를 함께 혼합하려는 하이브리드 알고리즘(ISMCTS)도 있습니다.여기서 주장에 주의하세요.간단한 샘플링 접근 방식은 코딩하기가 더 쉽습니다. 더 복잡한 접근 방식보다 더 간단한 접근 방식을 시도해야 합니다.
불완전한 정보에 대한 샘플링 접근 방식이 언제 잘 작동했는지에 대한 추가 정보를 제공하는 몇 가지 연구 논문은 다음과 같습니다.
게임트리 검색에서 완벽한 정보 몬테카를로 샘플링의 성공 이해 (이 문서에서는 샘플링 접근 방식이 작동할 가능성이 있는 경우를 분석합니다.)
트릭 기반 카드 게임의 상태 평가, 추론 및 검색 개선 (이 문서에서는 Skat의 샘플링 사용에 대해 설명합니다.)
계산적으로 어려운 게임의 불완전한 정보 (이 문서에서는 Bridge에서의 샘플링에 대해 설명합니다.)
정보 세트 몬테카를로 트리 검색 (이 논문에서는 첫 번째 참조의 문제를 피하기 위해 샘플링과 UCT/Monte Carlo Tree Search를 병합합니다.)
허용되는 답변에서 규칙 기반 접근 방식의 문제점은 초기 규칙을 생성하는 데 필요한 것 이상으로 계산 리소스를 활용할 수 없다는 것입니다.게다가 규칙 기반 접근 방식은 작성할 수 있는 규칙의 힘에 따라 제한됩니다.검색 기반 접근 방식은 조합 검색의 힘을 사용하여 프로그램 작성자보다 훨씬 더 강력한 플레이를 생성할 수 있습니다.
