Algoritam...

Privet na vsichki...

Interesuvam se ot algoritam (dobar) za igra na tabla (Backgammon). Ima li dostapni sources? Ili pone niakakvo dobro opisanie na strategiata...

Shte se radvam ako niakoi ima informacia po vaprosa (i ia spodeli)... ;-)

Здрасти
Какво разбираш под алгоритъм за табла? Аз в момента пиша табла, но единствения алгоритъм, който може да се приложи са правилата на таблата. Ако искаш да накараш компютъра да играе срещу тебе тогава вече става сложно, там нещата опират до изкуствен интелект, минимакс процедури и т.н.
Иначе сорсове сигурно има, виж на sf.net

Always Outnumbered - Never Outgunned

Estestveno, che iskam kompiutara da igrae sreshtu men. Ti kakva tabla pravish? Ako shte igraiat dvama to tova si e chisto risuvane na kartinki i generirane na sluchaini chisla za zarovete. Tova ne mi e interesno. Interesno e kak kompiutara shte igrae.

Abe cialata ideia e da vidia kak po princip se pravi takova neshto. Iska mi se da se realizirat i drugite dve igri - giulbara i tapa. Ne sam gi vijdal nikade realizirani. Tapite zapadniaci ne znaiat da gi igraiat.

Zasega vsichko tova e samo ideia. Ne sam pravil nikoga podobno neshto i ne sam mnogo naiasno. Iska mi se parvo da poprocheta i da vidia kak horata go praviat...

Ако говорим в общ аспект, алгоритъма ти трябва да се стреми към постигане на печеливша позиция.
Ето и най-грубо казано стъпките за постигането му:
1. Правиш функция която оценява количествено дадена позиция. Тук ще ти е най-интересно, щото ще даваш точки за голи пулове, за капия и прочее.
2. При дадена позиция и зарове извърташ всички възможни позиции и избираш най-добрата.
Дотук компютъра ще е просто лакомия. Когато ти стане безинтересно, ще караш нататък:
1. Ще изчисляваш вероятните позиции според падналите числа на заровете. Например е по-вероятно да се падне 3 и 4, отколкото чифт и т.н.
2. Ще сложиш рекурсивно обхождане на дървото с възможности, като му залагаш различни степени на дълбочина
3. Накрая му слагаш и таймер, за да му ограничиш времето за мислене и една прилична табла е готова
Какво следва ли? Ами ако вече не си сложил правилата за оценка на позиция в файл или база данни е време да го направиш. Просто за да може твоята табла да играе някоя друга игра, която ти си измислиш или видиш - като само добавиш темплейт с првилата й.
Успех!

чети и дишай по-леко

Да се направи ИИ за табла е по-трудно отколкото за шах. Тук имаш 2 вида възли - едните са ходовете, другите са възможните зарове за хвърляне. Последните са двойки (зар, вероятност). През вероятността трябва да прекараш оценката. За всеки възможен ход имаш 21 възможни зара. (Вероятностите са 2/36 и 1/36 за чифтовете. Или за по-просто 2 и 1.) Това страшно бързо разклонява дървото. Явно трябва да се режат клони, но не съм чувал за алгоритми. Иначе очевидно има, щото съм играл табла с комп. и се справяше прилично, до колкото може да прецени един табла-ламер.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Потърси за Jellyfish - игра на табла, като е направена с невронна мрежа - зададени са правилата, пускат се две програми да играят една срещо друга и така се самообучават.

И играе доста добре.

Но сорса едва ли ще го има :)

> Да се направи ИИ за табла е по-трудно отколкото за шах.

Сигурно се шегуваш. Шахът е далеч-далеч по-сложен за алгоритмизиране. Помисли само: всичките ти пулове се движат по едни и същи правила и линейно само в една посока. Това, че някой пул могат да го бият, и да трябва да започва отначало, е незначителна подробност. После, нямаш никаква нужда от изследване в дълбочина на ходовете на противника, понеже така или иначе не знаеш какво ще хвърли (освен ако не "щипеш" зарчетата), но тогава пък съвсем се улесняваш. :) Е, можеш да прогнозираш какво би могъл да хвърли противникът след теб и с каква вероятност ще ти удари някой гол пул, но общо взето стратегията е ясна - капии на подходящите места, минимум голи пулове и бой по голите на врага.

Мислиш ли, че е случайно, дето няма нито един дебют в таблата, наречен на нечие име? Да беше казал, че Го е по-сложен от шаха, да се съглася.

