#

අසම්පූර්ණතොරතුරු සහිත ක්රීඩා වල අවම කිරීම කනගාටු කරන්න (CFR)

කඩදාසි කනගාටුව අසම්පූර්ණ තොරතුරු සහිත ක්රීඩා වල අවම කිරීම ප්රතිවිරුද්ධ කනගාටුව හඳුන්වා දෙන අතර ස්වයං නාට්යය තුළින් ප්රතිවිරුද්ධ කනගාටුව අවම කිරීම නැෂ් සමතුලිතතාවයට ළඟා වීමට භාවිතා කළ හැකි ආකාරය. ඇල්ගොරිතම හැඳින්වෙන්නේ ප්රතිවිරුද්ධ කනගාටුව අවම කිරීම (CFR) ලෙසිනි.

පුළුල් ක්රීඩා වල කනගාටුව අවම කිරීම සඳහා මොන්ටේ කාලෝ නියැදීම කඩදාසි මොන්ටේ කාලෝ ප්රතිවිරුද්ධ කනගාටුව අවම කිරීම (MCCFR) හඳුන්වා දෙයි, එහිදී අපි ක්රීඩා ගසෙන් සාම්පල ලබාගෙන කනගාටුව තක්සේරු කරමු.

අපගේපයිතන් ක්රියාත්මක කිරීම නිබන්ධනයක් මෙන් පහසුවෙන් තේරුම් ගැනීමට අපි උත්සාහ කළෙමු. අපි එය ඉතා සරල අසම්පූර්ණ තොරතුරු ක්රීඩාවක් මත ධාවනය කරමු Kuhn පෝකර් ගහන්න දන්නවානම්.

ට්විටර් නූල්

හැඳින්වීම

අපිඅහම්බෙන් නියැදීම් (CS) සමඟ මොන්ටේ කාලෝ ප්රතිවිරුද්ධ කනගාටුව අවම කිරීම (MCCFR) ක්රියාත්මක කරමු. එය iteratively, සියලු ක්රීඩකයා ක්රියා උත්සාහ ක්රීඩාව ගස කොටසක් ගවේෂණය, නමුත් අවස්ථාවක් සිදුවීම් නියැදීම්. අවස්ථාවක් සිදුවීම් කාඩ්පත් ගනුදෙනු වැනි දේවල් ය; ඔවුන් නැවත එක් වරක් sampled තබා ඇත. එවිට එය ගණනය කරන්නේ, එක් එක් ක්රියාව සඳහා, එම පියවර ගැනීම වෙනුවට වර්තමාන උපායමාර්ගය අනුගමනය කිරීමේ කනගාටුව . ඉන්පසු එය කනගාටුව ගැලපීම භාවිතා කරමින් ඊළඟ පුනරාවර්තනය සඳහා මෙම කනගාටු මත පදනම් වූ උපාය යාවත්කාලීන කරයි. අවසාන වශයෙන්, එය පුනරාවර්තන පුරා උපාය මාර්ගවල සාමාන්යය ගණනය කරයි, එය අප ප්රමාණවත් පුනරාවර්තන දිව ගියහොත් නැෂ් සමතුලිතතාවයට ඉතා සමීප වේ.

අපිමුලින්ම ගණිතමය අංකනය සහ න්යාය හඳුන්වා දෙන්නෙමු.

ක්රීඩකයා

ක්රීඩකයෙක්විසින් දැක්වේ $i \in N$ , ක්රීඩකයන් සමූහයක් $N$ කොහෙද.

ඉතිහාසය

ඉතිහාසය $h \in H$ යනු ඇතුළු ක්රියා වල අනුක්රමයකි අවස්ථාවක් සිදුවීම්, $H$ එය සියලු ඉතිහාසයන්ගේ සමූහයයි.

$Z \subseteq H$ යනු පර්යන්ත ඉතිහාස සමූහයයි (ක්රීඩාව අවසන්).

ක්රියාව

ක්රියාව $a$ , පර්යන්ත $h \in H$ නොවන ඉතිහාසයක් $A (h) = a : (h, a) \in H$ කොහේද?

තොරතුරු කට්ටලය $I_{i}$

ක්රීඩකයා $I_{i} \in I_{i}$ සඳහාසකසා ඇති තොරතුරු ඉතිහාසයකට සමාන $i$ වන $h \in H$ නමුත් ක්රීඩකයාට පෙනෙන ක්රියාවන් පමණක් අඩංගු වේ $i$ . එනම්, ඉතිහාසයේ ප්රතිවිරුද්ධ ක්රීඩකයාට ගනුදෙනු $h$ කරන කාඩ්පත් වැනි ක්රියාවන්/සිදුවීම් අඩංගු වන අතර ඒවා $I_{i}$ නොලැබෙනු ඇත.

