# AI ćwiczenia 3 i 4
## Zad 1
Opisz poniższe algorytmy (możesz użyć nazw, jeżeli znasz):
- **a) local beam search dla k = 1**
*Hill Climbing* bo generujemy wszystkie następniki dla jednego (bo k = 1) wierzchołka i wybieramy jeden najlepszy.
- **b) local beam search z jednym początkowym stanem i bez limitu na liczbę zachowanych stanów po generacji następnika**
*BFS* bo jeden początkowy stan, generujemy wszystkich następników i wszystkich zachowujemy.
- **c) symulowane wyżarzanie z $T=0$ przez cały czas działania algorytmu**
*First Choice Hill Climbing* bo dla $T = 0$ mamy prawdopodobieństwo $e^{\frac{\Delta F} T}$ dąży do $0$ bo $\Delta F < 0$. Czyli praktycznie nie ma możliwości by wykonać gorszy ruch.
- **d) symulowane wyżarzanie z $T = ∞$**
Przez cały czas działania algorytmu *losujemy następny ruch* i go wykonujemy, niezależnie czy jest lepszy, czy gorszy od obecnego stanu.
- **e) algorytm genetyczny z populacją wielkości 1**
Mamy tylko mutacje, brak krzyżowania, więc najprościej to sąsiednie stany, z których wybieramy jeden najlepszy czyli mamy *Hill Climbing*.
## Zad 2
**Przypomnienie algorytmów**

**Taboo search** - dodanie pamięci algorytmowi, zabraniamy ostatnio odwiedzonych stanów (ileś ostatnich)

**Local beam search** - Zamiast pamiętać pojedynczy stan, pamiętamy ich k. Generujemy następnika (kilku następników) dla każdego z k stanów. Na następniki patrzymy globalnie. Z nowych stanów wybieramy k najlepszych stanów (liderów).

**Symulowane wyżarzanie**

Idea:
Losujemy początkowe rozwiązanie, następnie przez kolejne $T$ tur losujemy sąsiada tego rozwiązania z pewnym rozkładem prawdopodobieństwa (hiperparametr). Jeżeli sąsiad ma lepszą wartość funkcji celu, to staje się naszym głównym kandydatem. Jeżeli jest gorszy, to również czasem go dopuszczamy. Jesteśmy skłonni popełniać błędy częściej na początku niż na końcu. Ściśle wyraża się to wzorem:
$$
P(dopuszczenia)=e^{-\alpha \cdot (stare_{cost} - nowe_{cost}) \cdot \frac{t}{T}}
$$
gdzie $\alpha$ jest hiperparametrem określającym jak bardzo jesteśmy skłonni akceptować porażki (nieduża dodatnia liczba z przedziału mniej więcej $(1, 2.5)$), natomiast $t$ jest aktualną turą.


procedure simulated_annealing(T,alpha,radius)
    current_solution = random_solution()
    current_cost = cost_function(current_solution)
    for t=0 to T:
        new_solution = random_neighbour(radius)
        new_solution_cost = cost_function(new_solution_cost)
        if new_solution_cost < current_cost:
            current_cost = new_solution_cost
            current_solution = new_solution
        elif np.random.rand() < np.exp(- alpha * (current_cost - new_solution_cost) * t / T):
            current_cost = new_solution_cost
            current_solution = new_solution


**algorytm genetyczny** - klasa algorytmów ewolucyjnych działająca na przestrzeni poszukiwań $\{0,1\}^n$, niektóre wersje działają na przestrzeni poszukiwań złożonej z permutacji.

Podstawowe pojęcia:
* Przestrzeń poszukiwań - dziedzina, na której określony jest problem np. $R^n$, przestrzeń permutacji, $\{0,1\}^n$, $N^n$ lub pewne obcięcia tych zbiorów
* Populacja - $\mathcal{P}=\{x_1,x_2,...,x_N\}$, zbiór osobników, czyli elementów przestrzeni poszukiwań
* Funkcja celu - funkcja, określająca problem na przestrzeni poszukiwań. W zależności od określenia problemu chcemy znaleźć jej maksimum bądź minimum. Funkcja celu jest określona na całej przestrzeni poszukiwań, w szczególności przypisuje każdemu osobnikowi pewną wartość.

Ogólny schemat algorytmów ewolucyjnych

pocedure evolutionary_algorithm(cost_function,population_size):
    P <- random_population(population_size)
    Population_evaluation(P,cost_function)
    while termiantion_condition(P):
        evolutionary_operator_1(P)
        evolutionary_operator_2(P)
        ...
        evolutionary_operator_K(P)
        Population_evaluation(P,cost_function)

Operatory ewolucyjne można podzielić na cztery główne grupy:
* operatory selekcji rodziców - wybierają najlepsze osobniki z populacji
* operatory krzyżowania - krzyżują ze sobą rodziców, tworząc potomków - osobniki nowej populacji
* operatory mutacji - wprowadzają drobne losowe zaburzenia do potomków, czym przeciwdziałają przedwczesnej zbieżności algorytmu
* repleacement - osobników do nowego pokolenia spośród rodziców i dzieci