Докато ти четях поста си мислех точно за Го. Правилата са му доста по-прости от на таблата, пък е по-сложен. Изчислително. Иначе понеже (почти) няма алгоритми за него е супер лесно за програмиране. Само дето няма да може да се справи с добър играч.
Таблата също не е кой знае колко трудна като правила, но тези 21 допълнителни възела на всяко ниво дълбочина правят страхотен изчислителен бум. Иначе можеш да направиш нещо което играе ход за ход, но то никога няма да победи добър играч. Въобще игрите базирани на късмет са по-сложни от тези в които всичко е ясно. Навремето си мислех, че тези игри зависят от късмета и затова не ги харесвах. Предпочитах игри които зависят само от ума. Едва в последните години установих колко съм се лъгал. В шаха също има доста късмет и това се дължи на т.нар. в ИИ "проблем на хоризонта" - когато не можеш да стигнеш до листа в разбора и се налага да смяташ по оценка. Може да се окаже, че само малко по-надолу се открива дупка, която не си могъл да видиш заради ограничения ти обзор.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

> Въобще игрите базирани на късмет са по-сложни от тези в които всичко е ясно.

Не съм сигурен, дали е така. Късметът е свързан с точно определени проценти на вероятност, които, след като ги сметнеш, трябва само да ги сравниш, за да избереш по-добрата тактика.

В момента пиша нещо като ИИ за бридж. След като картите вече са раздадени и особено ако пък е приключило и анонсирането, късметът е сведен до нула, понеже приемаш, че противниците ще играят по най-добрия възможен начин. Остава ти да сметнеш всички проценти и да предложиш най-добрия начин за игра.

Ама ти ИИ за разиграването ли пишеш? Тук няма проблем. Ако си мъж напиши ИИ за анонсирането.



System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Някои хора са доста ревниви при отклоняването на топика, та трябва да се внимава.

> Ама ти ИИ за разиграването ли пишеш? Тук няма проблем. Ако си мъж напиши ИИ за анонсирането.

Всъщност след като написах генерирането на ръцете, продължих с анонсирането, понеже първоначално нямах никакви идеи, откъде да подхвана разиграването. Докарал съм го до откриване по SAYC с всички възможни ръце. После следва развитие на анонса без намеси от противника, а след това и с намеси. Принципно всичко е ясно, трябва само време.

Да кажа и нещо, свързано с първоначалната тема. Много се рових по всички възможни линкове за бридж и изкуствен интелект, понеже не ми се откриваше топлата вода. Отначало бях изненадан и разочарован, че няма нищо интересно освен Double Dummy Solvers от сорта на [линк]. Това са перфектно работещи програми за разиграване, които орязват очевидно губещите ходове и по метода на грубата сила намират оптималната игра от останалите възможности. Само че за да могат да работят, трябва да виждат всички ръце, а бриджът не е игра, в която всеки играч разполага с пълната информация, каквито са шахът и таблата. Планът за разиграване се прави в началото на играта, когато имаш твърде оскъдна, а понякога и нулева информация за разпределението на картите в защитниците.

Та сега съм далеч по-доволен, че няма утъпкани пътища, а има неразработена дива местност.

А не може ли да се напише самообучаващ се ИИ. Например като играе срещу себе си по правилата на таблата и гледа кои ходове са печеливши и ги запомня и после играе с тях. Например аз сум правил нещо подобно за морски шах, естествено с тази проста игра този подход работеше, не знам как ще е с таблата.

> А не може ли да се напише самообучаващ се ИИ. Например като играе срещу себе си по правилата на таблата и гледа кои ходове са печеливши и ги запомня и после играе с тях. Например аз сум правил нещо подобно за морски шах, естествено с тази проста игра този подход работеше, не знам как ще е с таблата.

Сигурно може и идеята е доста изкушаваща. Имаш обаче поне два проблема.

1. Не е ясно кой код ще е по-лесен за написване; този за самообучението или този, в който сам вкарваш логиката.

2. Не е ясно колко време ще е необходимо на програмата, за да се самообучи. Това е като да надраскаш една програма за разбиване на пароли, да се изненадаш, че на другата сутрин още е доникъде, да седнеш да сметнеш времето и да се окаже, че ти трябват само още няколко хиляди години.

Дори най-мощните програми за шах ползват библиотеки с дебюти. Иначе за отделен етюд, в който са останали малко фигури, става да го пуснеш да разиграе всички възможности.

[линк]