Seminarium Badawcze - Sztuczna Inteligencja w Grach

Termin: poniedziałek 16:00-17:30, sala 3230.
Lista referatów
Linki i materiały
Propozycje referatów

Tematyka:

  • gry : dwu- , jedno- i wielo-osobowe,
  • algorytmy i idee stosowane w komputerowych graczach,
  • techniki zarówno niezależne od dziedziny jak i specyficzne dla wybranych gier,
  • zastosowanie algorytmów sztucznej inteligencji w grach.

    • Cele:

  • uruchomienie projektów badawczych w wybranych tematach,
  • prezentacja wybranych osiągnieć w tej dziedzinie,
  • wzajemna wymiana informacjami i zainteresowaniami związanymi z tą tematyką.

    • Lista referatów

    21.11.2005 Jakub Pawlewicz

    Praktyczne odmiany Proof-Number-Search.

    PN-Search należy do grupy algorytmów best-first, przeszukujących bardzo wąskie i głębokie drzewa gry. Szuka ona kombinacji wygrywających i jest bardzo użyteczna w grach kombinacyjnych. Zwłaszcza znajduje bardzo dobre zastosowanie w grach z nagłą śmiercią.

    Na seminarium przypomnę na czym polega PN-Search. Zamierzam jednak skupić się na praktycznych odmianach, takich jak PN*, PDS, DF-PN i innych.

    14.11.2005 Arek Paterek

    Szachy - wybór parametrów funkcji oceniającej przy użyciu uczenia maszynowego

    Na seminarium opowiem o dwóch technikach uczenia z nadzorem, których użyłem do ustalenia wag funkcji oceniającej mojego programu szachowego Gosu. Pierwsza metoda jest typu "value adaptation" - próbuje tak wybrać wagi funkcji oceniającej, aby, dla pozycji ze zbioru treningowego, jak najlepiej przybliżała wyniki rozgrywek, z których pochodzą te pozycje. Druga metoda jest typu "move adaptation" - próbuje znaleźć takie wagi, żeby program jak najczęściej proponował ruchy zagrane w pozycjach ze zbioru treningowego.
    Obie metody wykorzystują odmianę regresji logistycznej, używaną w komputerowych sieciach neuronowych do ustalania wag pojedynczego neuronu.

    Program Gosu wygrał w tym roku IV Mistrzostwa Polski Programów Szachowych.

    7.11.2005 Jakub Żytka

    Brydż – techniki stosowane w grach z niepełną informacją

    Treścią wystąpienia będą techniki stosowane w grach z niepełną informacją, na przykładzie brydża. Bardziej szczegółowo opowiem o sprowadzaniu rozgrywki pojedynczego rozdania do wariantu gry z pełną informacją i zastosowaniu metody monte carlo, jak też problemów z tym związanych. W miarę możliwości czasowych poruszone zostaną także kwestie licytacji i obrony, zwłaszcza w kontekście problemów, z którymi komputery, póki co, radzą sobie słabo.

    24.10.2005 Jakub Pawlewicz

    Gra Hex – techniki użyte w najlepszych programach grających

    Przedstawiony zostanie szereg technik, które doprowadziły do bardzo silnych programów grających. Między innymi zostanie przedstawiony algorytm znajdowania wirtualnych połączeń oraz funkcja oceniająca zbudowana z wykorzystaniem analogii do układów elektrycznych.

    17.10.2005 Łukasz Lew

    Podejście Monte Carlo w zastosowaniu do gry Go

    Linki i materiały

    Hex

    Hex Theory - strona Kevina O'Gormana. Są na niej najaktualniesze materiały. Są tam też scany z różnych książek i żeby niektóre z nich sobie ściągnąć trzeba poprosić Kevina o hasło.

    playhex - grupa dyskusyjna założona przez Kevina.

    ICGA - strona ICGA o Hexie.

    Six - aktualnie najlepszy program napisany przez Gábora Melisa.

    Brydż

    2005 World Computer-Bridge Championship - oficjalna strona mistrzostw świata programów brydżowych, które odbyły się w dniach 25-30 paździenika 2005.

    Bibliografia

    [1] Blair, Mutchler, Lent "Perfect Recall and Pruning in Games with Imperfect Information" (1996)

    [2] Smith, Nau "Strategic Planning for Imperfect-Information Games" (1993)

    [3] Smith, Nau, Throop "Success in Spades: Using AI Planning Techniques to Win the World Championship of Computer Bridge" (1998)

    [4] Chang "Building a Fast Double-Dummy Bridge Solver" (1996)

    [5] Frank, Basin, Bundy "An Adaptation of Proof-Planning to Declarer Play in Bridge" (1992)

    [6] Frank "Search and Planning under Incomplete Information A Study using Bridge Card Play" (1996)

    [7] Frank, Basin, Matsubara "Finding Optimal Strategies for Imperfect Information Games" (1998)

    [8] Frank, Basin "Optimal Play against Best Defence: Complexity and Heuristics" (1998)

    [9] Frank, Basin "A Theoretical and Empirical Investigation of Search in Imperfect Information Games" (1999)

    [10] Frank, Basin, Bundy "Combining Knowledge and Search to Solve Single-suit Bridge" (2000)

    [11] Frank, Basin, Bundy "Solving Single-suit Bridge Play: Winning and Knowing Why" (2000)

    [12] Ginsberg "Partition Search" (1996) - szybki algorytm rozwiązywania drzewa gry

    [13] Ginsberg "GIB: Steps Toward an Expert-Level Bridge-Playing Program" (1999)

    [14] Ginsberg "GIB: Imperfect Information in a Computationally Challenging Game" (2001) - duża część referatu

    [15] Schaeffer "The Games Computers (and People) Play" (2000) - nie tylko o Brydżu

    [16] Smith, Nau, Throop "A Planning Approach To Declarer Play In Contract Bridge" (1996)

    [17] Smith, Nau, Throop "Total-Order Multi-Agent Task-Network Planning for Contract Bridge" (1996)

    [18] Smith, Nau, Throop "Computer Bridge: A Big Win for AI Planning" (1998)

    [19] Chang "Toward the Automation of the Card-Playing Component of Bridge"

    [20] Jamroga "A Linguistic Approach to Games with Communication" (2000) - polski rodzynek dotyczący licytacji

    Propozycje referatów

    Combinatorial Game Theory

    Bibliografia

    [1] Berlekamp, Conway, Guy "Winning Ways" - dostępne w bibliotece na Hożej 69

    [2] Conway "On Numbers and Games" - dostępne w bibliotece MIM

    [3] Cazenave "Comparative evaluation of strategies based on the values of direct threats"

    [4] Berlekamp "The Economist's View of Combinatorial Games"

    [5] West "Championship-Level Play of Domineering"

    [6] Guy "Unsolved Problems in Combinatorial Games"

    [7] Ferguson "Game Theory Text"

    Solving Awari

    Bibliografia

    [1] Romein, Bal "Solving the Game of Awari using Parallel Retrograde Analysis"

    [2] Romein, Bal "Awari is solved - Notes"

    Poker

    Bibliografia

    [1] http://www.cs.ualberta.ca/~darse/Papers/IJCAI03-ov.html

    [2] "Approximating Game-Theoretic Optimal Strategies for Full-scale Poker"

    [3] "The Challenge of Poker"

    [4] Inne z The University of Alberta GAMES Group

    Papier, nożyczki, kamień (RoShamBo)

    The Second International RoShamBo Programming Competition

    Zwycięzca pierwszego turnieju: Iocaine Powder