**Hill climbing** - Dla stanu znajdujemy wszystkie następniki i wybieramy ten, który ma największą wartość. Powtarzamy aż do momentu, w którym nie możemy nic poprawić.

**Część właściwa**

a) algorytmów ewolucyjnych i hill climbing - Można dodać do zwykłaego algorytmu genetycznego operator zamieniający każdego z osobników na pewne maksimum do którego doprowadzi go hill climbing. Można w ten sposób uniknąć przypadków, że wielu osobników przeszukuje okolice jednego maksimum i skupić się na innych częściach przestrzeni poszukiwań.


b) A* oraz local beam search - Można zrobić przeszukiwanie niczym w A* ale rozważać w każdej pozycji jedynie kilku następników. Dla każdego z następników wybierać k najlepszych i ich dalej rozwijać w podobny sposób. Przyspieszenie, kosztem nieoptymalności rozwiązania.

c) symulowanego wyżarzania i algorytmów ewolucyjnych (inaczej niż w podpunkcie a, z symulowanego
wyżarzania powinniśmy wziąć jedynie ogólną ideę) - zmniejszać prawdopodobieństwo mutacji zgodnie ze wzorem z symulowanego wyrzażania.

d) taboo search z algorytmami ewolucyjnymi - Zapamiętywać, które okolice przestrzeni poszukiwań w jakim stopniu są już zeksplorowane - im bardziej, tym żadziej wybieramy stamtąd osobników. Istotne mogło by się okazać spamiętywanie maksimów w pewnych sektoraach, gdyż nie jest pewne, że algorytm w ostatniej iteracji zwróci coś choćby podobnego do maksimum globalnego.

## Zad 3
Przeczytaj i opowiedz o tym, czym sa algorytmy mrówkowe (ant colony algorithms).
Powiedz, jak zastosowac je do rozwiązania problemu komiwojażera

**problem komiwojażera** - zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie.

**Algorytm mrówkowy** – algorytm zaproponowany przez Marco Dorigo[1], będący probabilistyczną techniką rozwiązywania problemów poprzez szukanie dobrych dróg w grafach. Jest on zainspirowany zachowaniem mrówek szukających pożywienia dla swojej kolonii.

W prawdziwym świecie, mrówki poruszają się w sposób losowy; gdy znajdują pożywienie, wracają do swojej kolonii pozostawiając ślad składający się z feromonów. Gdy inna mrówka natknie się na ten ślad, przestaje poruszać się w sposób losowy i podąża za śladem w kierunku pożywienia.

Jednak po pewnym czasie feromony wyparowują, a więc siła ich działania maleje. Im dłuższa jest trasa od pożywienia do kolonii, tym więcej mają czasu feromony, aby wyparować. Krótsze trasy jednak zapewniają, iż siła działania feromonów będzie większa. Parowanie feromonów jest efektem pozytywnym, bowiem pozwala to na odnajdywanie optymalnej trasy do pożywienia. Gdyby feromony nie wyparowywały, każda kolejna trasa miałaby taką samą siłę jak poprzednia, przez co nie dochodziłoby do odnalezienia optymalnego rozwiązania problemu.

Zatem gdy jedna mrówka odnajdzie dobrą (krótką) drogę, inne mrówki będą podążać tą właśnie drogą, również zostawiając feromony, a więc zwiększając ich natężenie. Ostatecznie wszystkie mrówki będą poruszać się tą samą, najlepszą drogą, a pozostałe drogi zostaną zapomniane (wyparują).

Sam algorytm, który wzoruje się na opisie przyrody zobrazowanym we wstępie, można przedstawić w następujący sposób.

Po pierwsze, optymalizacja następuje w sposób iteracyjny dzięki posiadaniu pewnej grupy „agentów”, którzy są odzwierciedleniem rzeczywistych mrówek. Każdy z agentów rozwiązuje zadanie w sposób unikalny, za pomocą losowych kroków, przy okazji zostawiając po sobie pewnego rodzaju ślad. Rozwiązane zadania są tutaj analogią drogi pomiędzy kolonią a jedzeniem. Następnie rozwiązanie to jest oceniane, a dalej nadawana jest mu waga, która jest odpowiednikiem intensywności zapachu (feromonów). Ocena bazuje na ocenie jakości, którą można przedstawić jako długość drogi — im krótsza droga, tym lepsza jakość rozwiązania zadania.

Warto powiedzieć jeszcze kilka słów na temat agentów. Przyjmuje się, że posiadają oni kilka cech:

* Mają możliwość tworzenia nowych zadań w sposób losowy
* Są prymitywni i indywidualnie zdolni do pojedynczych rzeczy
* Posiadają idealny sposób oceny jakości

Jest to opis ogólny algorytmu, ale pokazuje już pewne zależności. Trzeba mieć na uwadze, że algorytm mrówkowy jest dość młodym algorytmem i są znane jego różne wersje, dodatkowo czasami są one przedstawiane w różnych kombinacjach z innymi algorytmami. Jeżeli ktoś orientuje się w algorytmice, to może skojarzyć losowość algorytmu mrówkowego z tą samą cechą w algorytmie zachłannym.
## Zad 4

