태그 보관물: python

Minimax Algorithm과 간단한 예제

Minimax algorithm은 체스나 장기, 틱택토 혹은 오목 처럼 두 명의 플레이어가 번갈아 가면서 턴을 주고받는 유한 제로섬 게임(Finite zero-sum game)에서 최적의 선택을 내리기 위해 사용 할 수 있는 결정 트리 탐색 알고 리즘이다. 다시말해, 내가 얻는 이득이 상대의 손실이 되고, 내가 보는 손실이 상대의 이득이 되는 구조에서, “상대방은 항상 자신에게 유리한 선택을 하고 나에게는 불리한 선택을 한다”는 가정하에 자기 자신의 손실을 최소화(minimize)하고 이득을 최대화(maximize)하는 전략을 찾는 것이다.

이 포스팅에서는 minimax algorithm의 개념을 이해하고 간단한 게임에 적용시켜 최적의 해법을 찾아내는 과정을 확인해 본다.

Max Player와 Min Player

Minimax 알고리즘에서는 두 플레이어를 각각 Max와 Min으로 정의한다.

  • Max Player (컴퓨터): 자신의 점수를 maximize하려는 플레이어.
  • Min Player (상대방): Max의 점수를 minimize하려는 플레이어.

이 그림은 Max와 Min 두 플레이어가 서로 턴을 바꿔가며 결정하는 예제를 단순화 해서 트리로 그린 것이다. 각 선택 들의 최종 결과 값이 3, 5, 2, 9로 귀결된다고 할 때, Min은 Max의 이득을 최소화 하는 결정을 선택을 하게 될 것이므로, 왼쪽 노드의 3과 5중에서는 3, 오른쪽 노드의 2와 9중에서는 2를 선택할 것이다. 그렇다면 Max 입장에서는 Min이 결정 할 3과 2중에 이득을 최대화 하는 3을 고르게 되는 것이다.

전체 트리 상에는 Max가 이 게임에서 얻을 수 있는 더 큰 이득인 5와 9가 있지만 이들은 Min에 의해 버려지게 될 것이므로, Max 입장에서는 3을 얻기위한 결정을 수행하는 것이 최적이라고 할 수 있다.

변형 Nim 게임에 적용

Nim game은 “베스킨라빈스31” 게임과 유사한 것인데 판에 올려진 물체(코인)을 1개, 2개 혹은 3개씩 돌아가면서 가져가서 결국 마지막 남은 하나를 가져가는 사람이 지게되는 게임이다.

이것을 약간 변형해서 7개의 코인을 가정하고 컴퓨터와 번갈아 가면서 1개, 2개 혹은 3개씩 가져가서 최종적으로 남은 코인을 0개로 만드는 쪽이 이기는 게임을 “변형 Nim 게임”이라고 하고 여기에 minimax를 적용해 보도록 하자.

결정 트리의 모든 노드를 그리면 공간이 부족하니 Max(컴퓨터)가 3개를 가져가는 경우를 탐색하는 상황을 살펴보자. Max와 Min은 각각 번갈아 가면서 코인을 1개, 2개 혹은 3개를 가져가는 상황에 대하여 남은 coin이 0이 되는 상황을 탐색한다.

Max 입장에서 남은 코인이 0개가 되도록 만드는 node가 Min이 되도록 하는 조건이 유리하다고 판단하고, 이 때 큰 점수 +1을 매겨서 결정을 유도하고, 그 반대의 경우에는 -1 점수를 매겨서 이 상황을 피하도록 한다.

구현코드

이러한 트리 탐색 과정을 재귀함수로 나타내면 다음과 같다.

실행 결과 및 결론

다음은 전체 코인의 갯수를 설정하는 total_coins의 값을 12로 해서 수행한 결과이다.

결과를 보면 12 / 8 / 4개를 남기도록 하는 규칙을 명시적으로 주지 않았음에도 컴퓨터는 minimax tree로 부터 이러한 값들이 승부에 유리하다는 것을 탐색해서 항상 이러한 값에 가장 가까운 선택을 하려하는 것 처럼 보이는 약간의 지능적(?) 결과를 볼 수 있다.

pip 설치 중 컴파일 문제 회피를 위한 잡 기술

Python에서 어떤 패키지를 설치하려면 pip를 사용한다.

pip install <패키지>

이상적으로는 이렇게만 하면 편리하게도 pip가 PiPy에서 해당 패키지를 다운로드 해서 개발환경에 설치 해준다. 하지만 실제 pip 설치는 생각보다는 조금 복잡하다. 특히 macOS나 Linux 환경에서는 pip 설치가 기대치 않았던 C/C++ 컴파일 에러라는 새드 엔딩으로 치닫는 경우가 적지 않다.

