alt

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

  • ์ถœ์ œ ํฌ์ธํŠธ: ํ‰๊ฐ€ ํ•จ์ˆ˜
    f(n)=g(n)+h(n)f(n) = g(n) + h(n)๏ปฟ
    ์˜ ์˜๋ฏธ์™€ OPEN/CLOSED ๋ฆฌ์ŠคํŠธ๋ฅผ ํ™œ์šฉํ•œ ํƒ์ƒ‰ ๊ณผ์ • ์ดํ•ด
  • Why (์™œ ๋„์ž…๋˜์—ˆ๋‚˜): ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ชฉ์ ์ง€์™€ ๋ฌด๊ด€ํ•˜๊ฒŒ ๋ชจ๋“  ๋ฐฉํ–ฅ์„ ํƒ์ƒ‰ํ•˜์—ฌ ๋‚ญ๋น„๊ฐ€ ์‹ฌํ•จ. ๋ชฉ์ ์ง€๊นŒ์ง€์˜ ์ถ”์ • ๋น„์šฉ์„ ๊ณ ๋ คํ•˜์—ฌ ํƒ์ƒ‰ ๋น„์šฉ์„ ์ตœ์†Œํ™”ํ•˜๊ธฐ ์œ„ํ•ด ๋„์ž…๋จ.
  • How (์–ด๋–ป๊ฒŒ ์ž‘๋™ํ•˜๋‚˜):
  • g(n)g(n)๏ปฟ
    : ์‹œ์ž‘ ๋…ธ๋“œ์—์„œ ํ˜„์žฌ ๋…ธ๋“œ๊นŒ์ง€์˜ ์‹ค์ œ ๋ˆ„์  ๋น„์šฉ.
  • h(n)h(n)๏ปฟ
    (ํœด๋ฆฌ์Šคํ‹ฑ): ํ˜„์žฌ ๋…ธ๋“œ์—์„œ ๋ชฉ์ ์ง€๊นŒ์ง€์˜ ์ถ”์ • ๋น„์šฉ (์˜ˆ: ํผ์ฆ์˜ ์ œ์ž๋ฆฌ์— ์—†๋Š” ์ˆซ์žํŒ ๊ฐœ์ˆ˜, ์ง€๋„์ƒ์˜ ์ง์„ ๊ฑฐ๋ฆฌ).
  • OPEN ๋ฆฌ์ŠคํŠธ(ํƒ์ƒ‰ ํ›„๋ณด,
    ff๏ปฟ
    ๊ฐ’์ด ๊ฐ€์žฅ ์ž‘์€ ๊ฒƒ๋ถ€ํ„ฐ ์šฐ์„  ํƒ์ƒ‰)์™€ CLOSED ๋ฆฌ์ŠคํŠธ(๋ฐฉ๋ฌธ ์™„๋ฃŒ, ์ค‘๋ณต ํƒ์ƒ‰ ๋ฐฉ์ง€)๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํŠธ๋ฆฌ๋ฅผ ํ™•์žฅํ•จ.
  • Limit/Result (ํ•œ๊ณ„์  ๋ฐ ์˜์˜):
    h(n)h(n)๏ปฟ
    ์€ ์‹ค์ œ ๋น„์šฉ์„ ๊ณผ๋Œ€ํ‰๊ฐ€(overestimate)ํ•ด์„œ๋Š” ์•ˆ ๋˜๋ฉฐ, ๊ฐ€๋Šฅํ•œ ์‹ค์ œ ๋น„์šฉ์— ๊ฐ€๊น๊ฒŒ ์ตœ์†Œ ๋น„์šฉ์œผ๋กœ ์ถ”์ •ํ•ด์•ผ ์˜ฌ๋ฐ”๋ฅธ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ์Œ.