Freagmet kodu:

#!/usr/bin/env -S /usr/bin/swipl -O -g main -t halt

:- use_module(library(dcg/basics)).

:- use_module(library(clpfd)).
:- use_module(library(yall)).
:- use_module(library(apply)).

test(T, W) :-
    sum_list(T, SS),
    length(T, N),
    length(W, M),
    NN is M - (SS + N - 1),
    test(T, NN, W).

test([],_, W) :-
    !,
    zeros(W).
test(T, N, [0|W]) :-
    N > 0,
    NN is N - 1,
    test(T, NN, W).
test([A|T], N, W) :-
    test_(A, W, R),
    %NN is N - A,
    test(T, N, R).

test_(0, [], []) :- !.
test_(0, [0|R], R) :- !.
test_(N, [1|T], R) :-
    NN is N - 1,
    test_(NN, T, R).

main(N, M, NA, MA, L) :-
    findall(L, (between(1,N, _), length(L, M)), L),
    % Generowanie
    maplist(ustaw, NA, L, K1, L1),
    transpoze(TL, L),
    maplist(ustaw, MA, TL, K2, L2),
    % Wiązania
    maplist(tuples_in, K1, L1),
    maplist(tuples_in, K2, L2),
    % Bactraking
    maplist(test, NA, L),
    maplist(test, MA, TL).

ustaw(T, L, [L], LL) :-
    findall(L,test(T, L), LL).

Wyniki dla zadania 1 z listy:

Validation result: 12/12 cases pass.

For passing cases total time: 5.444566488265991

Wyniki dla zadanie 2 z listy (z bacgtrakingien):

Validation result: 3/3 cases pass.

For passing cases total time: 109.41725134849548

## Zadanie 5:

Dostajemy listę par nauczyciel i jakiej klasie należy dostarczyć owe zajęcie.

Musimy wybrać terminy dla tych zajęć.

Chcemy aby:

1. nauczyciel nie musiał staosować bilokacji
2. uczniowie nie musieli stosować bilokacji
3. uczniowie nie mieli okienek

1. Aby wyrazić to, że nauczyciel może być na raz w jednym miejscu musimy zmiennym oznaczającym terminy przypisanymi do nauczyciela że mają być wszystkie różne.

Na zapewnienei 2 i 3 możemy zastosować następujący sposob:

Możemy wygenerować $50 * \text{ilość klas}$ zmiennych i każdy z nich oznacza wówczas jakie zajęcie ma klasa w danej godzinie.