이 포스팅에서는 pip에서 소스 코드 빌드를 회피하는 방법을 중심으로, pytubefix와 그 의존성인 nodejs-wheel-binaries 사례를 통해 설치를 실행하기 전에 실패를 예측하는 방법과 이를 최대한 회피하는 방법을 정리해 본다. 다만, 설명의 편의를 위해 local wheel 파일을 설치하는 경우는 제외하고 PiPy에서 다운로드 받는 패키지를 가정하고 설명 하였다.

pip 설치에는 두 가지 경우가 있다

pip가 패키지를 설치하는 방식은 크게 두 가지다.

pip install <패키지>
 ├─ wheel(.whl) 파일이 PiPy에 있음 -> 다운로드 후 설치
 └─ wheel 없음 -> 소스 코드 빌드

PiPy에 원하는 버전의 wheel 파일이 존재하면 이것을 다운로드해서 설치하는 것으로 설치 과정이 끝난다. 이것이 바로 앞에서 말한 “이상적인” 경우이다. 만약 wheel이 없으면 pip는 자동으로 소스 빌드를 시도하게 되는데 이렇게 되면 pip 설치 명령어의 성공 여부는 더이상 pip 자체의 문제가 아니라 다양한 변수들의 의존성에 달려있게 된다.

  • OS 버전
  • 컴파일러(clang, gcc)
  • 각종 SDK
  • 외부 라이브러리(OpenSSL 등)

만약 이 모든 요소가 잘 못 얽히게 되면, 복잡 다단한 원인에 의한 컴파일 문제로 결국은 pip 설치 명령어가 실패 할 수도 있다.

설치 전에 컴파일 가능성 판별하기

pip install 명령어의 –dry-run 옵션은 실제로는 설치를 진행하지 않고 모의 실행(Dry run) 해주는 명령어 인데, 이것을 이용하면 컴파일을 필요로 하는 상황인지의 여부를 미리 확인할 수 있다. macOS에서 Pytubefix 패키지를 설치하려는 경우를 예를들어 살펴보자.

pip install pytubefix --dry-run

전술한 대로 이 명령은 실제로 설치를 하지는 않지만, pip가 무엇을 설치하려고 하는지는 그대로 보여 준다. 출력 중에서 주의해서 봐야 할 부분은 다음이다.

이 메세지는 wheel 파일이 없어서 소스 코드 빌드가 시도 됨을 의미한다.

컴파일 회피 하기

컴파일이 항상 실패하는 것은 아니고, 문제가 발생한 경우에도 간단한 의존성 문제를 해결하는 것으로 해결하는 것도 가능하겠지만 때로는 모든 종속성을 해결해 줄 수 없어 차라리 오래된 버전이라도 미리 컴파일 되어 있는 wheel을 사용하고자 할 때도 있다. –only-binary option을 사용하면 설치가 가능한지 여부를 확인할 수 있는데, 다음과 같이 입력하면 직접 컴파일 하지 않고 whl을 다운로드 받아서 설치가 가능한지 여부를 확인할 수 있다.

pip install pytubefix --dry-run --only-binary=:all:

이 옵션은 컴파일 된 wheel이 있는 패키지들로 dry run을 실행해 보라는 의미이다. 성공하면 모든 의존성이 wheel로 제공된다. –only-binary option을 주지 않았을 때에 비해 낮은 버전이 제시된 것을 눈여겨보자. 소스코드 설치는 v24.13.0 이지만 바이너리 설치는 v22.20.0 이다.

만약 이 명령어에서 실패한다면 안타깝게도 의존성이 소스 빌드 없이는 설치가 불가능 함을 의미한다.

실제사례 – Pytubefix

Pytubefix는 YouTube clip를 다운로드 받을 수 있도록 해주던 PyTube가 더 이상 유지 관리가 되지 않으면서 이를 이어받아 진행되고 있는 오픈소스 프로젝트이다. Pytubefix가 Node.js 환경을 독립적으로 관리할 수 있게 해주는 도구인 nodejs-wheel-binaries에 의존 하는데, 문제는 이 모듈이 macOS 13 이상의 버전에 대해서만 wheel을 제공하고 있다는 점이다.

그래서 macOS Monterey(12) 환경에서 pytubefix 설치를 시도하면 지원되는 가장 최신의 nodejs-wheel-binaries 버전인 v24.13.0 소스코드 빌드를 시도하게 되고 이것이 OpenSSL의 deprecated API 때문에 컴파일에 실패하게 된다.