[์ฃผ์ œ๋ช… 2] Minimax Search & Alpha-beta Pruning

  • ์ถœ์ œ ํฌ์ธํŠธ: ์ ๋Œ€์  ๊ฒŒ์ž„ ํŠธ๋ฆฌ์—์„œ ๋ถˆํ•„์š”ํ•œ ํƒ์ƒ‰์„ ์ค„์ด๋Š” ๊ฐ€์ง€์น˜๊ธฐ(Pruning) ์›๋ฆฌ
  • Why (์™œ ๋„์ž…๋˜์—ˆ๋‚˜): ์ฒด์Šค๋‚˜ ํ‹ฑํƒํ† ์ฒ˜๋Ÿผ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์€ ์—ฐ์‚ฐ๋Ÿ‰์ด ๋„ˆ๋ฌด ๋ฐฉ๋Œ€ํ•จ. ์ƒ๋Œ€๋ฐฉ์ด ์ตœ์„ ์„ ๋‹คํ•ด ๋‚˜๋ฅผ ๋ฐฉํ•ดํ•œ๋‹ค๋Š” ๊ฐ€์ •ํ•˜์— ์ตœ์ ์˜ ์ˆ˜๋ฅผ ์ฐพ๊ณ , ๋ถˆํ•„์š”ํ•œ ๊ฒฝ๋กœ๋Š” ํƒ์ƒ‰ํ•˜์ง€ ์•Š๊ธฐ ์œ„ํ•ด ๋„์ž….
  • How (์–ด๋–ป๊ฒŒ ์ž‘๋™ํ•˜๋‚˜):
  • Minimax: Max ๋…ธ๋“œ(๋‚˜)๋Š” ์ž์‹ ์ค‘ ์ตœ๋Œ€๊ฐ’์„, Min ๋…ธ๋“œ(์ƒ๋Œ€)๋Š” ์ตœ์†Œ๊ฐ’์„ ์„ ํƒ.
  • Alpha-beta Pruning: ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS) ๋ฐฉ์‹์œผ๋กœ ์™ผ์ชฝ๋ถ€ํ„ฐ ํƒ์ƒ‰. Max ๋…ธ๋“œ๋Š”
    ฮฑ\alpha๏ปฟ
    (์ตœ๋Œ€๊ฐ’), Min ๋…ธ๋“œ๋Š”
    ฮฒ\beta๏ปฟ
    (์ตœ์†Œ๊ฐ’)๋ฅผ ์œ ์ง€. ๋งŒ์•ฝ Min ๋…ธ๋“œ๊ฐ€ ํƒ์ƒ‰ ์ค‘ ๋ถ€๋ชจ Max ๋…ธ๋“œ๊ฐ€ ์š”๊ตฌํ•˜๋Š”
    ฮฑ\alpha๏ปฟ
    ๋ณด๋‹ค ์ž‘์€ ๊ฐ’์„ ๋ฐœ๊ฒฌํ•˜๋ฉด, ๋ถ€๋ชจ๋Š” ์–ด์ฐจํ”ผ ๊ทธ ๊ฒฝ๋กœ๋ฅผ ์„ ํƒํ•˜์ง€ ์•Š์„ ๊ฒƒ์ด๋ฏ€๋กœ ๋‚˜๋จธ์ง€ ํƒ์ƒ‰์„ ์ค‘๋‹จ(Pruning)ํ•จ.
  • Limit/Result (ํ•œ๊ณ„์  ๋ฐ ์˜์˜): ํƒ์ƒ‰ ๋น„์šฉ์„ ํš๊ธฐ์ ์œผ๋กœ ์ค„์ผ ์ˆ˜ ์žˆ์œผ๋‚˜, ์—ฌ์ „ํžˆ ๋ฐ”๋‘‘๊ณผ ๊ฐ™์ด ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๊ทน๋„๋กœ ๋งŽ์€ ๊ฒŒ์ž„์—์„œ๋Š” ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ํ‰๊ฐ€ํ•˜๊ธฐ ์–ด๋ ค์›€.

