Metody Sztucznej Inteligencji

PROJEKT

Temat: Stworzenie programu potrafiącego samodzielnie rozwiązywać krzyżówki


Data: 14.06.2006
Prowadzący: dr inż. Witold Paluszyński
Autor: Janusz Tymoszuk 128459


Idea

Zgodnie z pierwotnymi założeniami program miał rozwiązywać dowolne krzyżówki na podstawie własnej bazy wiedzy, a następnie, w razie konieczności, szukać odpowiedzi w Internecie.

Problem i próby jego rozwiązania

Niestety, jak się okazało po długich poszukiwaniach, nie znaleziono niekomercyjnej bazy danych w języku polskim, która odpowiadałaby potrzebom programu (definicje haseł). Z kolei, stworzenie od podstaw takiej bazy o sensownym rozmiarze, samo w sobie nadaje się na pracę semestralną (najmniejsze słowniki krzyżówkowe, dostępne w wersjii książkowej, zaczynają się od 15000 haseł). To co jednak udało się znaleźć, to listy słów występujących w języku polskim (od około 6000 do ponad 900000).

W wyniku powstałych ograniczeń zmieniono założenia. Podstawą działania programu miały się stać hasła znalezione w Interecie, a dopiero w razie nie wypełnienia całej krzyżówki, wykorzytywana by była jedna ze znalezionych list słów.

Rozpoczęto kolejne poszukiwania, mające tym razem na celu odnalezienie podobnych w założeniach projektów na sieci i ewntualne wykorzystanie udostępnionych źródeł. Jednak jak się okazało gdy programów, które na podstawie informacji o ilości i rozmiesczeniu znanych liter w słowie jest bardzo wiele, to "prawdziwych" progarmów do rozwiązywania krzyżówek praktycznie nie ma. A te które udało się odnaleźć są najczęsciej komercyjne, lub bardzo słabo opisane (ale z tego co udało sie wywnioskować najczęciej korzystały z własnej, wewnętrznej bazy danych). Jednak mimo tego niepowodzenia udało się natafić na kilka serwisów zajmujących sie tematyką krzyżówek, do których warto jest zajrzeć, jeżeli kogoś interesuje ta tematyka. Jednym z takich miejsc jest, jak się wydaje: www.crosswordtournament.com/links/index.htm.
W wyniku zaistaniałej "suszy" informacyjnej, postanowiono wykonać program od podstaw samodzielnie.

Program

Podstawą działania pierwszej części programu jest komunikacja przez protkół HTTP z dwoma wybranymi serwisami: Słownik Języka Polskiego PWN oraz Wolnodostępny Słownik Synonimów języka polskiego (w przypadku gdy opis hasła jest jednowyrazowy). Przyczyny wyboru tych stron były następujące:

Po wysłaniu wszystkich zapytań i uzyskaniu, bądź nie, satysfakcjonujących odpowiedzi, nastepuje wypełnianie siatki. W przypadku gdy któreś z haseł nie zostanie znalezione, powinno następić wyszukiwanie pasujących słów z wykorzystaniem jednego ze słowników. Niestety tej drugiej częsci nie udało się dokończyć i istnieje ona tylko jako osobny program potrafiący dopasować słowa ze słownika o danych parametrach (długość, występujące litery).

Algorytm wpisywania znalezionych haseł do siatki

Ponieważ, liczba odpowiedzi na jedno zapytanie z wyżej wymienionych stron jest różna (w skrajnych przypadkach od zera do kilkunastu), należało ustalić kryterium kolejności, w jakiej nastąpią próby wpisania kolejnych haseł do siatki.

Po kilkunastu próbach okazało się, że najpewniejszymi wynikami są synonimy, gdyż najcześciej znajdowano jeden, maksymalnie dwa o rządanej długości. Dlatego też wpisywane są one jako pierwsze i tym samym są miejscem krytycznym całego postepowania, gdyż kolejne wpisywane słowa są dopasowywane do tych które zostały zaakceptowane i wpisane wcześniej. A, więc jeżeli pierwszych kilka haseł zostanie źle zidentyfikowanych, kolejne, nawet jeżeli będą właściwe, nie będą wpisane do siatki. Niemniej poczas eksperymentów nie zaobserwowano takiego przypadku.

Kolejnym kryterium jest ilość znalezionych odpowiedzi. Algorytm wpisuje najpierw, te hasła, które mają najmniej znalezionych możliwości (optymalnie jedna), a następnie te z większą ich ilością.

Przy każdym kolejnym wpisie do siatki, badane są ewentualne kolizje. Jeśli wystąpi kolizja, wybierana jest następna pozycja (jeżeli istnieje) z listy znalezionych odpowiedzi na dane pytanie. Jeżeli wszystkie ze znalezionych odpowiedzi powodują kolizje, to nic nie zostaje wpisane do siatki.

Opis implementacji

Program stworzony w ramach tego projektu jest hybrydą, w której wykorzytany jest kod znazleiony na sieci, oraz napisany przeze mnie. I tak:

Opis obsługi programu

Wszystkie operacje są wykonywane w trybie tekstowym. Po uruchomieniu, program wczytuje plik z danymi, następnie dla każdego opisu wysyła zapytanie na stronę Słownika PWN lub Synonimów i wypisuje na ekranie otrzymane odpowiedzi. Cyfra przed każdą odpowiedzią oznacza numer pytania którego się dotyczy (kolejność bezpośrednio z pliku)

Plik krzyżówki

Dane wejściowe do programu są zapisawane w pliku wejściowym o okreslonym formacie:

Przykładowe pliki krzyżówki znajdują sie poniżej, w przykładach sesji.

Przykładowe sesje

Pytania z poniższych plików krzyżówki, pochodzą z dziennika "Metro", z sekcji: "KRZYŻÓWKA z koociakiem"

  1. Krzyżówka z dnia 6. czerwca 2006
  2. Krzyżówka z dnia 13. czerwca 2006
  3. Krzyżówka z dnia 19. czerwca 2006
  4. Przykładowa prosta krzyżówka znaleziona na sieci

Uwagi, wnioski, przemyślenia...

O programie

Ogólnie
Po jedynie kilkunastu testach można dojść do wniosku, że koncepcja programu rozwiązującego krzyżówki wykorzystującego do tego celu, jako bazę wiedzy, Internet jest właściwa. W gruncie rzeczy tylko to medium jest w pewien sposób, "podobne" do umysłu ludzkiego, ze swoją "zdolnością kojarzenia", oraz dynamicznie zwiększającymi się zasobami wiedzy. Dodatkowo dochodzi tutaj kwestia szybkości wyszukiwania i gromadzenia danych. Aby stworzyć od podstaw samą bazę danych, a następnie algorytmy ją przeszukujące na poziomie pozwalającym rozwiązywać rzeczywiste krzyżówki w skończonym czasie można spędzić całe lata i to bez gwarancji sukcesu. A tymczasem, ta część jest już niejako zrobiona i udostępniona, trzeba ją tylko właściwie wykorzytać.