wheel 없음 -> 소스 빌드 -> nodejs-wheel-binaries 컴파일 -> OpenSSL deprecated API -> 컴파일 실패

nodejs-wheel-binaries란?

nodejs-wheel-binaries는 Node.js 런타임을 Python wheel 형태로 패키징한 라이브러리로 Node.js 실행 파일을 Python 가상환경 내부에 포함시켜 pip install만으로 Node.js를 사용할 수 있게 만들어 준다. pytubefix는 YouTube 대응 로직 일부를 JavaScript 기반 코드로 처리하기 때문에 내부적으로 Node.js 실행을 필요로 하기 때문이 이 패키지에 의존한다. 주의할 점은 시스템에 설치한 Node.js의 버전은 이 동작과는 무관하다는 점이다. 즉, 시스템에 Node.js가 설치되어 있다 하더라도, 의존성이 있는 경우에는 이 패키지의 설치가 필요하다.

결론: 소스 빌드를 회피하는 현실적인 해결책

Pytubefix를 위해서는 반드시 최신버전의 nodejs-wheel-binaries 패키지를 사용하지는 않아도 된다. 위에서 pip 명령어로 wheel 파일이 지원되는 것으로 확인한 v22.20.0을 다음의 명령어로 먼저 설치하고 그 위에 pytubefix의 설치를 실행할 수 있다.

pip install "nodejs-wheel-binaries==22.20.0" pytubefix

OpenVINO Object Detection Model의 전처리와 후처리를 간단하게

AI model들은 입출력 layer의 구조가 다르므로 서로 다른 pre/post processing을 필요로 한다. Vision model을 예로 들면 어떤 모델은 입력을 416×416으로 받게 되어 있어서 입력 전에 원본 크기로 부터 resizing을 해주어야 하고, 어떤 모델은 resizing layer을 포함하고 있어서 그냥 입력해도 잘 동작하기도 한다. 또한 어떤 모델은 입력값을 정규화 해서 입력해 주어야 하고, 어떤 모델은 정규화가 필요 없기도 하다.

입력층 뿐 아니라 출력층도 제각각이다. Object detection을 수행하는 모델들을 보면 YOLO같은 모델은 score값을 bounding box와 함께 전달하고, D-Fine같은 모델은 bounding box, score, label을 각각 따로 출력하기도 한다.

어떤 모델의 입출력 형태의 차이를 보고 싶으면 읽어들인 모델의 inputs와 outputs 변수의 내용을 살펴보면 된다.

def print_model_io_layer(ovcore: Core, model_path: str, model_name: str):
    read_model = ovcore.read_model(model_path)
    print(f"[{model_name}]")

    # Display input layer
    for idx, input_layer in enumerate(read_model.inputs):
        print(f"Input({idx+1}):")
        print("  any_name     :", input_layer.get_any_name())
        print("  names        :", input_layer.get_names())
        print("  shape        :", input_layer.get_partial_shape())
        print("  element type :", input_layer.get_element_type())

    # Display output layer
    for idx, output_layer in enumerate(read_model.outputs):
        print(f"Output({idx+1}):")
        print("  any_name     :", output_layer.get_any_name())
        print("  names        :", output_layer.get_names())
        print("  shape        :", output_layer.get_partial_shape())
        print("  element type :", output_layer.get_element_type())

이렇게 다양한 모델들의 입출력을 직접 처리하는 것은 여간 번거로운 일이 아니다. OpenVINO에서는 모델에 전/후처리를 사용자가 지정할 수 있는 PrePostProcessor를 지원하기는 하지만 이 마저도 모델별로 상이한 부분을 직접 수정해 주어야 하기 때문에 번거로운 것은 마찬가지다.

OpenVINO Model API 사용법

예를 들어 ATSS, YOLOX-S, YOLOX-Tiny, D-Fine 네개의 OpenVINO model과 각각에 대한 ONNX model들까지 8개의 서로 다른 세개의 서로 다른 모델들이 있다고 할 때, 8개의 서로 다른 입출력 결과를 처리하는 것은 아주 많은 노력을 필요로 할 것이다.

openvino-model-api를 사용하면 이러한 부분을 비교적 간단하게 처리 할 수 있다. 사용하려면 다음과 같이 필요한 패키지들을 설치해 준다.

pip install openvino openvino-model-api onnx

설치가 끝나면 먼저 서로 다른 입출력 계층을 맞춰 주는 모델을 생성한다. 추론에 사용하고자 하는 모델 파일로 OpenvinoAdapter를 만들어서 create_model()에 넘겨 준다. 이렇게 생성된 모델은 입력을 위한 전처리 과정을 자동으로 수행한다.