[์ฃผ์ œ๋ช… 3] MCTS (Monte Carlo Tree Search)

  • ์ถœ์ œ ํฌ์ธํŠธ: ๋ฌด์ž‘์œ„ ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•œ ํŠธ๋ฆฌ ํƒ์ƒ‰ 4๋‹จ๊ณ„ ๋ฐ UCB1์˜ ์˜๋ฏธ
  • Why (์™œ ๋„์ž…๋˜์—ˆ๋‚˜): ๋ฐ”๋‘‘์ฒ˜๋Ÿผ ๋ถ„๊ธฐ ์ˆ˜๊ฐ€ ๋„ˆ๋ฌด ๋งŽ๊ณ (ํ‰๊ท  250์ˆ˜) ์ ๋‹นํ•œ ํ‰๊ฐ€ ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ธฐ ์–ด๋ ค์šด ๋ณต์žกํ•œ ๊ฒŒ์ž„์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ๋„์ž….
  • How (์–ด๋–ป๊ฒŒ ์ž‘๋™ํ•˜๋‚˜):
  1. Selection (์„ ํƒ): UCB1 ๊ณต์‹์„ ์‚ฌ์šฉํ•˜์—ฌ ์Šน๋ฅ (Exploitation)๊ณผ ํƒ์ƒ‰ ํšŸ์ˆ˜๊ฐ€ ์ ์€ ์ •๋„(Exploration)๋ฅผ ๊ณ ๋ คํ•ด ๋‹ค์Œ ๋…ธ๋“œ ์„ ํƒ.
  1. Expansion (ํ™•์žฅ): ์ž„์˜์˜ Action์„ ์„ ํƒํ•ด ํŠธ๋ฆฌ์— ๋…ธ๋“œ ์ถ”๊ฐ€.
  1. Simulation (์‹œ๋ฎฌ๋ ˆ์ด์…˜): ์ŠนํŒจ๊ฐ€ ๊ฒฐ์ •๋  ๋•Œ๊นŒ์ง€ ๋ฌด์ž‘์œ„๋กœ ๊ฒŒ์ž„ ์ง„ํ–‰.
  1. Backpropagation (์—ญ์ „ํŒŒ): ๊ฒŒ์ž„ ๊ฒฐ๊ณผ๋ฅผ ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฑฐ์Šฌ๋Ÿฌ ์˜ฌ๋ผ๊ฐ€๋ฉฐ ์Šน๋ฅ  ๋ฐ ์‹œ๋„ ํšŸ์ˆ˜ ํ†ต๊ณ„ ์—…๋ฐ์ดํŠธ.
  • Limit/Result (ํ•œ๊ณ„์  ๋ฐ ์˜์˜): ์‹œ๋ฎฌ๋ ˆ์ด์…˜์ด ๋งŽ์„์ˆ˜๋ก ํ†ต๊ณ„ ํŠธ๋ฆฌ๊ฐ€ ์ปค์ง€๊ณ  ๋…ธ๋“œ ๊ฐ’์˜ ์ •ํ™•๋„๊ฐ€ ํ–ฅ์ƒ๋จ. ์•ŒํŒŒ๊ณ ๋Š” ์—ฌ๊ธฐ์— ์ •์ฑ…๋ง(Policy Network)๊ณผ ๊ฐ€์น˜๋ง(Value Network)์„ ๊ฒฐํ•ฉํ•˜์—ฌ ์„ฑ๋Šฅ์„ ๊ทน๋Œ€ํ™”ํ•จ.

โš”๏ธ [ํ•„์ˆ˜ ์•”๊ธฐ] ํ—ท๊ฐˆ๋ฆฌ๋Š” ๊ฐœ๋… ๋น„๊ต

