English
资源说明：Connect4
Proiectarea Algoritmilor Tema 2 – Connect4 Descrierea problemei Ionel și Dorel, doi studenți cu mult timp liber, sunt pasionați de jocurile pe calculator. Atunci când au învățat algoritmul Minimax, s-au gândit că îl pot folosi pentru a implementa un program care să joace singur StarCraft II... După câteva ore de de gândire asiduă în care nu au avut prea multe idei, cei doi decid să înceapă cu ceva mai puțin ambițios, pentru a testa dacă algoritmul într-adevar funcționează și dacă ei pot să îl implementeze corect. Astfel, au decis să scrie un program care să joace Connect4. Competitivi din fire, s-au gândit să provoace toți studenții care studiază Proiectarea Algoritmilor să implementeze ceva similar. Connect4 este un joc cu doi jucători care mută alternativ. Fiecare jucător, atunci când îi vine rândul, adaugă jetonul de culoare proprie la una din coloanele unui grid format din 9 linii și 9 coloane. Jetonul este adăugat de sus și este lăsat să cadă până la prima căsuță neocupată pe acea coloană. Evident, nu se poate adăuga un jeton la o coloană care este plină. Să se implementeze un program care să joace Connect4 cât mai bine. Ionel și Dorel au terminat deja această sarcină, iar programul lor o să joace cu programul fiecărui student în parte, prin intermediul unei platforme de joc ce poate fi descărcată de pe site-ul de curs (detalii în secțiunea următoare). Singura condiție impusă este să se folosească un algoritm de explorare a arborelui de joc, precum Minimax sau variantele sale (Negamax, Alpha-Beta). Evident, pentru ca programul să joace cât mai bine într-un timp cât mai scurt, va fi necesară o abordare de tip Alpha-Beta. Interacțiunea cu platforma de joc Doi jucători vor putea concura prin intermediul unei platforme de joc pe care o puteți găsi în arhiva de pe site-ul de curs (cs.curs.pub.ro), din secțiunea temei 2. De asemenea, în arhivă veți găsi programul care joacă Connect4 scris de Ionel și Dorel. Programul este prezent în două versiuni: opponent4.exe pentru sistemele Windows, și respectiv opponent4 pentru sistemele Linux. Temele vor fi evaluate doar în Linux. Checkerul a fost scris însă cross-platform și veți putea implementa și testa în ce sistem de operare doriți. Vă rugăm însă în mod insistent să vă asigurați că soluția voastră funcționează pe Linux înainte de a o trimite! Platforma de joc permite atât interacțiunea dintre jucători umani, cât și interacțiunea dintre programe. În figura de mai jos aveți un exemplu în care primul jucător este uman, iar cel deal doilea este reprezentat de un program al cărui executabil este situat la calea precizată. Programele care joacă prin intermediul platformei trebuie să respecte un protocol fix, descris în secțiunea următoare. După selectarea jucătorilor trebuie apăsat butonul Start. Interfața grafică rulează pe orice platformă unde aveți instalată o mașină virtuală Java. Recomandăm instalarea unei versiuni recente a mașinii virtuale. Puteți descărca gratuit software Java direct de pe site-ul oficial (http://www.java.com/en/download/index.jsp). În Linux puteți instala pachetul sun-java6 pentru distribuții Ubuntu/Debian, sau un pachet similar pentru alte distribuții. Două programe care concurează prin intermediul platformei. Jucătorul roșu câștigă. Protocolul folosit pentru interacțiunea cu platforma Interacțiunea cu platforma se va realiza prin intermediul intrării și ieșirii standard (stdin, respectiv stdout). Astfel, un program care joacă Connect4 va afișa mutarea pe care dorește să o efectueze la ecran, și va citi mutarea efectuată de oponent de la tastatură. După orice afișare se va tipări și sfârșitul de linie și se va face obligatoriu flush la stream-ul de ieșire. De exemplu, dacă doriți să efectuați o mutare în coloana 4, în C va trebui să folosiți comenzile: printf(“4\n”); fflush(stdout); O mutare validă este specificată printr-un număr între 0 și 8, indicând coloana pe care se adaugă un jeton. Dacă un program afișează un șir care nu reprezintă un număr între 0 și 8, atunci automat va pierde. Programul va pierde și dacă încearcă adăugarea unui jeton la o coloană plină. În plus față de indicii coloanelor, un program poate primi unul din cele 3 coduri speciale, 10, 11 și 12. Semnificația codurilor este următoarea: dacă un program citește de la tastatură numărul 10, a câștigat, dacă citește numărul 11 a pierdut, iar dacă citește 12 jocul s-a terminat remiză. Aceste coduri pot fi doar citite. În cazul în care programul vostru afișează unul din aceste coduri va pierde. Deoarece platforma de joc gestionează interacțiunea dintre programe, puteți considera că mutările pe care le veți citi vor fi întotdeauna valide. Un program care va juca prin intermediul platformei va primi ca argument în linia de comandă unul din șirurile first sau second. Dacă programul primește first, atunci va trebui să efectueze prima mutare, iar în caz contrar va muta al doilea. Inițial, înainte să afișați orice altceva, trebuie să citiți un singur număr, care poate fi ignorat. Acest magic number are o semnificație specială doar pentru Ionel și Dorel. Numărul va fi citit o singură dată (la început), după care programul va trebui să respecte protocolul anterior. Pentru mai multe detalii despre platforma de joc și despre protocolul de comunicare puteți consulta programele orientative din arhiva de pe site-ul de curs sau tutorialele video din ultima secțiune. Reguli de notare 80% din punctajul temei se va acorda pentru rezultatul obținut de programul vostru în urma unui singur joc cu programul lui Ionel și Dorel. Acest program poate fi setat să joace la nivele diferite de dificultate. Puteți obține următoarele punctaje, astfel: 20 de puncte dacă programul vostru învinge adversarul la Level 0; 50 de puncte dacă programul vostru învinge adversarul la Level 1; 80 de puncte dacă programul vostru învinge sau face remiză, la Level 2. Puteți selecta nivelul de dificultate pentru oponent din interfața grafică. Va trebui să precizați în fișierul README împotriva cărei variante doriți să fie testată soluția voastră. La corectare, programul vostru va începe întotdeauna al doilea. Pentru testare pe sistemele proprii, puteți opta ca programul vostru să înceapă și primul. Jucătorul 2 pierde automat deoarece timpul de gândire pentru o mutare depășește 5 secunde Nu veți obține niciun punctaj la această parte în următoarele situații: programul vostru se termină neașteptat (cu eroare); programul vostru încearcă efectuarea unei mutări invalide; timpul de gândire pentru o mutare depășește 5 secunde; programul vostru pierde împotriva variantei specificate în README; nu se specifică nicio astfel de variantă în fișierul README. Cu 10% din punctaj va fi notată claritatea codului, iar restul de 10% se vor acorda pentru comentariile din fișierele sursă și pentru explicațiile din fișierul README. Soluțiile care folosesc algoritmi euristici fără să exploreze parțial arborele de joc nu vor fi luate în considerare și vor obține 0 puncte. Temele copiate se punctează cu -10 puncte (se vor penaliza toți participanții la procesul de fraudare cu minus punctajul maxim pentru temă). Tutoriale video Pentru mai multe detalii, vă recomandăm să urmăriți următoarele tutoriale video: http://www.youtube.com/watch?v=o_pWN9Se470 http://www.youtube.com/watch?v=nkEN1drRG9E
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