$I_{i}$ ක්රීඩකයාගේ තොරතුරු කොටස ලෙස හැඳින්වේ $i$ .

$h \in I$ යනු ලබා දී ඇති තොරතුරු කට්ටලයකට අයත් සියලු ඉතිහාස සමූහයයි; එනම් එම සියලු ඉතිහාසයන් ක්රීඩකයාගේ ඇසට සමාන වේ.

උපායමාර්ගය

ක්රීඩකයාගේඋපාය මාර්ගය $i$ , ක්රියාවන්ට වඩා බෙදා $σ_{i} \in Σ_{i}$ හැරීමකි $A (I_{i})$ , ක්රීඩකයා සඳහා සියලු උපාය මාර්ග සමූහයක් $Σ_{i}$ කොහේද $i$ . $t$ -th පුනරාවර්තනය පිළිබඳ උපාය මාර්ග මගින් $σ^{t}_{i}$ දැක්වේ.

මූලෝපායඅර්ථ දක්වා ඇත්තේ $a$ දී ඇති තොරතුරු කට්ටලයක් සඳහා ක්රියාමාර්ගයක් ගැනීමේ සම්භාවිතාවක් ලෙස ය $I$ ,

$σ_{i} (I) (a)$

$σ$ සියලුම ක්රීඩකයන්ගේ උපාය මාර්ග වලින් සමන්විත උපාය මාර්ග පැතිකඩයි $σ_{1}, σ_{2}, \dots$

$σ_{- i}$ හැර සියලුම ක්රීඩකයන්ගේ උපාය මාර්ග වේ $σ_{i}$

ඉතිහාසයේසම්භාවිතාව

$π^{σ} (h)$ උපාය මාර්ග පැතිකඩ $h$ සමඟ ඉතිහාසය කරා ළඟා වීමේ සම්භාවිතාව $σ$ වේ. $π^{σ} (h)_{- i}$ $i$ ක්රීඩකයාගේ දායකත්වය $h$ නොමැතිව ළඟා වීමේ සම්භාවිතාව; එනම් $i$ ක්රීඩකයා අනුගමනය කළ යුතු ක්රියාමාර්ග $h$ සම්භාවිතාවක් සමඟ $1$ .

$π^{σ} (h)_{i}$ පමණක් ක්රීඩකයා $i$ දායකත්වය $h$ සමග ළඟා වීමේ සම්භාවිතාව වේ. එනම්, $π^{σ} (h) = π^{σ} (h)_{i} π^{σ} (h)_{- i}$

තොරතුරුකට්ටලයක් වෙත ළඟා වීමේ $I$ සම්භාවිතාව, $π^{σ} (I) = h \in I \sum π^{σ} (h)$

උපයෝගීතාව(ගෙවන්න)

පර්යන්ත උපයෝගීතාව යනු පර්යන්ත ඉතිහාසයක් $i$ සඳහා ක්රීඩකයෙකුගේ උපයෝගීතාව (හෝ ගෙවීම) $h$ ය.

$u_{i} (h)$ කොහේද $h \in Z$

$u_{i} (σ)$ උපාය මාර්ග පැතිකඩ $i$ සහිත ක්රීඩකයා සඳහා අපේක්ෂිත උපයෝගීතාව (ගෙවීම්) $σ$ වේ.

$u_{i} (σ) = h \in Z \sum u_{i} (h) π^{σ} (h)$

නැෂ්සමතුලිතතාවය

නැෂ්සමතුලිතතාවය යනු ක්රීඩකයින්ගෙන් කිසිවෙකුට ඔවුන්ගේ උපාය මාර්ගය වෙනස් කිරීමෙන් ඔවුන්ගේ අපේක්ෂිත උපයෝගීතාව (හෝ ගෙවීම්) වැඩි කළ නොහැකි රාජ්යයකි.

ක්රීඩකයන්දෙදෙනෙකු සඳහා, නැෂ් සමතුලිතතාවය යනු උපාය මාර්ගික පැතිකඩකි

u_{1} (σ) u_{2} (σ) \geq m a x_{σ_{1}^{'} \in Σ_{1}} u_{1} (σ_{1}^{'}, σ_{2}) \geq m a x_{σ_{2}^{'} \in Σ_{2}} u_{1} (σ_{1}, σ_{2}^{'})

$ϵ$ -නැෂ් සමතුලිතතාවය,

u_{1} (σ) + ϵ u_{2} (σ) + ϵ \geq m a x_{σ_{1}^{'} \in Σ_{1}} u_{1} (σ_{1}^{'}, σ_{2}) \geq m a x_{σ_{2}^{'} \in Σ_{2}} u_{1} (σ_{1}, σ_{2}^{'})

අවමකිරීම කනගාටු