Aby powiązać nauczycieli z planem wykorzystujemy [`element/3`](https://www.swi-prolog.org/pldoc/doc_for?object=element/3)

Nauczyciela identyfikujemy z konkretną indywidualną liczbą.
Dwie liczby na raz nie mogą być w jednej komurce co powoduje że uczniowie na raz będą obcować z co najwyżej jednym nauczycielem.

Następnie dołączamy $2*5*\text{ilość klas}$ zmiennych oznaczających konice planu. przed nimi i po nich muszą być zera.

:::info
Alternatywnie zamiast dostawiać nowe zmienne możemy napisać że jeżeli mamy dwa zajęcia w jednym dniu to wszystkie pomiędzy muszą być zajęte.
:::

Na koniec za pomocą [`global_cardinality/2`](https://www.swi-prolog.org/pldoc/doc_for?object=global_cardinality/2) ustawiamy ile tych zajęć powinni mieć uczniowie w tygodniu.

## Zadanie 6:

Zakładamy, że plan jest dopuszczalny, gdy:

- żaden wykładowca nie ma jednocześnie dwóch różnych zajęć
- zajęcia odbywają się zaczynają się po określonej godzinie (np. 8) i kończą do określonej godziny (np. 20)
- w żadnej sali nie ma jednocześnie dwóch zajęć naraz

Chcemy znaleźć dopuszczalny plan, który maksymalizuje funkcję określającą jego jakość.

Funkcja będzie brała pod uwagę takie cechy planu w kolejności od tej z największym priorytetem do najmniejszej:

- przede wszystkim przedmioty obowiązkowe nie powinny kolidować ze sobą ani wykładem ani ćwiczeniami (najważniejsza cecha planu)
- uwzględnianie głosowania: dla każdej pary przedmiotów, takiej, że zagłosowało na oba przedmioty jednocześnie wiele osób, te przedmioty nie powinny ze sobą kolidować
- minimalna liczba okienek dla każdego studenta, uwzględniając przedmioty na które zagłosował
- prowadzący zajęcia nie powinien mieć długich ciągów zajęć bez większych przerw jednego dnia (np. 6 godzin pod rząd)
- jak najmniejsza liczba zajęć w piątek
- minimalna liczba studentów z dużymi blokami zajęć jednego dnia, np. od 10 do 18
- jak najmniej zajęć w nieprzyjemnych godzinach, czyli wcześnie rano i póżno wieczorem

**Głosowanie**
$\mathcal{Z}$ - zbiór zajęć
$c(\cdot,\cdot,\mathcal{P})$ - relacja nachodzenia na siebie zajęć dla ustalonego planu
$\mathcal{S}$ - zbiór studentów
$g(s,z_1)$ - wartość w głosowaniu przydzielona przez studenta $s$ przedmiotowi $z_1$
$$
F(\mathcal{P})=\sum_{\substack{z_1,z_2\in \mathcal{Z},\\\text{t.że }c(z_1,z_2,\mathcal{P})}}\sum_{s\in\mathcal{S}}g(s,z_1)
$$
Powyższą funkcję chcemy minimalizować.

## Zadanie 7:

Gra: Skoczki (https://pl.wikipedia.org/wiki/Skoczki_(gra))

Ocena sytuacji na planszy:
1. odległości naszych pionków od pól docelowych - minimum
(dodatkowo: odległości przeciwnika od pól docelowych - maximum)

Funkcja: suma naszych odległości - szukamy minimum

2. wybór najlepszego ruchu na podstawie jego jakości, czyli np. najdłuższy ruch "do przodu"
(dodatkowo: sprawdzenie, czy dzięki niemu przeciwnik nie wykona równie dobrego ruchu)

Funkcja: różnica pól w pionie - szukamy maksimum

## Zadanie 8:
:::info
gra: Reversi
:::

Reversi (https://pl.wikipedia.org/wiki/Reversi)

Funkcja oceniająca
$$\sum_{i} w_{i}*p_{i}(s)$$

s - stan
w - wagi
p - kryteria oceny

Przykładowe kryteria oceny:
* Balans pionków - różnica w pionkach między graczami,
* Balans możliwych ruchów - balans ruchów naszych i przeciwnika, lepsze są ruchy, które zwiększają naszą pulę ruchów i zmniejszają pulę ruchów oponenta,
* Balans zajętych rogów - pionki zajmujące rogi nie mogą zostać w żaden sposób przejęte. W szczególności linie od nich wychodzące również,
* Balans stabilnosci pionków - w późniejszych etapach gry, powstaja piony których nie da się odwrócić. Możemy wyróżnić 3 rodzaje stabilności: pełna (np. pionki w rogu), pół-pełna (możliwe przechwycenie w dalszej przyszłości), zerowa (przechywcenie możliwe już w następnym ruchu).

:::: spoiler Pomysły na nowe kryteria oceny

::::
## Zadanie 9:

Czemu pierwszy gracz ma duża przewagę?

Jako ze celem kółko i krzyżyk jest ustawienie 3 znaków w jednej kulumnie/wierszu albo na przekątnej, gracz pierwszy rozpoczynając ma tak zwany atak czyli pierwszy ma szansę zdobyć 3 znaku w lini.
Jeśli drugi gracz nie zablokuje nas po 2 ruchu automatycznie przegrywa.

Warto również wziąć pod uwagę fakt, że optymalnym zagraniem zazwyczaj jest przejęcie środka(pierwszy gracz zawsze to może zrobić). Wynika to z tego że środkowa pozycja prowadzi do wygranej w 4 różnych kombinacjach kolumna środkowa,wiersz środkowy, oraz dwie przekątne(Pozycje na krawędziach maja 3 możliwe ustawienia wygranej), a środki rogów tylko 2.

Rozpoczynając jako pierwszy przejmujemy środek zawsze,
następnie wybieramy losowo jedną z krawędzi(maksymalizacja rozwiązań). Jeśli dana krawędz była zajęta posiadamy informację o potencjalnych rozwiązaniach wroga.
W 3 ruchu próbujemy dokończych nasze rozwiązanie, jeśli zostaliśmy zablokowani to wybieramy losowy środek boczny. Jeśli przy próbie zdobyliśmy informację ze przeciwnik posiadał kontrole na jednym ze środków bocznych to zmieniamy taktykę i stawiamy znak na jednym z 2 rogów przy tym środku bocznym.

Jeśli nie przegraliśmy do tego momentu próbujemy skończyć nasze rozwiązanie. Następnie stawiając losowe ruchy.

Agent startujący jako drugi zawsze sprawdza środek(informacja) albo przejmujemy kontrolę nad środkiem.

Jeśli nie zajeliśmy środka to zajmujemy losowy róg, następnie wykonujemy losowe ruchy(jeśli podczas losowego ruchu trafiliśmy na pole wroga) bronimy się przed pozycją pole + środek + finsher.
****
Oczywiście pierwszy gracz ma dużą przewagę (dlaczego?)
- Jeżeli pierwszy gracz położy na środkowe pole, drugi nawet zdobędzie o tym wiedzę, położy swojego pinona w dowolne miejsce, następnie biały znów się ruszy, to czarny ma $1/7$ szans na odgadnięcie posunięcia białego i wpp $1/7$ na nieświadome zablokowanie go. Zatem już w tym momencie biały wygrywa z prawdopodobieństwem $5/7\approx71\%$.

**Agent**
* jeżeli może dołożyć trzeci pionek w lini - dokłada
* jeżeli ma wiedzę o tym, że przeciwnik może dołożyć trzeci pionek w lini - blokuje
* wpp wybiera najlepszy ruch zgodnie z heurystyką

heurystyka oceny planszy:
Dla każdej trójki, która nie zawiera pionków przeciwnika oblicz kwadrat liczby moich pionków. Suma wszystkich kwadratów jest wartością heurystyki. Im większ tym lepsza.

## Zadanie 10:

a)
- Alpha-Beta-Search
- W poprzednim kroku wyliczyliśmy wartość o poziom wyżej niż potrzebujemy w kolejnym (zakładając limit głębokości, nie czasu). Możemy użyć tej wartości do uporządkowaniu wierzchołków w kolejności od najbardziej obiecującego zwiększając szansę na obcięcię podczas analizowania kolejnego piętra.
- MCTS
- Zapamiętujemy wyniki symulowanych gier w każdym węźle, jeżeli przeciwnik wykonał ruch, który zdarzył się w jednej z symulowanych gier już znamy wynik symulacji pewnych naszych odpowiedzi.

W obu przypadkach równolegle wykonujemy obliczenia dla osobnych poddrzew.

## Zadanie 11
a) Co to jest algorytm $max^n$?
b) Czym jest paranoid assumption?
c) Jakie problemy łączą się z tymi dwoma algorytmami?
$max^n$ The result may be that maxn is too optimistic.
Paranoid may outperform maxn due to the larger lookahead (e.g., for Chinese Checkers or Hearts). Because of the unrealistic paranoid assumption, suboptimal play can occur . Furthermore, if an infinite amount of time would be available, the root player might assume that all moves are losing, leading to poor play.
d) Jak działa algorytm Best Reply Search, jakie są jego siły i słabości?

