[AI초급]One Step Lookahead (한 발 앞서 보자)

sources :
https://www.kaggle.com/code/alexisbcook/one-step-lookahead

One-Step Lookahead

Introduction
Even if you're new to Connect Four, you've likely developed several game-playing strategies. In this tutorial, you'll learn to use a heuristic to share your knowledge with the agent.
게임전략 개발에 대해서 알아보자.
휴리스틱이란: 발견법;
제한적인 정보나 시간에 대해 직관적 추론을 가능하게 하는 것 (인간과 유사한 직관성을 갖추도록 하는 것.)

Game trees
게임트리
As a human player, how do you think about how to play the game? How do you weigh alternative moves?
인간으로서 게임을 한다면 어떻게 의사 결정을 하는가, 다음 움직임을 정할때 뭘 중요시하게 되는가?

You likely do a bit of forecasting. For each potential move, you predict what your opponent is likely to do in response, along with how you'd then respond, and what the opponent is likely to do then, and so on. Then, you choose the move that you think is most likely to result in a win.

아마 대부분 약간의 예측이란 것을 하게 된다. 상대방(다른 플레이어이거나 게임 속 캐릭터이거나)의 움직임을 예측하고 내 캐릭터가 낼 수 있는 퍼포먼스를 생각하면서 동작을 정한다.
아마도 그렇게 선택한 움직임은 스스로 보기에 승리를 위한 최적의 선택 이었다는 생각을 할거다.

We can formalize this idea and represent all possible outcomes in a (complete) game tree.

우리는 이런 아이디어를 구체화하고 모든 가능성을 표현하는 게임 트리라는 것을 만들 수 있다.

The game tree represents each possible move (by agent and opponent), starting with an empty board. The first row shows all possible moves the agent (red player) can make. Next, we record each move the opponent (yellow player) can make in response, and so on, until each branch reaches the end of the game. (The game tree for Connect Four is quite large, so we show only a small preview in the image above.)
게임 트리는 플레이어와 적의 모든 가능한 움직임을 나타낼 수 있으며 비어있는 보드에서 시작하낟.
첫줄은 플레이어의 모든 가능한 움직임을 나타내고
그다음 우리는 그 다음줄에 적(Opponent)의 가능한 대응을 모두 적는다. 이런 방식으로 트리의 각 마지막 가지가 게임 종료 조건에 달할 때까지 적어 나간다.
여기서 예를 든, Connect Four라는 게임의 전체 게임트리는 방대하지만 여기서는 일부만 소개하고 있다.

Once we can see every way the game can possibly end, it can help us to pick the move where we are most likely to win.
일단 우리는 게임의 모든 가능한 분기점을 알게 된다면 어떤 선택이 최선의 선택 (승리가능성이 가장 높은지)인지를 알 수 있게 된다.

# 즉 모수가 되는 모든 분기를 아는 경우다.


Heuristics
The complete game tree for Connect Four has over 4 trillion different boards! So in practice, our agent only works with a small subset when planning a move.
자 앞서 소개한 Connect Four라는 게임의 분기는 4조 개가 넘는다고 한다.
실제로 이걸 매번 고려한다면 비실용적일 수 밖에 없다 . 실제로는 이중 매우 일부만 사용하여 판단하게 된다고 한다.

To make sure the incomplete tree is still useful to the agent, we will use a heuristic (or heuristic function). The heuristic assigns scores to different game boards, where we estimate that boards with higher scores are more likely to result in the agent winning the game. You will design the heuristic based on your knowledge of the game.
자 게임트리의 일부만 가지고도 충분히 유용하다는 것을 증명하기 위해 우리는 휴리스틱 알고리즘을 사용할 것이다.
휴리스틱은 각 분기(게임보드; Gameboard)마다 점수를 매기는데 우리가 유리하다고 판단한 분기가 선택되면 승리에 더 큰 기여를 한다고 판단하게 된다. 여기서 각 분기에 대한 평가는 여러분이나 전문가의 게임에 대한 분석을 토대로 하게 된다.

instance, one heuristic that might work reasonably well for Connect Four looks at each group of four adjacent locations in a (horizontal, vertical, or diagonal) line and assigns:
예를 들어 Connect Four 게임에서 이웃하는 연속적인 수평, 수직, 대각선의 직선을 이루게 되면 ...
아래와 같은 보상이 기대된다.

1000000 (1e6) points if the agent has four discs in a row (the agent won),
1 point if the agent filled three spots, and the remaining spot is empty (the agent wins if it fills in the empty spot), and
-100 points if the opponent filled three spots, and the remaining spot is empty (the opponent wins by filling in the empty spot).
This is also represented in the image below.


And how exactly will the agent use the heuristic? Consider it's the agent's turn, and it's trying to plan a move for the game board shown at the top of the figure below. There are seven possible moves (one for each column). For each move, we record the resulting game board.
그럼 Agent는 어떻게 휴리스틱을 사용할까?
우선 Agent의 턴이 되었다고 하고, 이제 움직일 수 있는 분기가 7개라고 할 때, 각 분기마다 게임 결과 보드에 기록을 하게 된다.

Then we use the heuristic to assign a score to each board. To do this, we search the grid and look for all occurrences of the pattern in the heuristic, similar to a word search puzzle. Each occurrence modifies the score.
각 보드에 휴리스틱 값을 넣고나면 마치 십자말 풀이에서 하듯이 각 사방을 탐색하고 휴리스틱에 저장된 패턴과 동일한 패턴이 있는지를 찾게된다. 만약 있다면 해당패턴에 의해 각 분기의 점수(가중치)가 변하게 된다.


#이하는 Connect Four 게임의 게임보드와 이에 대한 휴리스틱 적용을 설명한 것. (생략한다.)
For instance, The first board (where the agent plays in column 0) gets a score of 2. This is because the board contains two distinct patterns that each add one point to the score (where both are circled in the image above).

The second board is assigned a score of 1.
The third board (where the agent plays in column 2) gets a score of 0. This is because none of the patterns from the heuristic appear in the board.

The first board receives the highest score, and so the agent will select this move. It's also the best outcome for the agent, since it has a guaranteed win in just one more move. Check this in figure now, to make sure it makes sense to you!
##여기까지


The heuristic works really well for this specific example, since it matches the best move with the highest score. It is just one of many heuristics that works reasonably well for creating a Connect Four agent, and you may find that you can design a heuristic that works much better!

휴리스틱은 이처럼 어떤 움직임을 선택하느냐에 따라 높은 점수를 얻는 게임에는 아주 잘 맞는다.
사실 앞서 설명한 예는 적용 가능한 다양한 휴리스틱 방법 중에 하나일 뿐이다.

In general, if you're not sure how to design your heuristic (i.e., how to score different game states, or which scores to assign to different conditions), often the best thing to do is to simply take an initial guess and then play against your agent. This will let you identify specific cases when your agent makes bad moves, which you can then fix by modifying the heuristic.

만약 어떻게 해야 자신의 agent (여기서 agent는 AI agent, 인공지능 플레이어 또는 인공지능 적을 의미.)
를 위한 휴리스틱 알고리즘을 짤지 모르겠다면 일단 한번 점수를 넣고 돌려보면 된다. -> 그러고 나서 나중에 평가를 하는 것이다. 이것은 어떤 특정 케이스에서 agent가 제대로 된 판단을 내리고 있는지 볼 수 있게 해주고 휴리스틱을 수정할 수 있게 도와 준다.
<이하생략>
<코드 생략>