කනගාටුවවන්නේ උපයෝගීතාව (හෝ ගෙවීම) ක්රීඩකයාට නොලැබුනේ ඇය ප්රශස්ත උපාය මාර්ගයක් අනුගමනය නොකිරීම හෝ හොඳම පියවර ගැනීම නිසාය.

ක්රීඩකයා $i$ සඳහා සාමාන්ය සමස්ත කනගාටුව පුනරාවර්තන සෑම $T$ වටයකම ප්රශස්ත උපාය අනුගමනය නොකිරීම පිළිබඳ සාමාන්ය කනගාටුවයි.

$R_{i}^{T} = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T (u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - u_{i} (σ^{t}))$

පුනරාවර්තනයේසියලුම ක්රීඩකයින්ගේ උපාය මාර්ග පැතිකඩ $σ^{t}$ කොහේද $t$ , සහ

$(σ_{i}^{*}, σ^{t}_{- i})$

යනු $i$ ක්රීඩකයාගේ උපාය $σ^{t}$ සමඟ ප්රතිස්ථාපනය කරන ලද උපාය $σ_{i}^{*}$ මාර්ගයයි.

සාමාන්යඋපායමාර්ගය වන්නේ සෑම වටයකදීම අනුගමනය කරන උපාය මාර්ගවල සාමාන්යයයි $I \in I, a \in A (I)$

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

ප්රශස්තඋපායමාර්ගය සමඟ සෙල්ලම් නොකිරීමේ මධ්යන්ය කනගාටුව එයයි.

සියලුමක්රීඩකයින් $R_{i}^{T} < ϵ$ සඳහා නම් $2 ϵ$ -නැෂ් සමතුලිතතාවයකි. $\overset{σ}{ˉ}_{i}^{T} (I) (a)$

R_{i}^{T} R_{i}^{T} < ϵ = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T (u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - u_{i} (σ^{t})) = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - \frac{1}{T} t = 1 \sum T u_{i} (σ^{t}) < ϵ

එයශුන්ය මුදලක් ක්රීඩාවක් $u_{1} = - u_{2}$ බැවින්, අපට එකතු කළ හැකි $R_{1}^{T}$ $R_{i}^{T}$ අතර දෙවන වාරය අවලංගු වේ.

2 ϵ > \frac{1}{T} m a x_{σ_{1}^{*} \in Σ_{1}} t = 1 \sum T u_{1} (σ_{1}^{*}, σ^{t}_{- 1}) + \frac{1}{T} m a x_{σ_{2}^{*} \in Σ_{2}} t = 1 \sum T u_{2} (σ_{2}^{*}, σ^{t}_{- 2})

උපාය මාර්ග

සමූහයක් පුරා උපයෝගිතා වල සාමාන්යය සාමාන්ය උපාය මාර්ගයේ උපයෝගීතාවයට සමාන වේ.

$\frac{1}{T} t = 1 \sum T u_{i} (σ^{t}) = u_{i} (\overset{σ}{ˉ}^{T})$

එබැවින්,

2 ϵ > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T}) + m a x_{σ_{2}^{*} \in Σ_{2}} u_{2} (σ_{2}^{*}, \overset{σ}{ˉ}_{- 2}^{T})

අර්ථදැක්වීමෙන් $m a x$ , $m a x_{σ_{2}^{*} \in Σ_{2}} u_{2} (σ_{2}^{*}, \overset{σ}{ˉ}_{- 2}^{T}) \geq u_{2} (\overset{σ}{ˉ}^{T}) = - u_{1} (\overset{σ}{ˉ}^{T})$

එවිට,

2 ϵ u_{1} (\overset{σ}{ˉ}^{T}) + 2 ϵ > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T}) + - u_{1} (\overset{σ}{ˉ}^{T}) > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T})

මෙය $2 ϵ$ -නැෂ් සමතුලිතතාවයයි. ඔබට ඒ හා සමානව ක්රීඩකයින් 2 කට වඩා ඇති ක්රීඩා සඳහා ඔප්පු කළ හැකිය.

එබැවින්නැෂ් සමතුලිතතාවයකට සමීප $R_{i}^{T}$ වීමට අප අවම කළ යුතුය.

ප්රතිවිරුද්ධකනගාටුව

Counterfactualඅගය $v_{i} (σ, I)$ ක්රීඩකයා ළඟා වීමට $i$ උත්සාහ $i$ නම් ක්රීඩකයා සඳහා අපේක්ෂිත උපයෝගීතාව $I$ (ක්රියා ගෙන ක සම්භාවිතාව $I$ සමග ප්රමුඛ $1$ ).

$v_{i} (σ, I) = z \in Z_{I} \sum π^{σ_{- i}} (z [I]) π^{σ} (z [I], z) u_{i} (z)$