๋น„๊ต ํ•ญ๋ชฉ
[Max ๋…ธ๋“œ]
[Min ๋…ธ๋“œ]
ํ•ต์‹ฌ ์—ญํ• 
์ž์‹ ์˜ ์ด์ต(์ ์ˆ˜)์„ ์ตœ๋Œ€ํ™”ํ•˜๋Š” ์ˆ˜๋ฅผ ์„ ํƒ
์ƒ๋Œ€๋ฐฉ์˜ ์ด์ต์„ ์ตœ์†Œํ™”(๋‚˜๋ฅผ ์ง€๊ฒŒ ํ•จ)ํ•˜๋Š” ์ˆ˜๋ฅผ ์„ ํƒ
์œ ์ง€ ๋ณ€์ˆ˜
ฮฑ\alpha๏ปฟ
(์•ŒํŒŒ): ๋ฐœ๊ฒฌ๋œ ์ตœ๋Œ€๊ฐ’
ฮฒ\beta๏ปฟ
(๋ฒ ํƒ€): ๋ฐœ๊ฒฌ๋œ ์ตœ์†Œ๊ฐ’
Pruning ์กฐ๊ฑด
์ž์‹ ๋…ธ๋“œ์—์„œ
ฮฒโ‰คฮฑ\beta \le \alpha๏ปฟ
๊ฐ€ ๋˜๋ฉด ๊ฐ€์ง€์น˜๊ธฐ
์ž์‹ ๋…ธ๋“œ์—์„œ
ฮฑโ‰ฅฮฒ\alpha \ge \beta๏ปฟ
๊ฐ€ ๋˜๋ฉด ๊ฐ€์ง€์น˜๊ธฐ
โš ๏ธ [์ถœ์ œ์ž์˜ ํ•จ์ • ์ฃผ์˜!]A* ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ
h(n)h(n)๏ปฟ
์„ ๊ณ„์‚ฐํ•  ๋•Œ, ํผ์ฆ ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ '๋นˆ์นธ'์˜ ์œ„์น˜๊ฐ€ ํ‹€๋ฆฐ ๊ฒƒ์€ ์„ธ์ง€ ์•Š๊ณ  ์˜ค์ง '์ˆซ์žํŒ'์ด ์ž˜๋ชป๋œ ์œ„์น˜์— ์žˆ๋Š” ๊ฐœ์ˆ˜๋งŒ ์„ธ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. (๊ต์ˆ˜๋‹˜ ๊ฐ•์กฐ์‚ฌํ•ญ)

๏ปฟ

๐ŸŽฏ [์‹ค์ „ ๋ชจ์˜๊ณ ์‚ฌ] ๊ต์ˆ˜๋‹˜ ๋งž์ถคํ˜• ํ•˜๋“œ์ฝ”์–ด ํ›ˆ๋ จ

[์„น์…˜ 1: ๋‹จ๋‹ต ๋ฐ ๊ฐœ๋… ํ™•์ธํ˜•]
  • Q1. A* ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์ด๋ฏธ ๋ฐฉ๋ฌธํ•˜์—ฌ ๋‹ค์Œ ๋‹จ๊ณ„๋กœ ํ™•์žฅํ•œ ๋…ธ๋“œ๋“ค์„ ์ €์žฅํ•˜์—ฌ ์ค‘๋ณต ํƒ์ƒ‰์„ ๋ฐฉ์ง€ํ•˜๋Š” ๋ฆฌ์ŠคํŠธ์˜ ์ด๋ฆ„์€ ๋ฌด์—‡์ธ๊ฐ€?
  • Q2. ์ ๋Œ€์  ํƒ์ƒ‰์—์„œ ์ฃผ์‚ฌ์œ„๋‚˜ ํ™•๋ฅ ์  ์š”์†Œ๊ฐ€ ํฌํ•จ๋œ ๊ฒŒ์ž„์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด Max์™€ Min ๋…ธ๋“œ ์‚ฌ์ด์— ์ถ”๊ฐ€ํ•˜๋Š” ๋…ธ๋“œ๋Š” ๋ฌด์—‡์ธ๊ฐ€?
  • Q3. MCTS์˜ 4๋‹จ๊ณ„ ์ค‘, ๋ฆฌํ”„ ๋…ธ๋“œ์—์„œ ๊ฒŒ์ž„ ์ข…๋ฃŒ๊นŒ์ง€ ๋ฌด์ž‘์œ„๋กœ ์ˆ˜๋ฅผ ๋‘์–ด ์ŠนํŒจ๋ฅผ ํ™•์ธํ•˜๋Š” ๋‹จ๊ณ„๋Š” ๋ฌด์—‡์ธ๊ฐ€?
  • Q4. MCTS์—์„œ ํ˜„์žฌ๊นŒ์ง€ ์Šน๋ฅ ์ด ๋†’์€ ์ˆ˜๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ(Exploitation)๊ณผ ์•„์ง ์ถฉ๋ถ„ํžˆ ์‹œ๋„๋˜์ง€ ์•Š์€ ์ˆ˜๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ(Exploration)์˜ ๊ท ํ˜•์„ ๋งž์ถ”๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” ๊ณ„์‚ฐ์‹์˜ ์ด๋ฆ„์€ ๋ฌด์—‡์ธ๊ฐ€?
