MiniMax 알고리즘

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

누구나 궁금해 할 것입니다. Argh, 또 다른 MINIMAX 알고리즘입니다.

왜 필요합니까? 게임을하자 체스 또는 tic-tac-toe 우리는 종종 연산 게임에서이기려면

설명

많은 경우 우리는

• 상대방의 움직임을 해독 할 수 있었다
• 최적으로 플레이 할 수있었습니다

MiniMax Algorithm은 우리에게 딱 맞는 기능을 제공합니다!

XNUMX 인 게임의 검색 트리에는 두 종류의 노드가있을 수 있습니다.

• MAX 노드
  • 이동을 나타내는 노드입니다. 당신은 할 수 있습니다
    • 위쪽을 가리키는 삼각형으로 표시
    • 이러한 노드의 목표 : 노드 아래의 하위 트리 값 최대화
    • 최대 노드 값 : 최대 값을 가진 자식 값
• MIN 노드
  • 이들은 움직임을 나타내는 노드입니다. 당신의 상대 수
    • 아래쪽을 가리키는 삼각형으로 표시
    • 이러한 노드의 목표 : 노드 아래의 하위 트리 값 최소화
    • 최소 노드 값 : 최소 값을 가진 자식 값

이 중 많은 부분이 이해가되지 않을 수 있습니다.

예를 들어 이해합시다

아래 그림과 같이 값이있는 8 개의 초기 상태가 있다고 가정합니다.

• 처음에는 두 노드 각각의 최대 값을 취합니다.
  • Ex-From 3과 15에서 우리는 최대를 찾습니다
  • 이 최대 값을 최대 노드 (위를 가리키는 삼각형)에 넣습니다.
• 최대주기가 완료되면 최대 노드에서 최소값을 가져옵니다.
  • 예-15와 10에서 우리는 10을 취합니다
  • 이 min 값을 min 노드 (아래쪽을 가리키는 삼각형)에 넣습니다.
• 값에 도달 / 완료 될 때까지 계속 반복합니다.

가능한 모든 움직임을 역 추적하여 그에 따라 값을 선택하고 결론에 도달하는 결정을 내립니다.

핀

코드 스 니펫으로 더 잘 이해합시다

Minimax 알고리즘을위한 Java 코드

import java.io.*;
import java.util.*;
public class minimax
{
  public static int decide(int cur,int index,boolean max,int weight[],int height)
  {
    int num=0;
    //If we reach a leaf node
    if(cur==height)
      return weight[index];
    //If the node is a max one we find the max from sub-nodes
    if(max)
    num=Math.max(decide(cur+1,index*2,false,weight,height),decide(cur+1,index*2+1,false,weight,height));
      //If it is a min node we minimize the value under the sub-tree
      else
      num=Math.min(decide(cur+1,index*2,true,weight,height),decide(cur+1,index*2+1,true,weight,height));
      return num;
  }
  public static void main(String args[])
  {
    int scor[] = {3, 15, 2, 10, 12, 5, 2, 23};
    int n= scor.length;
    int h= (int)(Math.log(n) / Math.log(2));
    int a=decide(0,0,true,scor,h);
    System.out.println(a);
  }
}

C ++ 코드 Minimax 알고리즘 용

#include<iostream>
#include<cmath>
using namespace std;
    int max(int a,int b)
    {
    	if(a>b)
    		return a;
    	else
    		return b;
    }
    int min(int a,int b)
    {
    	if(a>b)
    		return b;
    	else
    		return a;
    }
    /*int log2(int n) 
    { 
    if(n==1)
    	return 0;
    else
    	return(log2(n/2));
    }*/
    int decide(int cur,int index,bool max_dec,int weight[],int height)
  {
    int num;
    //If we reach a leaf node
    if(cur==height)
      return weight[index];
    //If the node is a max one we find the max from sub-nodes
    if(max_dec)
    num=max(decide(cur+1,index*2,false,weight,height),decide(cur+1,index*2+1,false,weight,height));
      //If it is a min node we minimize the value under the sub-tree
      else
      num=min(decide(cur+1,index*2,true,weight,height),decide(cur+1,index*2+1,true,weight,height));
      return num;
  }
  int main()
  {
    int scor[] = {3, 15, 2, 10, 12, 5, 2, 23};
    int n= 8;
    int h= log2(n);
    int a= decide(0,0,true,scor,h);
    cout<<a;
    return 0;
  }

12

복잡성 분석

시간 복잡도 = O (h * m)

어디에

h = 생성 된 나무의 높이 / 깊이

m = 각 지점에서의 이동 횟수

따라서 minimax 알고리즘과 작동 방식에 대한 소개였습니다!

참조

몇 가지 다른 게시물 확인

그래프에 대한 BFS (Breadth First Search)