පර්යන්තඉතිහාස කට්ටලය වෙත ළඟා විය හැකි $I$ අතර $z [I]$ එය $z$ දක්වා උපසර්ගය වේ $Z_{I}$ $I$ . $π^{σ} (z [I], z)$ සිට z වෙත ළඟා වීමේ සම්භාවිතාව $z [I]$ වේ.

ක්ෂණිකප්රතිවිරුද්ධ කනගාටුව නම්,

$R_{i, i mm}^{T} (I) = m a x_{a \in A I} R_{i, i mm}^{T} (I, a)$

කොහේද

$R_{i, i mm}^{T} (I) = \frac{1}{T} t = 1 \sum T (v_{i} (σ^{t} ∣_{I \to a}, I) - v_{i} (σ^{t}, I))$

තොරතුරුකට්ටලයේ $σ ∣_{I \to a}$ සෑම විටම පියවර $a$ ගැනීම වෙනස් කිරීම $σ$ සමඟ උපාය පැතිකඩ $I$ කොහේද?

පත්රිකාව එය සනාථ කරයි (ප්රමේයය 3),

$R_{i}^{T} \leq I \in I \sum R_{i, i mm}^{T, +} (I)$ කොහේද $R_{i, i mm}^{T, +} (I) = m a x (R_{i, i mm}^{T} (I), 0)$

කනගාටුගැලපීම

උපායමාර්ගයගණනය කරනු ලබන්නේ කනගාටු ගැලපීම භාවිතා කරමිනි.

එක්එක් තොරතුරු කට්ටලය සහ ක්රියාකාරී යුගලය සඳහා කනගාටුව පවත්වා ගෙන $R_{i}^{T} (I, a)$ යනු ලැබේ,

r_{i}^{t} (I, a) R_{i}^{T} (I, a) = v_{i} (σ^{t} ∣_{I \to a}, I) - v_{i} (σ^{t}, I) = \frac{1}{T} t = 1 \sum T r_{i}^{t} (I, a)

උපායමාර්ගයගණනය කරනු ලබන්නේ කනගාටු ගැලපීමෙන්,

σ_{i}^{T + 1} (I) (a) = ⎩ ⎨ ⎧ \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}, \frac{1}{∣ A ( I )∣}, i f \sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0 o t h erw i se

කොහේද $R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

කඩදාසි අසම්පූර්ණ තොරතුරු සහිත ක්රීඩා වල කනගාටුව අවම කිරීම ඉහත සමීකරණයට අනුව උපාය මාර්ගය තෝරා $R_{i}^{T}$ ගන්නේ නම් ඊට සමානුපාතිකව කුඩා වන බව ඔප්පු කරයි $\frac{1}{T}$ , එබැවින් ළඟා වේ $ϵ$ -නෂ් සමතුලිතතාවය.

මොන්ටේකාලෝ CFR (MCCFR)

පරිගණකකරණයටඑක් එක් පුනරාවර්තනයේ සම්පූර්ණ ක්රීඩා ගස පුළුල් කිරීම $r_{i}^{t} (I, a)$ අවශ්ය වේ.

පුළුල් ක්රීඩා වල කනගාටුව අවම කිරීම සඳහා කඩදාසි මොන්ටේ කාලෝ නියැදීම අපට ක්රීඩා ගසෙන් සාම්පල ලබා ගත හැකි අතර කනගාටුව තක්සේරු කළ හැකිය.

$Q = Q_{1}, \dots, Q_{r}$ යනු උප කට්ටල සමූහයකි $Z$ ( $Q_{j} \subseteq Z$ ) එහිදී අපි පුනරාවර්තනයක තනි බ්ලොක් $Q_{j}$ එකක් පමණක් දෙස බලමු. සියලුම උප කුලවල සංගමය විහිදේ $Z$ ( $Q_{1} \cap \dots \cap Q_{r} = Z$ ). $q_{j}$ බ්ලොක් තෝරා ගැනීමේ සම්භාවිතාව $Q_{j}$ .

$q (z)$ වත්මන් පුනරාවර්තනයේ $z$ දී තෝරා ගැනීමේ සම්භාවිතාව; i.e. $q (z) = \sum_{j : z \in Q_{j}} q_{j}$ - $q_{j}$ කොතැනද එකතුව $z \in Q_{j}$ .

එවිටඅපි වාරණ සිට sampled counterfactual අගය ලබා $j$ ,

$\tilde{v} (σ, I ∣ j) = z \in Q_{j} \sum \frac{1}{q ( z )} π^{σ_{- i}} (z [I]) π^{σ} (z [I], z) u_{i} (z)$

කඩදාසිබව පෙන්නුම්

$E_{j \sim q_{j}} [\tilde{v} (σ, I ∣ j)] = v_{i} (σ, I)$

සරලසාක්ෂියක් සමඟ.