[์„น์…˜ 2: ์กฐ๊ฑด๋ถ€ ์ ์šฉ ๋ฐ ๊ณ„์‚ฐํ˜•]
  • Q5. 3x3 ์Šฌ๋ผ์ด๋”ฉ ํผ์ฆ์„ A* ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ’€๊ณ ์ž ํ•œ๋‹ค. ํ˜„์žฌ ๋…ธ๋“œ๊ฐ€ ์‹œ์ž‘ ์ƒํƒœ๋กœ๋ถ€ํ„ฐ 3๋ฒˆ ์ด๋™ํ•˜์—ฌ ๋„๋‹ฌํ–ˆ๊ณ , ๋ชฉํ‘œ ์ƒํƒœ์™€ ๋น„๊ตํ–ˆ์„ ๋•Œ ์ œ์ž๋ฆฌ์— ์žˆ์ง€ ์•Š์€ ์ˆซ์žํŒ(๋นˆ์นธ ์ œ์™ธ)์ด 4๊ฐœ๋ผ๋ฉด, ์ด ๋…ธ๋“œ์˜
    f(n)f(n)๏ปฟ
    ๊ฐ’์€ ์–ผ๋งˆ์ธ๊ฐ€?
[์„น์…˜ 3: ์„œ์ˆ ํ˜• ๋ฐ ๋…ผ์ˆ ํ˜•]
  • Q6. A* ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ํœด๋ฆฌ์Šคํ‹ฑ ํ•จ์ˆ˜
    h(n)h(n)๏ปฟ
    ์„ ์„ค์ •ํ•  ๋•Œ ์ฃผ์˜ํ•ด์•ผ ํ•  ํ•ต์‹ฌ ์›์น™์„ ์„ค๋ช…ํ•˜๊ณ , ๊ฒฝ๋กœ ํƒ์ƒ‰ ๋ฌธ์ œ์—์„œ '์ง์„ ๊ฑฐ๋ฆฌ'๋ฅผ
    h(n)h(n)๏ปฟ
    ์œผ๋กœ ์‚ฌ์šฉํ•˜๋Š” ์ด์œ ๋ฅผ ์„œ์ˆ ํ•˜์‹œ์˜ค.
  • Q7. Alpha-beta Pruning์—์„œ Min ๋…ธ๋“œ๊ฐ€ ํƒ์ƒ‰์„ ์ค‘๋‹จ(Pruning)ํ•˜๊ฒŒ ๋˜๋Š” ๋…ผ๋ฆฌ์  ์ด์œ ๋ฅผ Max ๋…ธ๋“œ์˜
    ฮฑ\alpha๏ปฟ
    ๊ฐ’๊ณผ ์—ฐ๊ด€ ์ง€์–ด ์„œ์ˆ ํ•˜์‹œ์˜ค.
