# Sztuczna inteligencja (c3, grupa PON) ## Ćwiczenia Czwartek 18-20 --- ```python= # python, formatowanie: for i in range(10): print (22) ``` Wzory : $f(N) = \sum_1^N \frac{1}{n^2+1} + \min(a_1, \dots, a_N)$ --- ## Deklaracje * Marcin Dąbrowski SUMA:6 ZADANIA: 1,2,3,7,8,9 * Maciej Dudek SUMA: ZADANIA: * Jakub Froń SUMA: 9 ZADANIA: 1,2,3,4,5,6,7,8,9 * Krzysztof Grynkiewicz SUMA:2 ZADANIA:1,3 * Hubert Jabłoński SUMA: 5 ZADANIA: 1, 3, 7, 8, 9 * Mateusz Leonowicz SUMA: 9 ZADANIA: 1,2,3,4,5,7,8,9,10 * Anna Pacanowska SUMA: 7 ZADANIA: 1,2,3,4,5,7,9 * Maksymilian Perduta SUMA: ZADANIA: * Łukasz Pluta SUMA:8 ZADANIA:1,4,5,6,7,8,9,10 * Paweł Smolak SUMA: ZADANIA: * Adam Turowski SUMA: 6 ZADANIA: 1, 2, 3, 7, 8, 9 * Jan Wańkowicz SUMA: 8 ZADANIA:1,2,3,4,5,7,8,9 * Adrianna Wilińska SUMA: 10 ZADANIA: 1,2,3,4,5,6,7,8,9,10 ## Rozwiązania ### Zadanie 1: **Opisz poniższe algorytmy:** #### a) local beam search dla k = 1 Generujemy następniki (k=1) jednego stanu i pozostawiamy (k=1) jednego lidera, czyli ten który ma największą wartość. Widzimy, że jest to opis Hill Climbing. #### b) local beam search z jednym początkowym stanem i bez limitu na liczbę zachowanych stanów po generacji następnika Zaczynamy od ustalonego stanu, generujemy wszystkie jego następniki, później wszystkie następniki jego następników - BFS. #### c) symulowane wyżarzanie z T = 0 przez cały czas działania algorytmu Nie wykonujemy ruchów losowych, a jedynie te które polepszają stan, zatem to po prostu First Choice Hill Climbing. #### d) symulowane wyżarzanie z T = ∞ przez cały czas działania algorytmu Nasz algorytm to losowe przechodzenie po stanach, bo zawsze wybieramy wylosowany następnik #### e) algorytm genetyczny z populacją wielkości 1 Nie jest możliwe krzyżowanie, wykonujemy jedynie mutację. Ten algorytm to Local Beam Search, gdzie następnik powstaje przez mutację stanu. --- ### Zadanie 2: Jan Wańkowicz #### a) algorytmy ewolucyjne i hill climbing: Zamiast stosować mutacje, możemy wykonywać kilka iteracji hill climbingu. #### b) A∗ oraz local beam search: Na samym początku wykonujemy kilka iteracji local beam searcha, a następnie kończym algorytmem A*. #### c) symulowane wyżarzanie i algorytmy ewolucyjne: Na końcu działania danej iteracji algorytmów ewolucyjnych nie bierzemy k najlepszych osobników, tylko z pewnym prawdopodobieństwem kilka z nich jest gorszych. #### d) taboo search z algorytmami ewolucyjnymi: Zapamiętujemy osobniki z kilku wcześniejszych populacji, aby w następnych uniknąć już używania ich. --- ### Zadanie 3: Adam Turowski ![](https://i.imgur.com/UuMELWA.png) https://www.youtube.com/watch?v=X-iSQQgOd1A Działanie algorytmów mrówkowych jest inspirowane rzeczywistym zachowaniem kolonii mrówek. Mrówki w poszukiwaniu pożywienia zostawiają za sobą feromony, które po pewnym czasie wyparowują. Mrówki poruszają się za śladem tych feromonów, bądź z pewnym prawdopodobieństwem, losowo. Gdy mrówki znajdą jakieś bogate źródło pożywienia, to więcej mrówek zacznie do niego docierać, w efekcie cały czas zwiększając natężenie feromonów na ścieżce prowadzącej do niego. Stosując algorytm mrówkowy można znaleźć optymalne, bądź bliskie optymalnemu, rozwiązanie problemu komiwojażera. Można stworzyć populację mrówek, które będą poruszały się zgodnie z następującymi zasadami: * każde miasto odwiedzone jest tylko raz * miasto bliższe jest atrakcyjniejsze niż dalsze * prawdopodobieństwo wybrania ścieżki rośnie wraz z natężeniem feromonów Wypuszczamy kolejno kilka kolonii mrówek. Wybór kolejnego miasta każda z mrówek uzależnia od dwóch czynników - odległości oraz natężenia feromonów pozostawionych przez poprzednie kolonie oraz z pewnym prawdopodobieństwem nie wybiera optymalnego miasta. Natężenie feromonów pomiędzy miastami określamy na podstawie optymalności ścieżki, do której takie połączenie należy. --- ### Zadanie 4: Adrianna Wilińska ![](https://i.imgur.com/QhHwzCf.png) Tworzymy zmienne odpowiadające komórkom w obrazku będzie ich odpowiednio $n \times m$ | $B_{1,1}$ | $B_{1,2}$ | $B_{1,3}$ | | --------- | --------- | --------- | | $B_{2,1}$ | $B_{2,2}$ | $B_{2,3}$ | | $B_{3,1}$ | $B_{3,2}$ | $B_{3,3}$ | $B_{i,j}\in\{0,1\}$ Teraz dla każdego wiersza i kolumny generujemy węzeł spełniony, gdy układ komórek odpowiada którejś z permutacji zadanego układu klocków. --- Rozwiązanie trudniejsze ale oszczedniejsze Pozostajemy przy zmiennych $B_{i,j}$. Ustanawiamy pomocnicze zmienne będące pozycjami bloczków w wierszach i kolumnach. Przykładowo dla szerokości obrazka 7 i układu bloczków w wierszu $\{2,3\}$ mamy zmienne o dziedzinach: $R_{IdWiersza,2,IdKlocka} \in \{1,2,3,4,5,6\}$ nie przejmujemy się tym, ze później się nie zmieści kolejny klocek. $R_{IdWiersza,3,IdKlocka} \in \{1,2,3,4,5\}$ a tu nie przejmujemy się tym, ze nie zmieści się klocek przed. Teraz musimy ustanowić więzy, które zapewnią, że bloczki nie będa na siebie nachodzić: Czyli dla każdej pary więzów w wierszu mamy: pomińmy id wiersza i klocka $R_{waga} + 1 + waga \quad\#<= \quad R_{nastepny}$ Dla każdej pary zmiennych w wierszu dajemy warunek, ze klocki nie będa na siebie nachodzić. Np dla zmiennej Teraz dla $B_{1,3} = 1 \quad \# <=>$ któryś z klocków nachodzi na to pole czyli $(R_1 \quad \#= 3 \quad \lor\quad (2\quad\#<= \,R_2 \,\#<3)$ --- ### Zadanie 5: Anna Pacanowska ![](https://i.imgur.com/vVzefHt.png) Mamy zmienne $Z_i$ oznaczające kolejne zajęcia. Każda z tych zmiennych ma dziedzinę: `Z_i in 1..50` `Z_i #\= Z_j` dla każdej pary zajęć $Z_i, Z_j$ mających tą samą klasę lub nauczyciela Wprowadzamy nowe zmienne $T_{c,d,h}$ oznaczające to, czy zajęcia z klasą $c$ odbywają się dnia $d$ o godzinie $h$. `T_cdh #= 1 #<==> Z_i #= d*10+h #\/ Z_j #= d*10+h ...` (dla zajęć z klasą $c$) Aby uniknąć okienek zapewniamy ``` tuples_in([[T_cd1, T_cd2, ..., T_cd10], ...(dla każdej klasy i dnia)], [wszystkie możliwe układy dnia bez okienek]) ``` --- ### Zadanie 6: Jakub Froń #### Twarde wymagania-więzy: * Żaden prowadzący nie może mieć dwóch zajęć w tej samej godzinie * Zajęcia obowiązkowe danego rocznika nie mogą kolidować * Zajęcia odbywają się w godzinach 10-20 #### Miękkię więzy i ich wartości * Najpopularniejsze przedmioty (z największą ilością głosó) nie powinny ze sobą kolidować: 10 punktów * Najpopularniejsze przedmioty nie powinny mieć między sobą okienek: 8 punktów * Prowadzący nie powinni mieć zbyt dużo zajęć jednego dnia (od 2 do 4): 3 punkty * Minimalizacja trudnych przedmiotów jednego dnia (powyżej 5 ects): 2 punkty * Mniej zajęć rano i po 16: 1 punkt --- ### Zadanie 7: Mateusz Leonowicz ### Zasady gry ![](https://i.imgur.com/Wy2Hy6Z.png) Celem gry jest ułożenie pięciu kulek w rzędzie. Ruchem kazdego gracza jest położenie kulki w swoim kolorze na pustym miejscu i obrócenie jednej z częci planszy o 90 stopni. ### Rozwiązanie Heurystyka dla żadego gracza jest taka sama. Jej składową jest dążenie do własnego zwycięsktwa oraz utrudnianie tego samego drugiemu graczowi - stąd heurystyka wynosi: liczba własnych obiecujacych linii - liczba lini drugiego gracza w taki sam sposób. Będziemy dążyli do zmaksymalizowania jej wartości: Jako ruch rozpatrujemy kulkę+obrót W ten sposób uzyskujemy następujący przelicznik * jeżeli ruch doprowadza nas do zwycięstwa to heurystyka jest równa $+\infty$ * jeżeli nie to stosujemy następujący przelicznik dla lini. Liczymy tylko takie linie, które składają się z conajmniej 2 kulek: * Jeżeli linia jest dostępna bez obrotu to jej mnożnik to 16. * Jeżeli linia jest dostępna po jednym obrocie mnożnik to 8. * Jeżeli po 2 mnożnik to 4. * I dalej analogicznie - musimy mieć jakiś limit, powiedzmy, ze to będa 4 obroty z wartością 1. * Potrzeba też zważyć linie - musi nam się bardziej opłacać zbudować więcej lini długości 2/3 niż ślepo budować pojedynczą linie długości 4 * Pojedyncze linie mają wagę odpowiadającą ich długości. * podwójny zestaw to przemnożenie długości przez 3 * potrójny przez 4 * i tak odpowiednio o jeden więcej niż jest zestawów. (?) Oczywiście są to przykładowe wartości. Przydałoby się je wyewaluować za pomocą na przykład mcst. Albo Uwaga: moze się okazać, że mozna dodatkowo ważyć położenie lini - na przykłąd pierwszej kulki. Przykłądowo - ułożenie na skraju jest mniej warte niż ułożenie bardziej w centrum. --- ### Zadanie 8: Hubert Jabłoński Gra: Wilk i Owce Zasady gry: ![](https://i.imgur.com/Tz7AOE4.png) 4 owce i 1 wilk Wygrywają Owce jeśli wilk nie ma możliwych ruchów Wygrywa Wilk jeśli dojdzie do końca planszy Owce mogą poruszać się tylko po przekątnych do przodu Wilk porusza się po przekątnych o jeden Heurystyka: 1) 8 - (odległość wilka od końca planszy) 2) S = średnia ykrekowa współrzędna owiec abs(S - y1) + abs(S - y2) + abs(S - y3) + abs(S - y4) --- ### Zadanie 9: Marcin Dąbrowski ## Zadanie 9 ![](https://i.imgur.com/bisTKOS.png) ### Gracz pierwszy 1. Wybieramy środek, ponieważ otwiera najwięcej gróźb wygranej (w poziomie, pionie i po dwóch przekątnych) 2. Grozimy wygraną w poziomie lub pionie, co gwarantuje nam przynajmniej remis. Nie grozimy po przekątnej, ponieważ wtedy może nastąpić sytuacja, w której w następnym ruchu mamy 50% szans na przegraną, 50% na przynajmniej remis (z dużą szansą na wygraną) - jedyna sytuacja, w której drugi gracz może grozić wygraną. 3. Próbujemy zrealizować groźbę wygranej, jeśli pole jest zablokowane, to blokujemy rząd, w którym chcieliśmy dostawić krzyżyk (jednocześnie grożąc wygraną dzięki pierwszemu ruchowi). 4. W każdym kolejnym ruchu próbujemy zrealizować groźbę wygranej, jeśli ona zablokowana, to blokujemy potencjalną wygraną przeciwnika (jeśli taka istnieje) i grozimy wygraną. ### Gracz drugi 1. Próbujemy wybrać środek, ponieważ jeśli udałoby się go zająć, to w następnym ruchu przeciwnik może zagrozić wygraną tylko na dwa sposoby. Jeśli się nie uda, to zajmujemy losowo wybrany róg, ponieważ pozwala on wykluczyć 3 potencjalne sposoby wygranej przez gracza pierwszego. 2. Mamy dwa warianty - przeciwnik grozi po przekątnej lub w pionie/poziomie. W pierwszym wariancie, jeśli wybierzemy bok, to przegramy, a jeśli znów wybierzemy róg i z prawd. 50% zablokujemy jego groźbę, mamy 50% szans na wygraną w następnym ruchu (bo przeciwnik nie wie czy grozimy w pionie czy w poziomie). W drugim wariancie, jeśli wybierzemy róg, to przegramy, a jeśli wybierzemy bok, to z prawd. 50% się obronimy. 3. Znów mamy dwa warianty - broniąc się ustawiliśmy groźbę wygranej lub nie. W pierwszym wariancie, to przeciwnik musi zacząć odpierać nasze groźby, więc możemy próbować je realizować, co przy dobrej obronie przeciwnika daje nam informacje o wszystkich jego ruchach, więc na pewno nie przegramy. W drugim wariancie przeciwnik ma dwa sposoby ustawienia groźby, więc znów bronimy jedną z nich i z prawd. 50% przegrywamy. --- ### Zadanie 10: Łukasz Pluta ![](https://i.imgur.com/ZiCjfV2.png) ![](https://i.imgur.com/I45owE5.png) a) W obu przypadkach algorytm buduje drzewo możliwości, które idzie kilka poziomów wgłąb. Jeśli po ruchu naszym i przeciwnika wejdziemy do poddrzewa, które już wczesniej zaczelismy przeliczac to nie musimy tego robic ponownie, jesli wczesniej zapamietamy wyniki obliczen tam wykonanych. Na przykład mozemy zapamietywac wyniki dla najbardziej obiecujacych poddrzew. b)Równoległe przetwarzanie kodu umożliwia liczenie wariantów w wielu poddrzewach naraz, co w oczywisty sposób przyspiesza obliczenia, dzięki czemu możemy lepiej oceniać faktyczny stan gry.