එබැවින්අපට ක්රීඩා ගසේ කොටසක් සාම්පල ගත කර කනගාටු ගණනය කළ හැකිය. කනගාටුව පිළිබඳ ඇස්තමේන්තුවක් අපි ගණනය කරමු

$\tilde{r}_{i}^{t} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I)$

එක්එක් පුනරාවර්තනයේ උපාය $σ_{i}^{T + 1} (I) (a)$ යාවත්කාලීන කිරීමට $R_{i}^{T} (I, a)$ සහ ගණනය කිරීමට එය භාවිතා කරන්න. අවසාන වශයෙන්, අපි සමස්ත සාමාන්ය උපාය ගණනය කරමු $\overset{σ}{ˉ}_{i}^{T} (I) (a)$ .

මෙන්න කුහ්න් පෝකර් මත CFR උත්සාහ කිරීමට Kuhn පෝකර් ක්රියාත්මක කිරීම.

අපි

කේතයට කිමිදෙමු!

328from typing import NewType, Dict, List, Callable, cast
329
330from labml import monit, tracker, logger, experiment
331from labml.configs import BaseConfigs, option

#

ක්රීඩකයන්ගේකට්ටලය $i \in N$ $N$ කොහෙද ක්රීඩකයෙක්

334Player = NewType('Player', int)

#

ක්රියාව $a$ , පර්යන්ත $h \in H$ නොවන ඉතිහාසයක් $A (h) = a : (h, a) \in H$ කොහේද?

336Action = NewType('Action', str)

#

ඉතිහාසය

ඉතිහාසය $h \in H$ යනු ඇතුළු ක්රියා වල අනුක්රමයකි අවස්ථාවක් සිදුවීම්, $H$ එය සියලු ඉතිහාසයන්ගේ සමූහයයි.

මෙමපන්තිය ක්රීඩා විශේෂිත තර්කනය සමඟ දීර් can කළ යුතුය.

339class History:

#

එයපර්යන්ත ඉතිහාසයක් වේවා; එනම් ක්රීඩාව අවසන්. $h \in Z$

351    def is_terminal(self):

#

356        raise NotImplementedError()

#

පර්යන්ත ඉතිහාසයක් $i$ සඳහා ක්රීඩකයාගේ උපයෝගීතාව. $u_{i} (h)$ කොහේද $h \in Z$

358    def terminal_utility(self, i: Player) -> float:

#

364        raise NotImplementedError()

#

වත්මන්ක්රීඩකයා ලබා ගන්න, විසින් දැක්වේ $P (h)$ , එහිදී ක්රීඩකයා උත්සවයලෙස $P$ හැඳින්වේ.

වර්තමාන $c$ සිදුවීම අවස්ථාවක් අවස්ථාවක් බව $P (h) = c$ එයින් අදහස් කරන්නේ නම්. කාඩ්පත් ගනුදෙනු කිරීම හෝ පෝකර් වල පොදු කාඩ්පත් විවෘත කිරීම වැනි දෙයක්.

366    def player(self) -> Player:

#

373        raise NotImplementedError()

#

ඊළඟපියවර අහම්බෙන් පියවරක් වේවා; නව කාඩ්පතක් ගනුදෙනු කිරීම වැනි දෙයක්. $P (h) = c$

375    def is_chance(self) -> bool:

#

380        raise NotImplementedError()

#

කවදාදඅවස්ථාවක් සාම්පලය $P (h) = c$ .

382    def sample_chance(self) -> Action:

#

386        raise NotImplementedError()

#

ඉතිහාසයටක්රියාවක් එක් කරන්න.

388    def __add__(self, action: Action):

#

392        raise NotImplementedError()

#

වත්මන්ක්රීඩකයා සඳහා තොරතුරු ලබා ගන්න

394    def info_set_key(self) -> str:

#

398        raise NotImplementedError

#

වත්මන්ක්රීඩකයා සඳහා නව තොරතුරු කට්ටලයක් සාදන්න

400    def new_info_set(self) -> 'InfoSet':

#

404        raise NotImplementedError()

#

මානවකියවිය හැකි නිරූපණය

406    def __repr__(self):

#

410        raise NotImplementedError()

#

තොරතුරුකට්ටලය $I_{i}$

413class InfoSet:

#

අද්විතීයයතුර තොරතුරු කට්ටලය හඳුනා ගැනීම

421    key: str

#

$σ_{i}$ , ක්රීඩකයාගේ උපාය $i$

423    strategy: Dict[Action, float]

#

එක්එක් පියවර නොගැනීම පිළිබඳ සම්පූර්ණ කනගාටුව $A (I_{i})$ ,

\tilde{r}_{i}^{t} (I, a) R_{i}^{T} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I) = \frac{1}{T} t = 1 \sum T \tilde{r}_{i}^{t} (I, a)