We point out two advantages of BRS over the maxn and paranoid algorithms. (1) More MAX nodes are visited along the search path, leading to more long-term planning. (2) It softens the unrealistic maxn and paranoid assumptions. $Max^n$ assumes that there are no coalitions, while paranoid assums that all opponents form a coalition against the root player. An additional advantage over maxn is that BRS may be able to prune parts of the tree. We point out two drawbacks of BRS as well. (1) Not all players are allowed to make a move, leading to illegal positions. (2) Opponent moves which are beneficial for the root player might not be considered.

e) Czym jest gra Rolit?
f) Przedstaw dokładniej wybrany eksperyment z pracy i opisz jego wyniki.

---

# Sztuczna inteligencja 4
###### tags: `AI`
## Ćwiczenia

---

[TOC]

---

## Rozwiązania

### Zadanie 1: :heavy_check_mark:
In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.

Heurystyka ruchu zerowego opiera się na fakcie, że większość rozsądnych ruchów szachowych poprawia pozycję strony, która je wykonała. Tak więc, jeśli gracz, którego jest kolej na ruch, może utracić prawo do ruchu (lub wykonać ruch zerowy - niedozwolona akcja w szachach) i nadal mieć pozycję wystarczająco silną, aby wygenerować odcięcie, to bieżąca pozycja prawie na pewno przyniosłaby cutoff, jeśli aktualny gracz rzeczywiście się poruszył.

Wykorzystując heurystykę ruchu zerowego, program komputerowy najpierw traci(forfituje) ruch strony, na której ma się poruszać, a następnie przeprowadza wyszukiwanie alfa-beta wynikowej pozycji na płytszą głębokość, niż gdyby przeszukiwałby bieżącą pozycję i nie używał heurystyki ruchu zerowego. Jeśli to płytkie przeszukiwanie daje odcięcie, zakłada się, że przeszukiwanie na pełnej głębokości przy braku utraconej tury również spowodowałoby odcięcie. Ponieważ wyszukiwanie płytkie jest szybsze niż wyszukiwanie głębsze, odcięcie jest znajdowane szybciej, co przyspiesza komputerowy program szachowy. Jeśli płytkie przeszukiwanie nie przyniesie odcięcia, program musi przeprowadzić pełne przeszukiwanie.

Podejście to zakłada dwa założenia.
* Po pierwsze zakłada, że strata straconej tury jest większa niż strata wynikająca z płytszego przeszukiwania. Pod warunkiem, że płytsze poszukiwania nie są zbyt płytsze (w praktycznej realizacji poszukiwania zerowego ruchu są zwykle o 2 lub 3 warstwy płytsze niż pełne poszukiwania), zwykle jest to prawda.
* Po drugie, zakłada się, że wyszukiwanie ruchu zerowego będzie generować odcięcie wystarczająco często, aby uzasadnić czas poświęcony na wyszukiwanie ruchu zerowego zamiast pełnych wyszukiwań. W praktyce jest to również zwykle prawdą.

Problemy :
Istnieje klasa pozycji szachowych, w których zastosowanie heurystyki ruchu zerowego może skutkować poważnymi błędami taktycznymi. W tych pozycjach *zugzwang* (po niemiecku „zmuszony do ruchu”) gracz, którego kolej jest na ruch, ma tylko złe ruchy jako swoje legalne wybory, więc właściwie byłoby lepiej, gdyby pozwolono mu stracić prawo do ruchu. W tych pozycjach heurystyka zerowego ruchu może spowodować odcięcie, w którym pełne wyszukiwanie by go nie znalazło, powodując, że program zakłada, że ​​pozycja jest bardzo dobra dla strony, podczas gdy w rzeczywistości może być dla niej bardzo zła.