<details>
<summary></summary>
[์„น์…˜ 1 ์ •๋‹ต]Q1. CLOSED ๋ฆฌ์ŠคํŠธ Q2. ํ™•๋ฅ  ๋…ธ๋“œ (Chance node / Expectiminimax) Q3. ์‹œ๋ฎฌ๋ ˆ์ด์…˜ (Simulation) Q4. UCB1
[์„น์…˜ 2 ์ •๋‹ต]Q5. 7 (
f(n)=g(n)+h(n)=3+4=7f(n) = g(n) + h(n) = 3 + 4 = 7๏ปฟ
)
[์„น์…˜ 3 ์ •๋‹ต ๋ฐ ์ฑ„์  ๊ธฐ์ค€]Q6.
  • ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ: ๊ณผ๋Œ€ํ‰๊ฐ€ ๋ฐฉ์ง€(Overestimate), ์ตœ์†Œ ๋น„์šฉ ์ถ”์ •, ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ณด์žฅ
  • ํ•ด์„ค:
    h(n)h(n)๏ปฟ
    ์€ ์‹ค์ œ ๋ชฉ์ ์ง€๊นŒ์ง€ ๋‚จ์€ ๋น„์šฉ์„ ๊ณผ๋Œ€ํ‰๊ฐ€ํ•ด์„œ๋Š” ์•ˆ ๋˜๋ฉฐ, ๊ฐ€๋Šฅํ•œ ์ตœ์†Œ ๋น„์šฉ์œผ๋กœ ์ถ”์ •ํ•ด์•ผ ์ตœ์ ์˜ ๊ธธ์„ ๋†“์น˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ์ง์„ ๊ฑฐ๋ฆฌ๋Š” ๋ฌผ๋ฆฌ์ ์œผ๋กœ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ์งง์€ ๊ฑฐ๋ฆฌ์ด๋ฏ€๋กœ, ์‹ค์ œ ๊ฒฝ๋กœ ๋น„์šฉ์ด ์ง์„ ๊ฑฐ๋ฆฌ๋ณด๋‹ค ์ž‘์„ ์ˆ˜ ์—†์–ด ์•ˆ์ „ํ•˜๊ณ  ํ•ฉ๋ฆฌ์ ์ธ
    h(n)h(n)๏ปฟ
    ์ถ”์ •๊ฐ’์ด ๋ฉ๋‹ˆ๋‹ค.
Q7.
  • ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ: ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS), ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์š”๊ตฌ์‚ฌํ•ญ(
    ฮฑ\alpha๏ปฟ
    ), ํƒ์ƒ‰ ๋ฌด์˜๋ฏธ
  • ํ•ด์„ค: Min ๋…ธ๋“œ๋Š” ์ž์‹ ๋…ธ๋“œ๋“ค์„ ํƒ์ƒ‰ํ•˜๋ฉฐ ์ตœ์†Œ๊ฐ’์„ ์ฐพ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ํƒ์ƒ‰ ๋„์ค‘ ๋ฐœ๊ฒฌํ•œ ๊ฐ’์ด ๋ถ€๋ชจ(Max ๋…ธ๋“œ)๊ฐ€ ์ด๋ฏธ ํ™•๋ณดํ•œ ์ตœ๋Œ€๊ฐ’์ธ
    ฮฑ\alpha๏ปฟ
    ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค๋ฉด, ๋ถ€๋ชจ ๋…ธ๋“œ๋Š” ์ž์‹ ์˜ ์ด์ต์„ ๊ทน๋Œ€ํ™”ํ•˜๊ธฐ ์œ„ํ•ด ์–ด์ฐจํ”ผ ์ด Min ๋…ธ๋“œ์˜ ๊ฒฝ๋กœ๋ฅผ ์„ ํƒํ•˜์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๋” ์ด์ƒ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด ๋ฌด์˜๋ฏธํ•˜๋ฏ€๋กœ ํƒ์ƒ‰์„ ์ค‘๋‹จํ•ฉ๋‹ˆ๋‹ค.
</details>

๏ปฟ

