가장 비싼 평화군

저자: 최적화 팀

이 사이트에 처음 게시되었습니다.

체스판의 일반적인 배열에서는 8개의 여왕, 8개의 룩, 14개의 비숍, 32개의 기사, 16개의 킹을 서로 위협하지 않고 수용할 수 있다는 것은 잘 알려져 있습니다. 하지만 이 모든 조각이 하나의 개체로 합쳐지면 어떻게 될까요?

여왕(Q)에 1/8, 루크(R)에 1/8, 비숍(B)에 1/14, 나이트(N)에 1/32, 킹(K)에 1/16을 할당한다고 가정할 때, 우리의 목표는 보드에서 이러한 구성 요소를 능숙하게 배치하여 다양한 조각들 간의 충돌이나 간섭을 피하면서 최적의 체스 전력을 구성하는 것입니다.

문제 공식화:

주어진 문제에 대한 해결책을 효과적으로 공식화하기 위해서는 먼저 각 체스 말의 ‘이웃’ 개념을 명확히 이해하는 것이 필수적입니다.

왕

목표 셀에서 2의 제곱근 이내 거리에 있는 셀은 1/sqrt(2)와 같은 이동 확률을 갖습니다.

Queen

주어진 격자에서 셀 (x0, y0)의 이웃 셀을 찾아봅시다.

셀 j는 다음 특성 중 하나 이상을 가지고 있는 경우 셀 i의 이웃 셀로 간주됩니다:

X=x0 Y=y0 U\\+007CX-x0U\\+007C=U\\+007CY-y0U\\+007C

Knight

셀 j는 다음 특성 중 하나 이상을 가진 경우 셀 i의 이웃 셀로 간주됩니다:

(X-x0,Y-y0) 이 목록의

[ (1,2),(1,-2) , (-1,2), (-1,-2) , (2,1), (2,-1) , (-2,-1),(-2,1) ]

비숍

셀 j는 다음 특성 중 하나 이상을 가지고 있는 경우 셀 i의 이웃 셀로 간주됩니다:

U\\+007CX-x0U\\+007C=U\\+007CY-y0U\\+007C

Rook

셀 j는 하나 이상의 특정 특성을 나타내는 경우 셀 i의 인접 셀로 간주됩니다. 이러한 특성에는 세포 i와 가까운 곳에 위치하거나, 세포 i와 유사한 물리적 또는 화학적 특성을 공유하거나, 세포 i의 기능에 직접적인 영향을 미치는 것 등이 포함되지만 이에 국한되지 않습니다.본질적으로 이러한 특성을 가진 세포는 각각의 생물학적 시스템 또는 환경의 맥락에서 세포 i의 이웃으로 간주됩니다.

이제 수학 모델에 대해 이야기해 보겠습니다:

우리의 군사력인 오델로 친구(OF)의 가치를 최적화하기 위해서는 모든 개별 유닛이 보드에서 적어도 하나의 위치를 점유해야 합니다. 또한, 그리드의 각 위치에는 한 명의 병사만 배치할 수 있습니다. 특정 전사가 점령하도록 지정된 셀은 경쟁 병사가 사용할 수 없게 됩니다. 또한, 적군의 위협을 받을 수 있는 인접한 셀은 비워두어야 합니다.

파이썬 코드:

def SolveWithTimeLimitSampleSat():
model = cp_model.CpModel()
# Creates the variables.
pieces = ['K', 'R', 'Q', 'N', 'B' ]
val= {'K':14, 'R':28, 'Q':28, 'N':7, 'B':16 }
symb= {'K':"\u265A", 'R':"\u265C", 'Q':"\u265B", 'N':"\u265E", 'B':"\u265D" }
U = {(n,p):model.NewBoolVar(f'assign_{n}_{p}') for n in nodes for p in pieces}
Occupied = {n:model.NewBoolVar(f'O_{n}') for n in nodes}for p in pieces:
expressions = [U[n,p] for n in nodes]
model.AddAtLeastOne(expressions)for n in nodes:
 expressions = [U[n,p] for p in pieces]
model.Add(sum(expressions) == Occupied[n])
model.AddAtMostOne(expressions)
expressions_king_around = [U[counter,'K'] for counter in nodes if counter in Nking[n] ]
expressions_rook_around = [U[counter,'R'] for counter in nodes if counter in NR[n] ]
expressions_queen_around = [U[counter,'Q'] for counter in nodes if counter in NQ[n] ]
expressions_knight_around = [U[counter,'N'] for counter in nodes if counter in Nknight[n] ]
expressions_bishop_around = [U[counter,'B'] for counter in nodes if counter in NB[n] ]around = expressions_king_around \\+ expressions_rook_around \\+ expressions_queen_around \\+ expressions_knight_around \\+ expressions_bishop_around
model.Add( sum(around) == 0 ).OnlyEnforceIf(Occupied[n])expressions_of = [val[p]*v for (n,p),v in U.items() ]
model.Maximize(sum(expressions_of))
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30.0
status = solver.Solve(model)if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print('OF = ', status, solver.ObjectiveValue())

결과:

관측:

이 문제가 제시하는 도전은 고유한 대칭성에 있으며, 이는 해결책을 찾는 노력을 복잡하게 만듭니다. 당면한 문제에 대한 여러 가지 해결책이 존재할 수 있습니다. 혼합 정수 선형 프로그램(MILP)의 프레임워크 내에서 공식화되었지만 기본 코드는 제약 조건 프로그래밍 도구(ORTools)의 사용에 의존합니다.

깃허브 링크 https://github.com/OptimizationExpert/Pyomo

8만 명 이상의 구독자를 자랑하는 권위 있는 AI 뉴스레터를 구독하여 존경받는 데이터 전문가 커뮤니티에 가입해 보시기 바랍니다. 획기적인 연구, 혁신적인 프로젝트, 새로운 개념에 대한 포괄적인 보도를 통해 다양한 영역에 걸친 인공지능의 최첨단 발전 상황을 파악할 수 있습니다. 또한, AI 기반 벤처를 설립하거나 개발 중인 경우, 귀사의 브랜드를 홍보하고 업계 내 협업을 촉진하는 귀중한 수단으로 저희 간행물을 후원할 수 있는 기회를 적극 환영합니다.

이 사이트를 통해 발행