Aby uniknąć używania heurystyki ruchu zerowego w pozycjach *zugzwang*, większość programów do gry w szachy, które używają heurystyki ruchu zerowego, nakłada ograniczenia na jej użycie. Takie ograniczenia często obejmują rezygnację z heurystyki ruchu zerowego if

* strona do ruchu jest szachowana
* stronie, która ma się ruszyć, pozostały tylko król i pionki
* strona do przesunięcia ma niewielką liczbę pozostałych elementów
* poprzedni ruch w wyszukiwaniu był również ruchem zerowym.

Inną heurystyką radzenia sobie z problemem zugzwang jest zweryfikowane przycinanie ruchu zerowego przez Omida Davida i Nathana Netanjahu. W zweryfikowanym przycinaniu zerowym ruchem, ilekroć płytkie przeszukiwanie zerowego ruchu wskazuje na wysoki poziom awarii, zamiast odcinania wyszukiwania od bieżącego węzła, wyszukiwanie jest kontynuowane ze zmniejszoną głębokością.
### Zadanie 2:

---
a) bezpiecznemu polu przypisujemy pewną wartość i w funkcji heurystycznej odpowiednio dodajemy lub odejmujemy ją za każde takie pole w posiadanu naszym lub przeciwnika
b) bezpieczne pole to:
- narożnik
- pole, dla którego w każdym z kierunków (pion, poziom, oba skosy) conajmniej jedna strona jest w pełni zajęta przez bezpieczne pola

c) Sprawdzamy czy mamy pole spamiętane jako bezpieczne, jeżeli tak, nie musimy go wyliczać.
W przyciwnym razie patrzymy na sąsiadów parami i sprawdzamy czy dla każdej pary conajmniej jeden z sąsiadów jesy bezpiecznym polem (lub ścianą), jeżeli tak to jest bezpieczy.

Szybko możemy wyznaczać bezpieczne pola wzdł*u*ż ścian od rogów.
http://pressibus.org/ataxx/autre/minimax/node3.html#SECTION00033000000000000000

### Zadanie 3: :heavy_check_mark:
a) Co może oznaczać: losowanie możliwego stanu?
Losujemy możliwą sytuację (czyli karty pozostałych graczy) na podstawie dostępnych kart i zasad gry.
b) W jakich sytuacjach losowanie z poprzedniego punktu chcielibyśmy wykonywać przypisując stanom niejednakowe prawdopodobieństwa? Co można w ten sposób uzyskać i jakie to rodzi problemy?
Na podstawie licytacji możemy szacować, że niektóre rozdania sa bardziej prawdopodobne (lub mniej). Przykład: tysiąc. Grę gracze rozpoczynają liczytacją mówiąc ile punktów uda im się zdobyć. Jednak niektóre wartości nie są możliwe do uzyskania za pomocą samych kart, wymagają dodatkowo punktowanych meldunków (meldunek to król i dama jednego koloru). Jeżeli gracz wylicytuje na początku dużą wartość to możemy przewidywać, że ma jakiś meldunek. Dodatkowo zagrania gracza też mogą nam coś powiedzieć o jego kartach. Przykładowo Makao, jeżeli gracz dobiera zamiast wykładać kartę to możemy podejrzewać, ze nie ma tej figury/koloru. Pozwala nam to lepiej szacować prawdopodobieństwo rozdania, przez co podejmujemy lepsze, trafniejsze decyzje. Problemy : możemy źle zinterpretować co się dzieje w grze.
c) Jaki istotny aspekt gier karcianych jest pomijany w tym podejściu?
Pomijamy całkowicie oszukiwanie (i zachowanie graczy, które może wiele zdradzić), gracze w trakcie licytacji (czy dalej w trakcie gry) nie muszą mówić prawdy. Dodatkowo gracze nie muszą podejmować mądrych, optymalnych decyzji.

### Zadanie 4: :heavy_check_mark:

1. Agent

Sprawdza, czy aktulna zadeklarawana liczba kart przez gracza jest możliwa do zadeklarowania, mając wiedzę o swojej ręce (np. jeśli mamy 3 asy, a ktoś deklaruje, że daje 2, to wtedy wiemy, że kłamie).

2. Agent

Również sprawdza, czy ruch poprzedniego gracza był możliwy oraz przy swoim ruchu zawsze wykłada wszystkie karty, najmniejszego, możliwego typu, jakie ma na ręce.

### Zadanie 5: :heavy_check_mark:

a) - Do okręgu (bo suma kwadratów występuje w równaniu okręgów)
- Do xor (bo podgląd cechy x1x2 tak wygląda)
- Do "Gaussian" bo dzielimy przestrzeń jedna prostą

b) Sieci gwałtownie schodzą do nieoptymalnego wyniku

c) przy klasyfikacji spirali, gdyż wykazuje ona pewną okresowość.

