Not logged in. · Lost password · Register

tomabrafix
I'm blue da ba dee
Avatar
Member since Oct 2014
126 posts
Subject: More Training Data for Exam Preparation [Alpha-Beta-Pruning]
+4 lu60ruhy, Nash, kissen, LasagneAlForno
Hi,

I am not very creative so I generated some trees to practice alpha beta pruning under time pressure. Maybe someone finds this helpful.

Pruned nodes are red in the solution.

Without solutions: https://www.tomabrafix.de/ki/alphabetapruning-print.pdf
With solutions: https://www.tomabrafix.de/ki/alphabetapruning.pdf

Large random shit: https://www.tomabrafix.de/ki/alphabetapruning_largeset.pdf
(I did not really look at these)

All tree files (dot and pdf): https://www.tomabrafix.de/ki/trees

If you find a bug (attach seed pls) or want other tree structures just answer here.

[Image: https://imgs.xkcd.com/comics/random_number.png]
This post was edited 2 times, last on 2019-02-09, 11:44 by tomabrafix.
kissen (Moderator)
Avatar
Member since Oct 2014
82 posts
I think the solution for 1927540640805326515 (the first tree of random shit) is wrong, the algorithm should prune I, J, L and M, not just L and M. Maybe somewhere you have a "less than" where there should be a "less or equal."
tomabrafix
I'm blue da ba dee
Avatar
Member since Oct 2014
126 posts
Quote by kissen:
I think the solution for 1927540640805326515 (the first tree of random shit) is wrong, the algorithm should prune I, J, L and M, not just L and M. Maybe somewhere you have a "less than" where there should be a "less or equal."

No, I think it is correct. C is the Max player. The Max player tries to maximize alpha and prunes if he finds a value which is greater or equal than beta. So in this tree when alpha-beta-pruning visits C it has alpha=-inf and beta=0. And therefor nodes get only pruned if there is a child which is greater or equal to 0. You can also imagine that if J had a value like +42 it would be inacceptable for the Min player at node A to select C because the Max player then has the opportunity to achieve +42 instead of 0 at B.
kissen (Moderator)
Avatar
Member since Oct 2014
82 posts
Sorry, disregard what I said. I didn't notice the game started with Min.
tomabrafix
I'm blue da ba dee
Avatar
Member since Oct 2014
126 posts
Here is the solution for the same tree with Max player starting: https://www.tomabrafix.de/ki/trees/tree_193654784006006750…

[Image: https://imgs.xkcd.com/comics/labyrinth_puzzle.png]
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen