4w0325
2026๋ 11์ 15์ผ ๊ณต์
๐จ [์ํ ์ถ์ ๋ ์ด๋] ํต์ฌ ํ ํฝ ๋ถ์
์์ ์ถ์ ์์ | ํต์ฌ ํ ํฝ (์ฃผ์ ๋ช
) | ๊ต์๋ ๊ฐ์กฐ ์์ค (์/์ค/ํ) | ์ถ์ ์์ ์ ํ (๋จ๋ต/๊ณ์ฐ/๋น๊ต/์์ ) |
|---|---|---|---|
1์์ | A* ์๊ณ ๋ฆฌ์ฆ (f, g, h ๊ณ์ฐ ๋ฐ OPEN/CLOSED ๋ฆฌ์คํธ) | ์ | ๊ณ์ฐ/๋จ๋ต/์์ |
2์์ | Minimax ๋ฐ Alpha-beta Pruning ์๋ ์๋ฆฌ | ์ | ๊ณ์ฐ/์์ |
3์์ | MCTS (Monte Carlo Tree Search) 4๋จ๊ณ | ์ค | ๋จ๋ต/์์ |
4์์ | AlphaGo์ MCTS ์ ์ฉ (์ ์ฑ
๋ง/๊ฐ์น๋ง) | ํ | ์์ |
๐ง [A+ ์์ ํ ์๋ฒฝ ๋๋น] ๋ ผ๋ฆฌ ํ๋ฆ ๋ ธํธ
[์ฃผ์ ๋ช 1] A* Algorithm
- ์ถ์ ํฌ์ธํธ: ํ๊ฐ ํจ์ ๏ปฟ์ ์๋ฏธ์ OPEN/CLOSED ๋ฆฌ์คํธ๋ฅผ ํ์ฉํ ํ์ ๊ณผ์ ์ดํด
- Why (์ ๋์ ๋์๋): ๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆ์ ๋ชฉ์ ์ง์ ๋ฌด๊ดํ๊ฒ ๋ชจ๋ ๋ฐฉํฅ์ ํ์ํ์ฌ ๋ญ๋น๊ฐ ์ฌํจ. ๋ชฉ์ ์ง๊น์ง์ ์ถ์ ๋น์ฉ์ ๊ณ ๋ คํ์ฌ ํ์ ๋น์ฉ์ ์ต์ํํ๊ธฐ ์ํด ๋์ ๋จ.
- How (์ด๋ป๊ฒ ์๋ํ๋):
- ๏ปฟ: ์์ ๋ ธ๋์์ ํ์ฌ ๋ ธ๋๊น์ง์ ์ค์ ๋์ ๋น์ฉ.
- ๏ปฟ(ํด๋ฆฌ์คํฑ): ํ์ฌ ๋ ธ๋์์ ๋ชฉ์ ์ง๊น์ง์ ์ถ์ ๋น์ฉ (์: ํผ์ฆ์ ์ ์๋ฆฌ์ ์๋ ์ซ์ํ ๊ฐ์, ์ง๋์์ ์ง์ ๊ฑฐ๋ฆฌ).
- OPEN ๋ฆฌ์คํธ(ํ์ ํ๋ณด, ๏ปฟ๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฒ๋ถํฐ ์ฐ์ ํ์)์ CLOSED ๋ฆฌ์คํธ(๋ฐฉ๋ฌธ ์๋ฃ, ์ค๋ณต ํ์ ๋ฐฉ์ง)๋ฅผ ์ฌ์ฉํ์ฌ ํธ๋ฆฌ๋ฅผ ํ์ฅํจ.
- Limit/Result (ํ๊ณ์ ๋ฐ ์์): ๏ปฟ์ ์ค์ ๋น์ฉ์ ๊ณผ๋ํ๊ฐ(overestimate)ํด์๋ ์ ๋๋ฉฐ, ๊ฐ๋ฅํ ์ค์ ๋น์ฉ์ ๊ฐ๊น๊ฒ ์ต์ ๋น์ฉ์ผ๋ก ์ถ์ ํด์ผ ์ฌ๋ฐ๋ฅธ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ์ ์ ์์.
[์ฃผ์ ๋ช 2] Minimax Search & Alpha-beta Pruning
- ์ถ์ ํฌ์ธํธ: ์ ๋์ ๊ฒ์ ํธ๋ฆฌ์์ ๋ถํ์ํ ํ์์ ์ค์ด๋ ๊ฐ์ง์น๊ธฐ(Pruning) ์๋ฆฌ
- Why (์ ๋์ ๋์๋): ์ฒด์ค๋ ํฑํํ ์ฒ๋ผ ๊ฐ๋ฅํ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋๊น์ง ํ์ํ๋ ๊ฒ์ ์ฐ์ฐ๋์ด ๋๋ฌด ๋ฐฉ๋ํจ. ์๋๋ฐฉ์ด ์ต์ ์ ๋คํด ๋๋ฅผ ๋ฐฉํดํ๋ค๋ ๊ฐ์ ํ์ ์ต์ ์ ์๋ฅผ ์ฐพ๊ณ , ๋ถํ์ํ ๊ฒฝ๋ก๋ ํ์ํ์ง ์๊ธฐ ์ํด ๋์ .
- How (์ด๋ป๊ฒ ์๋ํ๋):
- Minimax: Max ๋ ธ๋(๋)๋ ์์ ์ค ์ต๋๊ฐ์, Min ๋ ธ๋(์๋)๋ ์ต์๊ฐ์ ์ ํ.
- Alpha-beta Pruning: ๊น์ด ์ฐ์ ํ์(DFS) ๋ฐฉ์์ผ๋ก ์ผ์ชฝ๋ถํฐ ํ์. Max ๋
ธ๋๋ ๏ปฟ(์ต๋๊ฐ), Min ๋ ธ๋๋๏ปฟ(์ต์๊ฐ)๋ฅผ ์ ์ง. ๋ง์ฝ Min ๋ ธ๋๊ฐ ํ์ ์ค ๋ถ๋ชจ Max ๋ ธ๋๊ฐ ์๊ตฌํ๋๏ปฟ๋ณด๋ค ์์ ๊ฐ์ ๋ฐ๊ฒฌํ๋ฉด, ๋ถ๋ชจ๋ ์ด์ฐจํผ ๊ทธ ๊ฒฝ๋ก๋ฅผ ์ ํํ์ง ์์ ๊ฒ์ด๋ฏ๋ก ๋๋จธ์ง ํ์์ ์ค๋จ(Pruning)ํจ.
- Limit/Result (ํ๊ณ์ ๋ฐ ์์): ํ์ ๋น์ฉ์ ํ๊ธฐ์ ์ผ๋ก ์ค์ผ ์ ์์ผ๋, ์ฌ์ ํ ๋ฐ๋๊ณผ ๊ฐ์ด ๊ฒฝ์ฐ์ ์๊ฐ ๊ทน๋๋ก ๋ง์ ๊ฒ์์์๋ ๋ชจ๋ ๋ ธ๋๋ฅผ ํ๊ฐํ๊ธฐ ์ด๋ ค์.
[์ฃผ์ ๋ช 3] MCTS (Monte Carlo Tree Search)
- ์ถ์ ํฌ์ธํธ: ๋ฌด์์ ์๋ฎฌ๋ ์ด์ ์ ๊ธฐ๋ฐ์ผ๋ก ํ ํธ๋ฆฌ ํ์ 4๋จ๊ณ ๋ฐ UCB1์ ์๋ฏธ
- Why (์ ๋์ ๋์๋): ๋ฐ๋์ฒ๋ผ ๋ถ๊ธฐ ์๊ฐ ๋๋ฌด ๋ง๊ณ (ํ๊ท 250์) ์ ๋นํ ํ๊ฐ ํจ์๋ฅผ ๋ง๋ค๊ธฐ ์ด๋ ค์ด ๋ณต์กํ ๊ฒ์์ ํด๊ฒฐํ๊ธฐ ์ํด ๋์ .
- How (์ด๋ป๊ฒ ์๋ํ๋):
- Selection (์ ํ): UCB1 ๊ณต์์ ์ฌ์ฉํ์ฌ ์น๋ฅ (Exploitation)๊ณผ ํ์ ํ์๊ฐ ์ ์ ์ ๋(Exploration)๋ฅผ ๊ณ ๋ คํด ๋ค์ ๋ ธ๋ ์ ํ.
- Expansion (ํ์ฅ): ์์์ Action์ ์ ํํด ํธ๋ฆฌ์ ๋ ธ๋ ์ถ๊ฐ.
- Simulation (์๋ฎฌ๋ ์ด์ ): ์นํจ๊ฐ ๊ฒฐ์ ๋ ๋๊น์ง ๋ฌด์์๋ก ๊ฒ์ ์งํ.
- Backpropagation (์ญ์ ํ): ๊ฒ์ ๊ฒฐ๊ณผ๋ฅผ ํธ๋ฆฌ์ ๋ฃจํธ ๋ฐฉํฅ์ผ๋ก ๊ฑฐ์ฌ๋ฌ ์ฌ๋ผ๊ฐ๋ฉฐ ์น๋ฅ ๋ฐ ์๋ ํ์ ํต๊ณ ์ ๋ฐ์ดํธ.
- Limit/Result (ํ๊ณ์ ๋ฐ ์์): ์๋ฎฌ๋ ์ด์ ์ด ๋ง์์๋ก ํต๊ณ ํธ๋ฆฌ๊ฐ ์ปค์ง๊ณ ๋ ธ๋ ๊ฐ์ ์ ํ๋๊ฐ ํฅ์๋จ. ์ํ๊ณ ๋ ์ฌ๊ธฐ์ ์ ์ฑ ๋ง(Policy Network)๊ณผ ๊ฐ์น๋ง(Value Network)์ ๊ฒฐํฉํ์ฌ ์ฑ๋ฅ์ ๊ทน๋ํํจ.
โ๏ธ [ํ์ ์๊ธฐ] ํท๊ฐ๋ฆฌ๋ ๊ฐ๋ ๋น๊ต
๋น๊ต ํญ๋ชฉ | [Max ๋
ธ๋] | [Min ๋
ธ๋] |
|---|---|---|
ํต์ฌ ์ญํ | ์์ ์ ์ด์ต(์ ์)์ ์ต๋ํํ๋ ์๋ฅผ ์ ํ | ์๋๋ฐฉ์ ์ด์ต์ ์ต์ํ(๋๋ฅผ ์ง๊ฒ ํจ)ํ๋ ์๋ฅผ ์ ํ |
์ ์ง ๋ณ์ | ๏ปฟ (์ํ): ๋ฐ๊ฒฌ๋ ์ต๋๊ฐ | ๏ปฟ (๋ฒ ํ): ๋ฐ๊ฒฌ๋ ์ต์๊ฐ |
Pruning ์กฐ๊ฑด | ์์ ๋
ธ๋์์ ๏ปฟ ๊ฐ ๋๋ฉด ๊ฐ์ง์น๊ธฐ | ์์ ๋
ธ๋์์ ๏ปฟ ๊ฐ ๋๋ฉด ๊ฐ์ง์น๊ธฐ |
โ ๏ธ [์ถ์ ์์ ํจ์ ์ฃผ์!]A* ์๊ณ ๋ฆฌ์ฆ์์๏ปฟ์ ๊ณ์ฐํ ๋, ํผ์ฆ ๋ฌธ์ ์ ๊ฒฝ์ฐ '๋น์นธ'์ ์์น๊ฐ ํ๋ฆฐ ๊ฒ์ ์ธ์ง ์๊ณ ์ค์ง '์ซ์ํ'์ด ์๋ชป๋ ์์น์ ์๋ ๊ฐ์๋ง ์ธ์ด์ผ ํฉ๋๋ค. (๊ต์๋ ๊ฐ์กฐ์ฌํญ)
๐ฏ [์ค์ ๋ชจ์๊ณ ์ฌ] ๊ต์๋ ๋ง์ถคํ ํ๋์ฝ์ด ํ๋ จ
[์น์
1: ๋จ๋ต ๋ฐ ๊ฐ๋
ํ์ธํ]
- Q1. A* ์๊ณ ๋ฆฌ์ฆ์์ ์ด๋ฏธ ๋ฐฉ๋ฌธํ์ฌ ๋ค์ ๋จ๊ณ๋ก ํ์ฅํ ๋ ธ๋๋ค์ ์ ์ฅํ์ฌ ์ค๋ณต ํ์์ ๋ฐฉ์งํ๋ ๋ฆฌ์คํธ์ ์ด๋ฆ์ ๋ฌด์์ธ๊ฐ?
- Q2. ์ ๋์ ํ์์์ ์ฃผ์ฌ์๋ ํ๋ฅ ์ ์์๊ฐ ํฌํจ๋ ๊ฒ์์ ํด๊ฒฐํ๊ธฐ ์ํด Max์ Min ๋ ธ๋ ์ฌ์ด์ ์ถ๊ฐํ๋ ๋ ธ๋๋ ๋ฌด์์ธ๊ฐ?
- Q3. MCTS์ 4๋จ๊ณ ์ค, ๋ฆฌํ ๋ ธ๋์์ ๊ฒ์ ์ข ๋ฃ๊น์ง ๋ฌด์์๋ก ์๋ฅผ ๋์ด ์นํจ๋ฅผ ํ์ธํ๋ ๋จ๊ณ๋ ๋ฌด์์ธ๊ฐ?
- Q4. MCTS์์ ํ์ฌ๊น์ง ์น๋ฅ ์ด ๋์ ์๋ฅผ ์ ํํ๋ ๊ฒ(Exploitation)๊ณผ ์์ง ์ถฉ๋ถํ ์๋๋์ง ์์ ์๋ฅผ ์ ํํ๋ ๊ฒ(Exploration)์ ๊ท ํ์ ๋ง์ถ๊ธฐ ์ํด ์ฌ์ฉํ๋ ๊ณ์ฐ์์ ์ด๋ฆ์ ๋ฌด์์ธ๊ฐ?
[์น์
2: ์กฐ๊ฑด๋ถ ์ ์ฉ ๋ฐ ๊ณ์ฐํ]
- Q5. 3x3 ์ฌ๋ผ์ด๋ฉ ํผ์ฆ์ A* ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ๊ณ ์ ํ๋ค. ํ์ฌ ๋
ธ๋๊ฐ ์์ ์ํ๋ก๋ถํฐ 3๋ฒ ์ด๋ํ์ฌ ๋๋ฌํ๊ณ , ๋ชฉํ ์ํ์ ๋น๊ตํ์ ๋ ์ ์๋ฆฌ์ ์์ง ์์ ์ซ์ํ(๋น์นธ ์ ์ธ)์ด 4๊ฐ๋ผ๋ฉด, ์ด ๋
ธ๋์ ๏ปฟ๊ฐ์ ์ผ๋ง์ธ๊ฐ?
[์น์
3: ์์ ํ ๋ฐ ๋
ผ์ ํ]
- Q6. A* ์๊ณ ๋ฆฌ์ฆ์์ ํด๋ฆฌ์คํฑ ํจ์ ๏ปฟ์ ์ค์ ํ ๋ ์ฃผ์ํด์ผ ํ ํต์ฌ ์์น์ ์ค๋ช ํ๊ณ , ๊ฒฝ๋ก ํ์ ๋ฌธ์ ์์ '์ง์ ๊ฑฐ๋ฆฌ'๋ฅผ๏ปฟ์ผ๋ก ์ฌ์ฉํ๋ ์ด์ ๋ฅผ ์์ ํ์์ค.
- Q7. Alpha-beta Pruning์์ Min ๋
ธ๋๊ฐ ํ์์ ์ค๋จ(Pruning)ํ๊ฒ ๋๋ ๋
ผ๋ฆฌ์ ์ด์ ๋ฅผ Max ๋
ธ๋์ ๏ปฟ๊ฐ๊ณผ ์ฐ๊ด ์ง์ด ์์ ํ์์ค.
<details>
</details>
<summary></summary>
[์น์
1 ์ ๋ต]Q1. CLOSED ๋ฆฌ์คํธ
Q2. ํ๋ฅ ๋
ธ๋ (Chance node / Expectiminimax)
Q3. ์๋ฎฌ๋ ์ด์
(Simulation)
Q4. UCB1
[์น์
2 ์ ๋ต]Q5. 7 (
๏ปฟ
)[์น์
3 ์ ๋ต ๋ฐ ์ฑ์ ๊ธฐ์ค]Q6.
- ํต์ฌ ํค์๋: ๊ณผ๋ํ๊ฐ ๋ฐฉ์ง(Overestimate), ์ต์ ๋น์ฉ ์ถ์ , ์ต๋จ ๊ฒฝ๋ก ๋ณด์ฅ
- ํด์ค: ๏ปฟ์ ์ค์ ๋ชฉ์ ์ง๊น์ง ๋จ์ ๋น์ฉ์ ๊ณผ๋ํ๊ฐํด์๋ ์ ๋๋ฉฐ, ๊ฐ๋ฅํ ์ต์ ๋น์ฉ์ผ๋ก ์ถ์ ํด์ผ ์ต์ ์ ๊ธธ์ ๋์น์ง ์์ต๋๋ค. ์ง์ ๊ฑฐ๋ฆฌ๋ ๋ฌผ๋ฆฌ์ ์ผ๋ก ๋๋ฌํ ์ ์๋ ๊ฐ์ฅ ์งง์ ๊ฑฐ๋ฆฌ์ด๋ฏ๋ก, ์ค์ ๊ฒฝ๋ก ๋น์ฉ์ด ์ง์ ๊ฑฐ๋ฆฌ๋ณด๋ค ์์ ์ ์์ด ์์ ํ๊ณ ํฉ๋ฆฌ์ ์ธ๏ปฟ์ถ์ ๊ฐ์ด ๋ฉ๋๋ค.
Q7.
- ํต์ฌ ํค์๋: ๊น์ด ์ฐ์ ํ์(DFS), ๋ถ๋ชจ ๋
ธ๋์ ์๊ตฌ์ฌํญ(๏ปฟ), ํ์ ๋ฌด์๋ฏธ
- ํด์ค: Min ๋
ธ๋๋ ์์ ๋
ธ๋๋ค์ ํ์ํ๋ฉฐ ์ต์๊ฐ์ ์ฐพ์ต๋๋ค. ๋ง์ฝ ํ์ ๋์ค ๋ฐ๊ฒฌํ ๊ฐ์ด ๋ถ๋ชจ(Max ๋
ธ๋)๊ฐ ์ด๋ฏธ ํ๋ณดํ ์ต๋๊ฐ์ธ ๏ปฟ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค๋ฉด, ๋ถ๋ชจ ๋ ธ๋๋ ์์ ์ ์ด์ต์ ๊ทน๋ํํ๊ธฐ ์ํด ์ด์ฐจํผ ์ด Min ๋ ธ๋์ ๊ฒฝ๋ก๋ฅผ ์ ํํ์ง ์์ ๊ฒ์ ๋๋ค. ๋ฐ๋ผ์ ๋ ์ด์ ํ์ํ๋ ๊ฒ์ด ๋ฌด์๋ฏธํ๋ฏ๋ก ํ์์ ์ค๋จํฉ๋๋ค.
โก [์ํ ์ง์ 5๋ถ ์ปท] ๋ฒผ๋ฝ์น๊ธฐ ์์ฝ ์๊ธฐ์ฅ
- A ํ๊ฐ ํจ์:* ๏ปฟ.
- ํด๋ฆฌ์คํฑ(๏ปฟ) ์กฐ๊ฑด: ์ ๋ ์ค์ ๋น์ฉ์ ๊ณผ๋ํ๊ฐํ๋ฉด ์ ๋จ (ํผ์ฆ์ ์๋ชป๋ ์ซ์ํ ๊ฐ์, ๊ธธ ์ฐพ๊ธฐ๋ ์ง์ ๊ฑฐ๋ฆฌ ์ฌ์ฉ).
- OPEN vs CLOSED: OPEN์ ํ์ ๋๊ธฐ์ด(๏ปฟ์ต์๊ฐ ์ฐ์ ), CLOSED๋ ์ค๋ณต ๋ฐฉ์ง๋ฅผ ์ํ ๋ฐฉ๋ฌธ ์๋ฃ ๋ชฉ๋ก.
- Minimax ์๋ฆฌ: ์๋(Min)๋ ๋๋ฅผ ์ง๊ฒ ๋ง๋ค๋ ค ์ต์ ์ ๋คํ๊ณ , ๋(Max)๋ ๊ทธ์ค์์ ๋ด ์ ์๋ฅผ ์ต๋ํํ๋ ์๋ฅผ ๊ณ ๋ฆ.
- Alpha-beta Pruning: ๋ถ๋ชจ๊ฐ ์๊ตฌํ๋ ์กฐ๊ฑด(๏ปฟ๋๋๏ปฟ)์ ๋ง์กฑ์ํฌ ์ ์์์ ํ์ธํ๋ ์๊ฐ, ํ์ ๋ ธ๋ ํ์์ ์ฆ์ ์ค๋จํ์ฌ ์ฐ์ฐ๋์ ์ค์.
- MCTS 4๋จ๊ณ: Selection(์ ํ) ๏ปฟExpansion(ํ์ฅ)๏ปฟSimulation(์๋ฎฌ๋ ์ด์ )๏ปฟBackpropagation(์ญ์ ํ).
- ์ํ๊ณ ์ ํต์ฌ: MCTS์ '์ด๋์ ๋์ง'๋ฅผ ์ถ์ฒํ๋ ์ ์ฑ ๋ง(Policy Network)๊ณผ 'ํ์ฌ ํ์ธ๊ฐ ์ด๋ค์ง' ํ๊ฐํ๋ ๊ฐ์น๋ง(Value Network)์ ๊ฒฐํฉํจ.
๋ค๋ฅธ ๊ณต๊ฐ ๋ ธํธ
๊ณต๊ฐ ๋ ธํธ ๋ชจ๋ ๋ณด๊ธฐKYA ๊ธฐ๋ฐ ์์ด์ ํธ ์ธ์ฆ ํ๋กํ ์ฝ
2026๋ 11์ 18์ผ
๋ณด๊ธฐ
ํ๋ฅ MVP ๋ฒ์ ๋ฐ ๊ธฐ๋ฅ ์ ์ ํ์
2026๋ 11์ 17์ผ
๋ณด๊ธฐ
์ด์์ฒด์ 10/26
2026๋ 11์ 17์ผ
๋ณด๊ธฐ
New Note
2026๋ 11์ 16์ผ
๋ณด๊ธฐ
RLC ์คํ๊ณผ ์๊ธฐ์ฅ ์ธก์ ์คํ๊ธฐ๋ก
2026๋ 11์ 14์ผ
๋ณด๊ธฐ
ํ๋ณตํ ์๋๊ธฐ๋ฅผ ์ํ ๋ถ๋ชจ์ ์ดํด์ ์ํ์ง๋
2026๋ 11์ 13์ผ
๋ณด๊ธฐ