පරිගණකඋපාය විට $\frac{1}{T}$ කාලීන කෙසේ හෝ සිදු අවලංගු $R_{i}^{T} (I, a)$ සිට අපි $T R_{i}^{T} (I, a)$ ඒ වෙනුවට පවත්වාගෙන $σ_{i}^{T + 1} (I) (a)$

438    regret: Dict[Action, float]

#

සමස්තසාමාන්ය උපායමාර්ගය ගණනය $t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$ කිරීම සඳහා අපි සමුච්චිත උපාය මාර්ගය පවත්වා ගනිමු

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

445    cumulative_strategy: Dict[Action, float]

#

ආරම්භකරන්න

447    def __init__(self, key: str):

#

451        self.key = key
452        self.regret = {a: 0 for a in self.actions()}
453        self.cumulative_strategy = {a: 0 for a in self.actions()}
454        self.calculate_strategy()

#

ක්‍රියා $A (I_{i})$

456    def actions(self) -> List[Action]:

#

460        raise NotImplementedError()

#

සුරකිනලද ශබ්දකෝෂයකින් තොරතුරු කට්ටලය පූරණය කරන්න

462    @staticmethod
463    def from_dict(data: Dict[str, any]) -> 'InfoSet':

#

467        raise NotImplementedError()

#

ශබ්දකෝෂයකට සකසා ඇති තොරතුරු සුරකින්න

469    def to_dict(self):

#

473        return {
474            'key': self.key,
475            'regret': self.regret,
476            'average_strategy': self.cumulative_strategy,
477        }

#

සුරකිනලද ශබ්දකෝෂයකින් දත්ත පූරණය කරන්න

479    def load_dict(self, data: Dict[str, any]):

#

483        self.regret = data['regret']
484        self.cumulative_strategy = data['average_strategy']
485        self.calculate_strategy()

#

උපායගණනය

කනගාටු ගැලපීමභාවිතා කරමින් වත්මන් උපාය ගණනය කරන්න.

σ_{i}^{T + 1} (I) (a) = ⎩ ⎨ ⎧ \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}, \frac{1}{∣ A ( I )∣}, i f \sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0 o t h erw i se

කොහේද $R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

487    def calculate_strategy(self):

#

$R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

506        regret = {a: max(r, 0) for a, r in self.regret.items()}

#

$a^{'} \in A (I) \sum R_{i}^{T, +} (I, a^{'})$

508        regret_sum = sum(regret.values())

#

නම් $\sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0$ ,

510        if regret_sum > 0:

#

$σ_{i}^{T + 1} (I) (a) = \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}$

513            self.strategy = {a: r / regret_sum for a, r in regret.items()}

#

එසේනොමැති නම්

515        else:

#

$∣ A (I)∣$

517            count = len(list(a for a in self.regret))

#

$σ_{i}^{T + 1} (I) (a) = \frac{1}{∣ A ( I )∣}$

520            self.strategy = {a: 1 / count for a, r in regret.items()}

#

සාමාන්යඋපාය ලබා ගන්න

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

522    def get_average_strategy(self):

#

$t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$

531        cum_strategy = {a: self.cumulative_strategy.get(a, 0.) for a in self.actions()}

#

$t = 1 \sum T π_{i}^{σ^{t}} (I) = a \in A (I) \sum t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$

535        strategy_sum = sum(cum_strategy.values())

#

නම් $\sum_{t = 1}^{T} π_{i}^{σ^{t}} (I) > 0$ ,

537        if strategy_sum > 0:

#

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

541            return {a: s / strategy_sum for a, s in cum_strategy.items()}

#

එසේනොමැති නම්

543        else:

#

$∣ A (I)∣$

545            count = len(list(a for a in cum_strategy))

#

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{1}{∣ A ( I )∣}$

548            return {a: 1 / count for a, r in cum_strategy.items()}

#

මානවකියවිය හැකි නිරූපණය

550    def __repr__(self):

#

554        raise NotImplementedError()

#

ප්රතිවිරුද්ධකනගාටුව අවම කිරීම (CFR) ඇල්ගොරිතම

අපිඅහම්බෙන් නියැදීම් (සීඑස්) කරන්නෙමු, එහිදී සියලු අවස්ථා සිදුවීම් (නෝඩ්) නියැදි කර ඇති අතර අනෙක් සියලුම සිදුවීම් (නෝඩ්) ගවේෂණය කරනු ලැබේ.

අපිඅහම්බෙන් නියැදීම් සිදු කරන $q (z)$ බැවින් එය සියලු පර්යන්ත ඉතිහාසයන් සඳහා සමාන බැවින් මෙම පදය නොසලකා හැරිය හැකි අතර උපාය ගණනය කිරීමේදී එය අවලංගු වේ (සංඛ්යාංකය සහ නිහාකය තුළ පොදු).

557class CFR:

#

$I$ සියලු තොරතුරු කට්ටල කට්ටලයක්.

