Wieże Hanoi to dla większości ludzi na świecie prosta, drewniana zabawka dla dzieci. Natomiast dla studentów informatyki to nie raz jedno z najgorszych wspomnień z pierwszych lat studiów i nauki programowania. Jak to możliwe? Co jest w nich takiego strasznego? Przekonajmy się na własną rękę.

Poprzednio w serii algorytmika gier pochyliłem się nad grą w sapera, gdzie przeanalizowaliśmy, jak generuje się planszę oraz prowadzi rozgrywkę. Teraz spróbujmy przenieść na komputer jedną z najpopularniejszych gier rozgrywanych na kartce — kółko i krzyżyk. Jednak tym razem nie skupimy się na zaprogramowaniu całej rozgrywki, a tylko na jednej rzeczy: sztucznej inteligencji komputerowego gracza.

Gdy we wczesnych latach podstawówki uczyliśmy się dzielenia (szczególnie „pod kreską”), w pewnym momencie dowiadywaliśmy się, że nie da się liczb idealnie podzielić. Czasami zostaje reszta. W końcu gdy dzielimy 6 na 4, to w szóstce zmieścimy tylko jedną czwórkę, ale to nie oznacza, że 6 dzielone przez 4 to po prostu 1. Mamy jeszcze 2 reszty, ewentualnie co dokładniejsi podaliby wynik 1,5. Jak się okazuje, obliczenie reszty z dzielenia, mimo że wydaje się czymś prostym i oczywistym... no cóż, zawsze coś musi się komplikować. Dlatego też przeanalizujmy tę operację: rozłóżmy ją na czynniki pierwsze i zobaczmy, co może tutaj pójść inaczej, i dlaczego, mimo różnych wyników, wciąż wszystko jest poprawnie.