from openvino import Core
from model_api.adapters import OpenvinoAdapter
from model_api.models import Model


ovcore = Core()

# Adapter를 생성하고 create_model()에 넘겨준다.
ovadapter = OpenvinoAdapter(ovcore, model_path)
model = Model.create_model(ovadapter, preload=True)

그리고 나서 추론을 실행하면 그 결과는 DetectionResult 타입으로 정리되어 반환된다. 따라서 모델별로 서로다른 후처리(post processing) 과정 필요 없이 DetectionResult으로 반환되는 결과를 처리해주면 된다.

# 추론 실행
detection_result = model(test_image)

결과물 처리를 위해서 detection_result를 원본 이미지에 overlay하는 함수로 만들었다(overlay_detection_result). 이 함수는 Threshold값을 넘는 결과물을 원본 이미지 위에 bounding box와 label로 표시하고 detect된 object의 갯수와 함께 반환해 준다.

DetectionResult에서 참조되는 주요한 멤버변수는 Socre값을 나타내는 .score, bounding box를 나타내는 .xmin, .ymin, .xmax, .ymax 그리고 label을 가지고 있는 .str_label이다. Bounding box 좌표도 입력 이미지의 크기에 맞게 이미 scaling되어 있으므로 좌표를 그대로 가져다 쓰면 된다.

from model_api.models.utils import DetectionResult


def overlay_detection_result(
    original_image: np.ndarray, detection_result: DetectionResult, threshold: float
) -> Tuple[np.ndarray, int]:
    num_detected = 0
    processed_image = original_image.copy()

    for det in detection_result[0]:
        score = det.score
        if score >= threshold:
            num_detected += 1

            # Bounding box
            x1 = int(det.xmin)
            y1 = int(det.ymin)
            x2 = int(det.xmax)
            y2 = int(det.ymax)

            # Clamping
            x1 = max(0, min(x1, original_image.shape[1]))
            y1 = max(0, min(y1, original_image.shape[0]))
            x2 = max(0, min(x2, original_image.shape[1]))
            y2 = max(0, min(y2, original_image.shape[0]))

            # Draw BBox
            cv2.rectangle(processed_image, (x1, y1), (x2, y2), BBOX_COLOR, 2)

            # Draw label.
            display_text = (
                f"{det.str_label} {score:.2f}" if {det.str_label} else f"{score:.2f}"
            )
            cv2.putText(
                processed_image,
                display_text,
                (x1, y1 - 10),
                cv2.FONT_HERSHEY_SIMPLEX,
                0.5,
                LABEL_COLOR,
                2,
            )
    return processed_image, num_detected

8개의 모델에 시험해 보자

사용하려는 8개의 모델들은 다음과 같다.

atss_model_file = os.path.join(MODEL_PATH, "atss_fp32/model.xml")
atss_onnx_model_file = os.path.join(MODEL_PATH, "atss_onnx_fp32/model.onnx")
yolos_model_file = os.path.join(MODEL_PATH, "yolos_fp32/model.xml")
yolos_onnx_model_file = os.path.join(MODEL_PATH, "yolos_onnx_fp32/model.onnx")
yolotiny_model_file = os.path.join(MODEL_PATH, "yolotiny_fp32/model.xml")
yolotiny_onnx_model_file = os.path.join(MODEL_PATH, "yolotiny_onnx_fp32/model.onnx")
dfinex_model_file = os.path.join(MODEL_PATH, "dfinex_fp32/model.xml")
dfinex_onnx_model_file = os.path.join(MODEL_PATH, "dfinex_onnx_fp32/model.onnx")

이것들을 all_models라는 list에 넣고 한번에 돌린다. 즉, 각 모델들의 서로 다른 입력과 출력 계층에 대한 처리를 단일한 코드로 수행하는 것이다.

ovcore = Core()


# Test image
test_image = cv2.imread("./data/test_image.jpg")

threshold = 0.8
for m in all_models:
    model_path = m[0]
    model_name = m[1]
    ovadapter = OpenvinoAdapter(ovcore, model_path)
    model = Model.create_model(ovadapter, preload=True)
    detection_result = model(test_image)
    proc_image, num_det = overlay_detection_result(
        test_image, detection_result, threshold
    )

    print(f"{model_name} :: {num_det} objects detected (threshold: {threshold}).")
    cv2.imwrite(f"output_{model_name}.jpg", proc_image)

전체 소스코드