570    info_sets: Dict[str, InfoSet]

#

create_new_history නව හිස් ඉතිහාසයක් නිර්මාණය කරයි
epochs මත පුහුණු කිරීමට පුනරාවර්තන සංඛ්යාව $T$
n_players ක්රීඩකයන් සංඛ්යාව

572    def __init__(self, *,
573                 create_new_history: Callable[[], History],
574                 epochs: int,
575                 n_players: int = 2):

#

581        self.n_players = n_players
582        self.epochs = epochs
583        self.create_new_history = create_new_history

#

සියලුතොරතුරු කට්ටල $I$ කට්ටලයක් සඳහා ශබ්ද කෝෂයක්

585        self.info_sets = {}

#

විශ්ලේෂණසඳහා ට්රැකර්

587        self.tracker = InfoSetTracker()

#

දීඇති ඉතිහාසයක් සඳහා වර්තමාන ක්රීඩකයාගේ තොරතුරු කට්ටලය $I$ නැවත ලබා දෙයි $h$

589    def _get_info_set(self, h: History):

#

593        info_set_key = h.info_set_key()
594        if info_set_key not in self.info_sets:
595            self.info_sets[info_set_key] = h.new_info_set()
596        return self.info_sets[info_set_key]

#

රුක්ඇවිදින්න

මෙමකාර්යය ක්රීඩා ගස ඇවිදිනවා.

h වර්තමාන ඉතිහාසය $h$
i අපි පරිගණක කනගාටු වන ක්රීඩකයා $i$ වේ
pi_i වේ $π_{i}^{σ^{t}} (h)$

pi_neg_i වේ

π_{- i}^{σ^{t}} (h)

එයඅපේක්ෂිත උපයෝගීතාව නැවත ලබා දෙයි, ඉතිහාසය සඳහා උපසර්ගය සහිත පර්යන්ත ඉතිහාස සමූහයක් $h$ $z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)$ $Z_{h}$ කොහේද? $h$

ටීඇවිදින අතරතුර එය සම්පූර්ණ කනගාටුව යාවත්කාලීන කරයි $R_{i}^{T} (I, a)$ .

598    def walk_tree(self, h: History, i: Player, pi_i: float, pi_neg_i: float) -> float:

#

එයපර්යන්ත ඉතිහාසයක් නම් පර්යන්ත උපයෝගීතාව $h \in Z$ නැවත ලබා දෙන්න $u_{i} (h)$ .

619        if h.is_terminal():
620            return h.terminal_utility(i)

#

එයඅහම්බෙන් සිදුවීම් $P (h) = c$ නියැදියක් නම් සහ ඊළඟ පියවරට යන්න.

622        elif h.is_chance():
623            a = h.sample_chance()
624            return self.walk_tree(h + a, i, pi_i, pi_neg_i)

#

සඳහාවත්මන් ක්රීඩකයාගේ තොරතුරු ලබා ගන්න $h$

627        I = self._get_info_set(h)

#

ගබඩාකිරීමට $\sum_{z \in Z_{h}} π^{σ} (h, z) u_{i} (z)$

629        v = 0

#

එක්එක් ක්රියාව $z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z)$ සඳහා ගබඩා කිරීම $a \in A (h)$

633        va = {}

#

සියලුක්රියාවන් හරහා නැවත ක්රියා කරන්න

636        for a in I.actions():

#

වත්මන්ක්රීඩකයා නම් $i$ ,

638            if i == h.player():

#

π_{i}^{σ^{t}} (h + a) π_{- i}^{σ^{t}} (h + a) = π_{i}^{σ^{t}} (h) σ^{t}_{i} (I) (a) = π_{- i}^{σ^{t}} (h)

643                va[a] = self.walk_tree(h + a, i, pi_i * I.strategy[a], pi_neg_i)

#

එසේනොමැති නම්

645            else:

#

π_{i}^{σ^{t}} (h + a) π_{- i}^{σ^{t}} (h + a) = π_{i}^{σ^{t}} (h) = π_{- i}^{σ^{t}} (h) * σ^{t}_{i} (I) (a)

650                va[a] = self.walk_tree(h + a, i, pi_i, pi_neg_i * I.strategy[a])

#

$z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z) = a \in A (I) \sum [σ^{t}_{i} (I) (a) z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z)]$

655            v = v + I.strategy[a] * va[a]

#

වර්තමානක්රීඩකයා නම් $i$ , සමුච්චිත උපාය මාර්ග සහ සම්පූර්ණ කනගාටු යාවත්කාලීන කරන්න

659        if h.player() == i:

#

සමුච්චිතඋපාය මාර්ග යාවත්කාලීන කරන්න $t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a) = t = 1 \sum T [h \in I \sum π_{i}^{σ^{t}} (h) σ^{t} (I) (a)]$