โšก [์‹œํ—˜ ์ง์ „ 5๋ถ„ ์ปท] ๋ฒผ๋ฝ์น˜๊ธฐ ์š”์•ฝ ์•”๊ธฐ์žฅ

  1. A ํ‰๊ฐ€ ํ•จ์ˆ˜:*
    f=g(๊ณผ๊ฑฐย ๋ˆ„์ ย ๋น„์šฉ)+h(๋ฏธ๋ž˜ย ์ถ”์ •ย ๋น„์šฉ)f = g(\text{๊ณผ๊ฑฐ ๋ˆ„์  ๋น„์šฉ}) + h(\text{๋ฏธ๋ž˜ ์ถ”์ • ๋น„์šฉ})๏ปฟ
    .
  1. ํœด๋ฆฌ์Šคํ‹ฑ(
    hh๏ปฟ
    ) ์กฐ๊ฑด: ์ ˆ๋Œ€ ์‹ค์ œ ๋น„์šฉ์„ ๊ณผ๋Œ€ํ‰๊ฐ€ํ•˜๋ฉด ์•ˆ ๋จ (ํผ์ฆ์€ ์ž˜๋ชป๋œ ์ˆซ์žํŒ ๊ฐœ์ˆ˜, ๊ธธ ์ฐพ๊ธฐ๋Š” ์ง์„ ๊ฑฐ๋ฆฌ ์‚ฌ์šฉ).
  1. OPEN vs CLOSED: OPEN์€ ํƒ์ƒ‰ ๋Œ€๊ธฐ์—ด(
    ff๏ปฟ
    ์ตœ์†Ÿ๊ฐ’ ์šฐ์„ ), CLOSED๋Š” ์ค‘๋ณต ๋ฐฉ์ง€๋ฅผ ์œ„ํ•œ ๋ฐฉ๋ฌธ ์™„๋ฃŒ ๋ชฉ๋ก.
  1. Minimax ์›๋ฆฌ: ์ƒ๋Œ€(Min)๋Š” ๋‚˜๋ฅผ ์ง€๊ฒŒ ๋งŒ๋“ค๋ ค ์ตœ์„ ์„ ๋‹คํ•˜๊ณ , ๋‚˜(Max)๋Š” ๊ทธ์ค‘์—์„œ ๋‚ด ์ ์ˆ˜๋ฅผ ์ตœ๋Œ€ํ™”ํ•˜๋Š” ์ˆ˜๋ฅผ ๊ณ ๋ฆ„.
  1. Alpha-beta Pruning: ๋ถ€๋ชจ๊ฐ€ ์š”๊ตฌํ•˜๋Š” ์กฐ๊ฑด(
    ฮฑ\alpha๏ปฟ
    ๋˜๋Š”
    ฮฒ\beta๏ปฟ
    )์„ ๋งŒ์กฑ์‹œํ‚ฌ ์ˆ˜ ์—†์Œ์„ ํ™•์ธํ•˜๋Š” ์ˆœ๊ฐ„, ํ•˜์œ„ ๋…ธ๋“œ ํƒ์ƒ‰์„ ์ฆ‰์‹œ ์ค‘๋‹จํ•˜์—ฌ ์—ฐ์‚ฐ๋Ÿ‰์„ ์ค„์ž„.
  1. MCTS 4๋‹จ๊ณ„: Selection(์„ ํƒ)
    โ†’\rightarrow๏ปฟ
    Expansion(ํ™•์žฅ)
    โ†’\rightarrow๏ปฟ
    Simulation(์‹œ๋ฎฌ๋ ˆ์ด์…˜)
    โ†’\rightarrow๏ปฟ
    Backpropagation(์—ญ์ „ํŒŒ).
  1. ์•ŒํŒŒ๊ณ ์˜ ํ•ต์‹ฌ: MCTS์— '์–ด๋””์— ๋‘˜์ง€'๋ฅผ ์ถ”์ฒœํ•˜๋Š” ์ •์ฑ…๋ง(Policy Network)๊ณผ 'ํ˜„์žฌ ํŒ์„ธ๊ฐ€ ์–ด๋–ค์ง€' ํ‰๊ฐ€ํ•˜๋Š” ๊ฐ€์น˜๋ง(Value Network)์„ ๊ฒฐํ•ฉํ•จ.
๊ณต๊ฐœ ๋…ธํŠธ ๋ชจ๋‘ ๋ณด๊ธฐ