https://wiki.haskell.org/index.php?title=Principal_variation_search&feed=atom&action=history
Principal variation search - Revision history
2024-03-19T06:24:47Z
Revision history for this page on the wiki
MediaWiki 1.35.5
https://wiki.haskell.org/index.php?title=Principal_variation_search&diff=6744&oldid=prev
DonStewart: category
2006-10-08T03:47:34Z
<p>category</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:47, 8 October 2006</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 147:</td>
<td colspan="2" class="diff-lineno">Line 147:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>--test24 = pvs (-1000) 1000 []</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>--test24 = pvs (-1000) 1000 []</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Code]]</div></td>
</tr>
</table>
DonStewart
https://wiki.haskell.org/index.php?title=Principal_variation_search&diff=5828&oldid=prev
Ashley Y: PrincipalVariationSearch moved to Principal variation search
2006-09-04T21:48:22Z
<p>PrincipalVariationSearch moved to Principal variation search</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:48, 4 September 2006</td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-5827:rev-5828:1.10.0 -->
</table>
Ashley Y
https://wiki.haskell.org/index.php?title=Principal_variation_search&diff=5827&oldid=prev
Rened at 19:08, 4 September 2006
2006-09-04T19:08:21Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 19:08, 4 September 2006</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 2:</td>
<td colspan="2" class="diff-lineno">Line 2:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{-# OPTIONS -fglasgow-exts #-}</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{-# OPTIONS -fglasgow-exts #-}</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>module <del class="diffchange diffchange-inline">Zertz.NegaMax</del> (pvs) where</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>module <ins class="diffchange diffchange-inline">PVS</ins> (pvs) where</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>import Data.Tree</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>import Data.Tree</div></td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-5826:rev-5827:1.10.0 -->
</table>
Rened
https://wiki.haskell.org/index.php?title=Principal_variation_search&diff=5826&oldid=prev
Rened at 19:07, 4 September 2006
2006-09-04T19:07:33Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 19:07, 4 September 2006</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 53:</td>
<td colspan="2" class="diff-lineno">Line 53:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> negaLevel best alpha beta _ = best </div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> negaLevel best alpha beta _ = best </div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> neg (m,v) = (m,-v)</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> neg (m,v) = (m,-v)</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>{--</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>int AlphaBeta (pos, depth, alpha, beta)</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>{</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if (depth == 0) return Evaluate(pos);</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> best = -INFINITY;</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> succ = Successors(pos);</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> while (not Empty(succ) && best < beta)</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> {</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos = RemoveOne(succ);</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if (best > alpha) alpha = best;</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> value = -AlphaBeta(pos, depth-1, -beta, -alpha);</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if (value > best) best = value;</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> }</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> return best;</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>--}</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- Principle variation search</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- Principle variation search</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- the search continues as long as alpha < pvs < beta</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- the search continues as long as alpha < pvs < beta</div></td>
</tr>
</table>
Rened
https://wiki.haskell.org/index.php?title=Principal_variation_search&diff=5825&oldid=prev
Rened at 19:06, 4 September 2006
2006-09-04T19:06:35Z
<p></p>
<p><b>New page</b></p><div><haskell><br />
{-# OPTIONS -fglasgow-exts #-}<br />
<br />
module Zertz.NegaMax (pvs) where<br />
<br />
import Data.Tree<br />
import Debug.Trace<br />
<br />
import Test.QuickCheck<br />
import System.Random<br />
import Control.Monad<br />
<br />
<br />
-- Top node reflects the current position<br />
b x = Node x []<br />
testt = Node ("p1_1",1) <br />
[Node ("p2_2_1",2) <br />
[b $ ("p1_3_1",-7), b $ ("p1_3_2",-2)], <br />
Node ("p2_2_1",3) <br />
[b $ ("p1_3_1",-4), b $ ("p1_3_2",-6)], <br />
Node ("p2_2_2",4) <br />
[b $ ("p1_3_3",-2), b $ ("p1_3_4",-5)] ] <br />
<br />
showTree x = putStr $ drawTree $ fmap show x<br />
<br />
test2 = fmap show testt<br />
test3 = putStr $ drawTree test2<br />
<br />
-- straightforward minimax (not even with alpha beta)<br />
negamax node = case node of<br />
Node (move,v) [] -> ([move],v)<br />
Node (move,_) (n:nn) -> (move:pvm, pvv)<br />
where (pvm, pvv) = negaLevel (neg (negamax n)) nn<br />
where negaLevel prev_best@(_,old_v) (n:nn) <br />
= negaLevel best4 nn<br />
where best4 = case neg $ negamax n of <br />
value@(_,v) | v > old_v -> value<br />
| otherwise -> prev_best<br />
negaLevel best _ = best <br />
neg (m,v) = (m,-v)<br />
<br />
-- Normal alpha beta<br />
alpha_beta alpha beta node = case node of<br />
Node (move,v) [] -> ([move],v)<br />
Node (move,_) nn -> (move:pvm, pvv)<br />
where (pvm, pvv) = negaLevel ([1010101],-1000) alpha beta nn<br />
where negaLevel prev_best@(_,v1) prev_alpha beta (n:nn) | v1 < beta<br />
= negaLevel best4 alpha beta nn<br />
where best4 = case neg $ alpha_beta (-beta) (-alpha) n of <br />
value@(_,v2) | (v2 > v1) -> value<br />
| otherwise -> prev_best<br />
alpha = if v1 > prev_alpha then v1 else prev_alpha<br />
negaLevel best alpha beta _ = best <br />
neg (m,v) = (m,-v)<br />
{--<br />
int AlphaBeta (pos, depth, alpha, beta)<br />
{<br />
if (depth == 0) return Evaluate(pos);<br />
best = -INFINITY;<br />
succ = Successors(pos);<br />
while (not Empty(succ) && best < beta)<br />
{<br />
pos = RemoveOne(succ);<br />
if (best > alpha) alpha = best;<br />
value = -AlphaBeta(pos, depth-1, -beta, -alpha);<br />
if (value > best) best = value;<br />
}<br />
return best;<br />
--}<br />
-- Principle variation search<br />
-- the search continues as long as alpha < pvs < beta<br />
-- as soon pvs hits one these bounds the search stops and returns best<br />
pvs :: (Num a1, Ord a1) => a1 -> a1 -> [Tree (a, a1)] -> ([a], a1)<br />
pvs alpha beta (n:nn) = case negpvs (-beta) (-alpha) n of <br />
best -> negaLevel best alpha beta nn<br />
where negaLevel prev_best@(_,v1) prev_alpha beta (n:nn) | v1 < beta<br />
= negaLevel best4 alpha beta nn<br />
where best4 = case negpvs (-alpha - 1) (-alpha) n of <br />
value@(_,v2) | (alpha < v2) && (v2 < beta) <br />
-> negpvs (-beta) (-v2) n<br />
| (v2 > v1) -> value<br />
| otherwise -> prev_best <br />
alpha = if v1 > prev_alpha then v1 else prev_alpha<br />
negaLevel best alpha beta _ = best <br />
negpvs alpha beta node = case node of<br />
Node (move,v) [] -> ([move], -v)<br />
Node (move,_) nn -> (move:pvm, -pvv)<br />
where (pvm, pvv) = pvs alpha beta nn<br />
pvs _ _ _ = error "PV Search called with empty list"<br />
<br />
pvs_topnode (Node (move,v) []) = ([move],v)<br />
pvs_topnode (Node (move,_) nn) = case pvs (-10000) 10000 nn of <br />
(pvm, pvv) -> (move:pvm, pvv)<br />
<br />
test5 = pvs_topnode testt<br />
test6 = negamax testt<br />
<br />
rtest n = generate 1000 (mkStdGen n) <br />
test7 = rtest 4 $ choose (1, 10)<br />
test8 = rtest 4 $ (vector 5 :: Gen [Int])<br />
-- Twenty numbers from 1 to 10.<br />
test9 = rtest 4 $ sequence [ choose (1,10) | i <- [1..20] ]<br />
<br />
instance (Arbitrary x) => Arbitrary (Tree x) where<br />
arbitrary = sized tree'<br />
where tree' 0 = liftM leaf arbitrary <br />
tree' n | n>0 = <br />
oneof [liftM leaf arbitrary, <br />
liftM2 Node arbitrary leaves]<br />
where subtree = tree' (n `div` 2)<br />
leaves = do n <- choose (1,5)<br />
sequence [ subtree | i <- [1..n] ]<br />
leaf = flip Node []<br />
coarbitrary (Node v nodes) = <br />
variant 0 . coarbitrary v .coarbitrary nodes<br />
<br />
test10 :: Tree (Int, Int)<br />
test10 = rtest 14 $ arbitrary<br />
test11 = showTree test10<br />
test12 = pvs_topnode test10<br />
test13 = negamax test10<br />
<br />
prop_SameResult :: Tree (Int,Int) -> Bool<br />
prop_SameResult node = case pvs' == negamax' of<br />
True -> True<br />
False -> trace (show (pvs', negamax')) False<br />
where pvs' = pvs_topnode node<br />
negamax' = negamax node<br />
<br />
test14 = quickCheck prop_SameResult<br />
test15 = verboseCheck prop_SameResult<br />
test16 = test prop_SameResult<br />
-- beta sets the maximum best score. <br />
-- test17 returns -6 because there is a lower node that returns -6, which is good enough<br />
-- we don't need to search further.<br />
-- i.e. test17 <= beta if there is such a score.<br />
test17 = pvs (-1000) (-6) nodes <br />
where Node _ nodes = testt<br />
-- alpha sets the minimum best score.<br />
-- presumably alpha <= test17 <= beta if there is a valid path for this<br />
test18 = pvs (-1000) 1000 nodes <br />
where Node _ nodes = testt<br />
test19 = pvs (-4) 1000 nodes <br />
where Node _ nodes = testt<br />
test20 = pvs (-100001) (-100000) nodes <br />
where Node _ nodes = testt<br />
test21 = pvs 100000 100001 nodes <br />
where Node _ nodes = testt<br />
testt1 = Node ("p1_1",1) <br />
[Node ("p2_2_1",2) <br />
[b $ ("p1_3_1",-7)], <br />
Node ("p2_2_2",4) <br />
[b $ ("p1_3_3",-2), b $ ("p1_3_4",-5)] ] <br />
test22 = pvs (-1000) 1000 nodes <br />
where Node _ nodes = testt1<br />
testt2 = Node ("p1_1",1) <br />
[Node ("p2_2_2",4) <br />
[b $ ("p1_3_3",-2)] ] <br />
test23 = pvs (-1000) 1000 nodes <br />
where Node _ nodes = testt2<br />
--the only failing test, and it makes sense that this fails.<br />
--test24 = pvs (-1000) 1000 []<br />
</haskell></div>
Rened