664            for a in I.actions():
665                I.cumulative_strategy[a] = I.cumulative_strategy[a] + pi_i * I.strategy[a]

#

\tilde{r}_{i}^{t} (I, a) T R_{i}^{T} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I) = π_{- i}^{σ^{t}} (h) (z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z) - z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)) = t = 1 \sum T \tilde{r}_{i}^{t} (I, a)

678            for a in I.actions():
679                I.regret[a] += pi_neg_i * (va[a] - v)

#

උපායමාර්ගයයාවත්කාලීන කරන්න $σ^{t} (I) (a)$

682            I.calculate_strategy()

#

ක්රීඩකයාසඳහා අපේක්ෂිත උපයෝගීතාව ආපසු ලබා දෙන්න $i$ , $z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)$

686        return v

#

නැවතයාවත්කාලීන කිරීම $σ^{t} (I) (a)$

මෙය $T$ පුනරාවර්තන සඳහා උපාය මාර්ග යාවත්කාලීන කරයි.

688    def iterate(self):

#

epochs වේලාවන් සඳහා ලූප්

696        for t in monit.iterate('Train', self.epochs):

#

ගසඇවිදින්න සහ එක් එක් ක්රීඩකයා සඳහා කනගාටු යාවත්කාලීන කරන්න

698            for i in range(self.n_players):
699                self.walk_tree(self.create_new_history(), cast(Player, i), 1, 1)

#

විශ්ලේෂණසඳහා දත්ත ලුහුබඳින්න

702            tracker.add_global_step()
703            self.tracker(self.info_sets)
704            tracker.save()

#

සෑම $1, 000$ පුනරාවර්තනයක්ම මුරපොලවල් සුරකින්න

707            if (t + 1) % 1_000 == 0:
708                experiment.save_checkpoint()

#

තොරතුරුකට්ටල මුද්රණය කරන්න

711        logger.inspect(self.info_sets)

#

තොරතුරුකට්ටලයක් ට්රැකර්

තොරතුරුකට්ටල වලින් දත්ත සොයා ගැනීම සඳහා මෙය කුඩා උපකාරක පන්තියකි

714class InfoSetTracker:

#

සොයාගැනීෙම් දර්ශක

720    def __init__(self):

#

724        tracker.set_histogram(f'strategy.*')
725        tracker.set_histogram(f'average_strategy.*')
726        tracker.set_histogram(f'regret.*')

#

සියලුමතොරතුරු කට්ටල වලින් දත්ත නිරීක්ෂණය කරන්න

728    def __call__(self, info_sets: Dict[str, InfoSet]):

#

732        for I in info_sets.values():
733            avg_strategy = I.get_average_strategy()
734            for a in I.actions():
735                tracker.add({
736                    f'strategy.{I.key}.{a}': I.strategy[a],
737                    f'average_strategy.{I.key}.{a}': avg_strategy[a],
738                    f'regret.{I.key}.{a}': I.regret[a],
739                })

#

වින්යාසගතකළ හැකි CFR මොඩියුලය

742class CFRConfigs(BaseConfigs):

#

746    create_new_history: Callable[[], History]
747    epochs: int = 1_00_000
748    cfr: CFR = 'simple_cfr'

#

CFR ඇල්ගොරිතම ආරම්භ කරන්න

751@option(CFRConfigs.cfr)
752def simple_cfr(c: CFRConfigs):

#

756    return CFR(create_new_history=c.create_new_history,
757               epochs=c.epochs)

අසම්පූර්ණතොරතුරු සහිත ක්රීඩා වල අවම කිරීම කනගාටු කරන්න (CFR)

හැඳින්වීම

ක්රීඩකයා

ඉතිහාසය

ක්රියාව

තොරතුරු කට්ටලය Ii​

උපායමාර්ගය

ඉතිහාසයේසම්භාවිතාව

උපයෝගීතාව(ගෙවන්න)

නැෂ්සමතුලිතතාවය

අවමකිරීම කනගාටු

ප්රතිවිරුද්ධකනගාටුව

කනගාටුගැලපීම

මොන්ටේකාලෝ CFR (MCCFR)

ඉතිහාසය

තොරතුරුකට්ටලය Ii​

උපායගණනය

සාමාන්යඋපාය ලබා ගන්න

ප්රතිවිරුද්ධකනගාටුව අවම කිරීම (CFR) ඇල්ගොරිතම

රුක්ඇවිදින්න

නැවතයාවත්කාලීන කිරීම σt(I)(a)

තොරතුරුකට්ටලයක් ට්රැකර්

වින්යාසගතකළ හැකි CFR මොඩියුලය

තොරතුරු කට්ටලය $I_{i}$

තොරතුරුකට්ටලය $I_{i}$

නැවතයාවත්කාලීන කිරීම $σ^{t} (I) (a)$