Algorytm alpha-beta

[Piotr]

Witam!

Mam problem z algorytmem alpha-beta
http://pl.wikipedia.org/wiki/Algorytm_alfa-beta. Generalnie to on
działa, zwraca mi wartość alpha (lub beta) odpowiednią dla
najkorzystniejszego liścia.
Zupełnie się gubię gdy chodzi o rekurencję. :(
Nie potrafię zapamiętać adresu tego końcowego liścia.

Czy mógłby mi ktoś pomóc? Męczę się z tym strasznie. :(

Pseudo kod algorytmu alfa-beta
(http://pl.wikipedia.org/wiki/Algorytm_alfa-beta):

funkcja alfabeta(węzeł, głębokość, α, β)
jeżeli węzeł jest końcowy lub głębokość = 0
zwróć wartość heurystyczną węzła
jeżeli przeciwnik ma zagrać w węźle
dla każdego potomka węzła
β := min(β, alfabeta(potomek, głębokość-1, α, β))
jeżeli α≥β
zwróć α
zwróć β
w przeciwnym przypadku {my mamy zagrać w węźle}
dla każdego potomka węzła
α := max(α, alfabeta(potomek, głębokość-1, α, β))
jeżeli α≥β
zwróć β
zwróć α



Moja implementacja w C++:

http://wklej.eu/index.php?id=971666da4f





Prosę o jakąś podpowiedź. Jak zapamiętać adres tego końcowego liścia?
Może być tylko dla gracza. Bo stanąłem w miejscu. ;(


Pozdrawiam serdecznie
Piotr

[(general kenobi)]

Post by Piotr
Witam!
Mam problem z algorytmem alpha-beta
http://pl.wikipedia.org/wiki/Algorytm_alfa-beta. Generalnie to on
działa, zwraca mi wartość alpha (lub beta) odpowiednią dla
najkorzystniejszego liścia.
Zupełnie się gubię gdy chodzi o rekurencję. :(
Nie potrafię zapamiętać adresu tego końcowego liścia.
Czy mógłby mi ktoś pomóc? Męczę się z tym strasznie. :(
Pseudo kod algorytmu alfa-beta
funkcja alfabeta(węzeł, głębokość, α, β)
jeżeli węzeł jest końcowy lub głębokość = 0
zwróć wartość heurystyczną węzła
jeżeli przeciwnik ma zagrać w węźle
dla każdego potomka węzła
β := min(β, alfabeta(potomek, głębokość-1, α, β))
jeżeli α≥β
zwróć α
zwróć β
w przeciwnym przypadku {my mamy zagrać w węźle}
dla każdego potomka węzła
α := max(α, alfabeta(potomek, głębokość-1, α, β))
jeżeli α≥β
zwróć β
zwróć α
http://wklej.eu/index.php?id=971666da4f
Prosę o jakąś podpowiedź. Jak zapamiętać adres tego końcowego liścia?
Może być tylko dla gracza. Bo stanąłem w miejscu. ;(
Pozdrawiam serdecznie
Piotr

niestety nie ma odpowiedzi co by moglo swiadczyc
ze grupy usenetowe padają (sam nie jestem w temacie
tak ze tez nie odpowiem), moze powinienem zwiekszyc
ilosc swoich postow i odpowiedzi na nie wyedy
wygenerowalbym wiekszy ruch? ew mozna sie zwrocic
o dofinansowanie (np na sto tysiecy zlotych) do EU
np w ramach funduszu 'innowacyjna gospodarka?'
(zarty zartami ale usenet to instytucja vel instancja
przece mnie bardzo lubiana i doveniana, i tak
polski chyba trzyma sie lepiej niz np angielskojezyczne
lang.c i inn (nie zagladam tam bo nie mam dobrego
czytnika czy barmki www ale chyba tez nie swieci
populatnoscia, mimo ze tez jest zdaje sie powazane
w oldschoolowym kregu tych co znaja sie na rzeczy :-/)

[Seweryn Habdank-Wojewódzki]

Witam,

Mam problem z algorytmem alpha-betahttp://pl.wikipedia.org/wiki/Algorytm_alfa-beta. Generalnie to on
działa, zwraca mi wartość alpha (lub beta) odpowiednią dla
najkorzystniejszego liścia.

To dobrze.

Zupełnie się gubię gdy chodzi o rekurencję. :(
Nie potrafię zapamiętać adresu tego końcowego liścia.

Nie wiem jaka masz implementacje drzewa wied o adresie nic nie moge
powiedziec.

Jednak to co proponuje to sprobowac najpierw zaimplementowac symulacje
adresowania poprzez nadanie kazdemu wezlowi adresu jako jakiegos
unikalnego numeru. Niech algorytm przebiega przez te numery i zwraca
numer.

Prosę o jakąś podpowiedź. Jak zapamiętać adres tego końcowego liścia?

Jesli chodzi o sama funkje, to zwracalbym pare ::std::pair <
Ptr<Wezel>, int > gdzie Ptr<Wezel> jest adresem liscia, a int jest
wartoscia,
tak jak masz alpha i beta.

Pozdrawiam,

--
|\/\/| Seweryn Habdank-Wojewodzki
\/\/
Professionalism in programming - www.accu.org