d)
Koło:
XOR:
Linia prosta:

### Zadanie 6: :heavy_check_mark:

Rozważamy sieć neuronową z prostą funkcją schodkową w roli σ (równą 1 dla liczb dodatnich, 0 w przeciwnym przypadku). Wejściem do tej sieci będą zera i jedynki, zatem sieć będzie obliczała jakąś funkcję boolowską.
- a) Podaj sieci neuronowe (złożone z jednego neurona) obliczające: $x ∨ y$, $x ∧ y$, $¬x$.
- $x \lor y$ - $\sigma(1 * x + 1* y + 0)$
- $x \land y$ - $\sigma(1 * x + 1 * y - 1)$
- $\neg x$ - $\sigma(-1 * x + 1)$
- b) Podaj sieć neuronową dla $x \oplus y$
$x \oplus y \equiv (x \lor y) \land \neg (x \land y)$
zatem możemy użyć neuronów z punktu a)
$\sigma(1 * x' + 1 * y' - 1)$
gdzie:
x' = $\sigma(1 * x + 1* y + 0)$
y' = $\sigma(-1 * \sigma(1 * x + 1 * y - 1) + 1)$

- c) Uzasadnij, że nie jest możliwa sieć z punktu b), która ma tylko 1 neuron

Jeden neuron robi regresję logistyczną (więc rysuje kreskę i mówi, że na lewo od kreski jest jedna klasa, a na prawo od kreski ta druga). Nie da się narysować takiej kreski która oddzieli zera od jedynek na wykresie funkcji XOR.
a jak ktoś bardziej lubi formalnie:

Załóżmy że się da. Neuron ma postać:
$\sigma(ax + by + c)$

Zachodzą:

$\sigma(a\cdot0 + b\cdot0 + c) = 0$
$\sigma(a\cdot0 + b\cdot1 + c) = 1$
$\sigma(a\cdot1 + b\cdot0 + c) = 1$
$\sigma(a\cdot1 + b\cdot1 + c) = 0$

Zatem:

$c \leq 0$
$b + c > 0$
$a + c > 0$
$a + b + c \leq 0$

Dodaje stronami drugie i trzecie otrzymuje:

$a + b + 2c > 0$
$0 > a + b + c > -c > 0$, sprzeczność

### Zadanie 7: :heavy_check_mark:

Najpierw odpowiedzmy sobie na pytanie, czy możemy za pomocą sieci z poprzedniego zadania, jesteśmy w stanie wyrazić dowolną funkcję boolowską? Jesteśmy, ponieważ mamy negację, koniunkjcę oraz alternatywę, możemy z nich zbudować np. CNF, a z innych przedmiotów (np. logiki) wiemy, że w CNF możemy wyrazić każdą formułę logiczną.

Teraz zastanówmy się ile warstw potrzebujemy?
Jak dla mnie są to minimalnie dwie, ponieważ najpierw musimy zrobić $\lor$ w każdym składniku CNF, a następnie na wszystkich wykonać $\land$.

W jedynej ukrytej warstwie będziemy wyliczać odpowiednie $\lor$, a w drugiej robimy gigantycznego $\land$.

### Zadanie 8:

a. **~Rolling horizon** - rozwijamy aktualny stan, nie odrzucając poprzednich wyników. To jak przechodzenie w głąb drzewa. Czasem trzeba tylko odwrócić interpretację wyniku w grach z przeciwnikiem -- jak w MinMaxie

b. równolegle można rozwijać kilka rzeczy:

### Zadanie 9: :heavy_check_mark:
**Nadracjonalność** polega na zakładaniu, że przeciwnik przeprowadza identyczne rozumowanie jak my i szukaniu strategii, która daje najlepsze wyniki przy tym założeniu.

Przykład w dylemacie więźnia:
| A\B | Więzień B milczy | Więzień B zeznaje |
|:--------------------- |:------------------------------------ |:------------------------------------ |
| **Więzień A milczy** | Obaj skazani na 6 miesięcy | Więzień B wolny, A skazany na 10 lat |
| **Więzień A zeznaje** | Więzień A wolny, B skazany na 10 lat | Obaj skazani na 5 lat |

Gracz nadracjonalny wybierze milczenie.

Dylemat więźnia – problem w teorii gier. Jest oparty na dwuosobowej grze o niezerowej sumie, w której każdy z graczy może zyskać, zdradzając przeciwnika, ale obaj stracą, jeśli obaj będą zdradzać. Dylemat ten jest więc niekooperacyjną (o częściowym konflikcie) grą o sumie niezerowej, ponieważ strategia konfliktu przeważa nad strategią pokojową: najwięcej można zyskać zdradzając, a najwięcej stracić idąc na współpracę. W odróżnieniu jednak od dylematu kurczaków w tej grze istnieje większe pole do współpracy, które może zaistnieć w strategiach wielokrotnego dylematu więźnia.

Historyjka:

Dwóch podejrzanych zostało zatrzymanych przez policję. Policja, nie mając wystarczających dowodów do postawienia zarzutów, rozdziela więźniów i przedstawia każdemu z nich tę samą ofertę: jeśli będzie zeznawać przeciwko drugiemu, a drugi będzie milczeć, to zeznający wyjdzie na wolność, a milczący dostanie dziesięcioletni wyrok. Jeśli obaj będą milczeć, obaj odsiedzą 6 miesięcy za inne przewinienia. Jeśli obaj będą zeznawać, obaj dostaną pięcioletnie wyroki. Każdy z nich musi podjąć decyzję niezależnie i żaden nie dowie się, czy drugi milczy czy zeznaje, aż do momentu wydania wyroku. Jak powinni postąpić?

Równowaga Nasha – profil strategii teorii gier, w którym strategia każdego z graczy jest optymalna, przyjmując wybór jego oponentów za ustalony. Jeśli każdy z graczy wybrał strategię (plan działania), wybierając ją na podstawie tego, co do tej pory wydarzyło się w grze, a jednocześnie żaden z graczy nie może zwiększyć własnej oczekiwanej wygranej poprzez zmianę swojego planu działania, podczas gdy pozostali gracze pozostają przy swojej, pierwotnie wybranej strategii, wówczas zestaw wybranych przez poszczególnych graczy strategii nazywamy równowagą Nasha.

### Zadanie 10: :heavy_check_mark:

Słownie: żaden z graczy nie może podwyższyć swojej wypłaty przez jednostronną.

Równowagą nasha w tej grze będzie zawsze zdradzenie.

I) Zawsze zdradzać tutaj działa najlepiej, mozemy spytac o ich aktualą karę i cos z tego uzyskac(większa kara, szli wcześniej na sojusz), spodziewana kara czyli opt*nta_parta, zdradzamy

II) Jeśli wiemy jakas strategię przyjał nasz przeciwnik wczesniej za pomocą (identyfikatora) mozemy sie nad nim zemsić albo z nim współpracować, na początku mozemy dać komuś kredyt zaufania a potem pracowac z tą informacją, to samo ze sterowaniem twoma więźniami i iść na sojusz z naszym kolegą

III) Jeśli liczy się sumaryczny wynik wielu rozgrywek to najlepsza strategią jest strategia optymalna wet for wet, albo wet za wet z wybaczaniem jeśli chcemy zaryzykowac wygraną.

Jeśli to jest warunek wspólny trzech punktów to strategia z dawaniem na początku kredytu zaufania, a potem działac z tym informacjami jest najoptymalniejszy (+ mechanizm wybacznia)

https://www.britannica.com/science/game-theory/N-person-games

## Ćwiczenia 5
### Zadanie 1
Algorytm K-średnich(-means) - 1. k initial "means" (in this case k=3) are randomly generated within the data domain (shown in color).
2. k clusters are created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram generated by the means.
3. The centroid of each of the k clusters becomes the new mean.
4. Steps 2 and 3 are repeated until convergence has been reached.

Algorytm K-median(-medians) - It is a variation of k-means clustering where instead of calculating the mean for each cluster to determine its centroid, one instead calculates the median. This has the effect of minimizing error over all clusters with respect to the 1-norm distance metric, as opposed to the squared 2-norm distance metric (which k-means does.)

This relates directly to the k-median problem with respect to the 1-norm, which is the problem of finding k centers such that the clusters formed by them are the most compact. Formally, given a set of data points x, the k centers ci are to be chosen so as to minimize the sum of the distances from each x to the nearest ci.

The criterion function formulated in this way is sometimes a better criterion than that used in the k-means clustering algorithm, in which the sum of the squared distances is used. The sum of distances is widely used in applications such as the facility location problem.

The proposed algorithm uses Lloyd-style iteration which alternates between an expectation (E) and maximization (M) step, making this an expectation–maximization algorithm. In the E step, all objects are assigned to their nearest median. In the M step, the medians are recomputed by using the median in each single dimension.

The median is computed in each single dimension in the Manhattan-distance formulation of the k-medians problem, so the individual attributes will come from the dataset (or be an average of two values from the dataset). This makes the algorithm more reliable for discrete or even binary data sets. In contrast, the use of means or Euclidean-distance medians will not necessarily yield individual attributes from the dataset. Even with the Manhattan-distance formulation, the individual attributes may come from different instances in the dataset; thus, the resulting median may not be a member of the input dataset.

This algorithm is often confused with the k-medoids algorithm. However, a medoid has to be an actual instance from the dataset, while for the multivariate Manhattan-distance median this only holds for single attribute values. The actual median can thus be a combination of multiple instances. For example, given the vectors (0,1), (1,0) and (2,2), the Manhattan-distance median is (1,1), which does not exist in the original data, and thus cannot be a medoid.

Algorytm K-medoids -
### Zadanie 2

### Zadanie 3

### Zadanie 4

### Zadanie 5

### Zadanie 6
Co to jest *zombie filozofów*?
Jaki związek ma to pojęcie ze sztuczną inteligencją?
Jak ma się do tego zagadnienia ChatGPT i pokrewne modele językowe?
Opcjonalnie: co sądzisz na ten temat?