Een PC oneinding lang tetris laten spelen?

[QuestGamer]

Modjes: ik weet niet of dit in dit topic thuis hoort hoor, verplaats anders maar ?

Ik was op een dromerige vrijdagmiddag eens begonnen met het namaken van Tetris. Dit ging prima (Turbo Pascal 7 gebruikt). Maar toen dacht ik: laat ik eens proberen een bot/PC te maken die tetris speelt

Maar wat ik me nu dus afvraag: is het mogelijk om een bot te programmeren die oneinding lang tetris blijft spelen? Of kan hij zoveel 'pech' hebben dat ie altijd wel een keer af gaat?
Tot nu toe heb ik hem zo ver gekregen dat ie gemiddeld zo'n 75 lijnen heeft gemaakt voor ie afgaat. Soms gaat ie al na 30 lijnen af, maar hij haalde ook een keer de 250 Hij heeft dus pech en geluk (vooral met die lange stukken).

URL naar mijn tetrisbot: http://home.wanadoo.nl/mlangenbach/Tetris.ace
Tetris2.exe gaat supersnel (zodat je snel kunt zien tot hoeveel lijnen ie gaat).
Tetris.exe gaat gewoon normaal traag, je kan deze ook zelf spelen. (op C drukken laat de PC spelen).
Voor de liefhebbers zit de code er ook bij (Tetris.pas)

Dit topic hoorde naar mijn gevoel toch hier thuis, omdat je beetje moet 'filosoferen' over of het oneindig lang door kan gaan of niet.

[Mx. Alba]

Het probleem is dat zo'n bot geen inzicht heeft. Hij gaat uit van wat er licht, en van het ene stuk waarvan hij weet dat die daarna komt. Maar een mens gaat ook uit van ervaring en inzicht, en kan dus ook stukken plaatsen in de verwachting dat binnenkort het missende stuk zal vallen, ook al komt die niet meteen. Een tetrisbot zal dus altijd voor winst op de korte termijn gaan, terwijl een mens in staat is om ondanks het ontbreken van concrete informatie over wat komen gaat te gaan voor winst op de langere termijn.

(Een tetrinet-bot is volgens mij juist daardoor ook veel moeilijker dan een tetris-bot, omdat je bij tetrinet veel meer op die onzekere toekomst moet werken)

[Orphix]

Er stond hier laatst ook iets over op tweakers:
nieuws: Wetenschappelijk bewezen: Tetris is ingewikkeld

[QuestGamer]

Damn, weer een droom in duigen gevallen

--
Men heeft namelijk bewezen dat Tetris voldoet aan de eisen van een 'NP-compleet probleem'. Dit houdt in dat er geen algoritme te geven is dat een efficiënte manier van spelen berekent.

Zowel het maximaliseren van het aantal weggespeelde rijen, het aantal geplaatste stenen voordat het spel afgelopen is en het aantal tetrises (vier rijen tegelijk wegspelen), als het zo laag mogelijk houden van het bouwwerk, zijn niet wetenschappelijk te bereiken.
--

Jammer dan

Toch denk ik dat het mogelijk is de bot nog veel langer te laten spelen als dat ie nu doet. Maar ik weet niet goed hoe...

[Anoniem: 55510]

QuestGamer schreef op 17 November 2002 @ 14:48:
Damn, weer een droom in duigen gevallen

--
Men heeft namelijk bewezen dat Tetris voldoet aan de eisen van een 'NP-compleet probleem'. Dit houdt in dat er geen algoritme te geven is dat een efficiënte manier van spelen berekent.

Zowel het maximaliseren van het aantal weggespeelde rijen, het aantal geplaatste stenen voordat het spel afgelopen is en het aantal tetrises (vier rijen tegelijk wegspelen), als het zo laag mogelijk houden van het bouwwerk, zijn niet wetenschappelijk te bereiken.
--

Jammer dan

Toch denk ik dat het mogelijk is de bot nog veel langer te laten spelen als dat ie nu doet. Maar ik weet niet goed hoe...

Dit betekent niet dat het niet mogelijk is om het oneindig door te laten gaan hoor. Het ging om de effiecientste manier, die is niet te berekenen, maar met een goed programma kan je computer het waarschijnlijk wel oneindig volhouden.

[Justice]

offtopic:
zeer goed gemaakt zeg! ja wat ik nou zou verbeteren in je programma is dat je verschillende strategieën gebruikt naar gelang het aantal stukjes. Met een soort basisstrategie als uitgangspunt. De PC ging bij mij bijvoorbeeld af, omdat hij te lang wachtte op een lange gele. Als je dan zorgt dat wanneer er bijvoorbeeld 50% van het scherm gevult is met lijnen, overschakelt op "zo snel mogelijk lijnen weg krijgen".

[Grum]

En hoe het echt moet:

Mirrors: (~13mb)

http://evol.ath.cx/files/mpg/tetris_japan_finals.mpeg
http://jivemagazine.com/misc/tetris_japan_finals.mpeg
http://penguinppc.org/~olaf/tetris_japan_finals.mpeg

[QuestGamer]

Justice schreef op 17 November 2002 @ 15:06:

offtopic:
zeer goed gemaakt zeg! ja wat ik nou zou verbeteren in je programma is dat je verschillende strategieën gebruikt naar gelang het aantal stukjes. Met een soort basisstrategie als uitgangspunt. De PC ging bij mij bijvoorbeeld af, omdat hij te lang wachtte op een lange gele. Als je dan zorgt dat wanneer er bijvoorbeeld 50% van het scherm gevult is met lijnen, overschakelt op "zo snel mogelijk lijnen weg krijgen".

Klopt helemaal, hij gaat eigenlijk bijna altijd af als ie te lang aan het wachten is op een lange gele. Dat is het grootste probleem
Ga ik nog wel mee aan de gang.
Maar zo 'offtopic' is dat toch niet?

En dat Japanse filmpje is asociaal

[Anoniem: 61635]

Hmm... what about Brute Force?

Dat zou het toch moeten doen...

[Firestormer]

Anoniem: 61635 schreef op 17 November 2002 @ 18:45:
Hmm... what about Brute Force?

Dat zou het toch moeten doen...

De vraag is > hoe wil jij een som uitreken als je alle getallen en het antwoord nog niet weet
de blokjes worden RANDOM gegenereert
Je kunt wel gaan brute forcen
maar stel je voor je moet een ruimte inruimen
en je krijgt elke keer 2 stukjes dat je dat nooit 100% perfect kan inruimen
bij tetris word je bij elke zet op een ander dood spoor gezet
er is immers ook geen algoritme wat de blokjes kiest

en stel je laat de computer doorspelen en hij speelt zo save mogelijk
dan krijgt hij op een gegeven moment een reeks pechcijfers/blokjes en dan verliest hij gewoon

laten we het probleem maar ff verplaatsen naar de roulette tafel
een computer kan daar ook niet weten welk nummer het wordt omdat het balletje gewoon random valt eigenluk hoort tetris ook onder kansspelen

als je een gokkast zo afstelt dat de kansen gelijk zijn dan zou je op het laatst ook verliesen

omdat er aan het aantal winst geen limiet zit maar aan het verlies wel

je mag immers 1000000000000 winnen maar je mag maar 0 keer verliesen
daar komt de het gezegde je kunt niet altijd winnen vandaan
ook de computer niet

als je niet kan verliesen dan kan je toch ook niet winnen en je kan pas doodgaan als je geleefd hebt

Tetris is dus eindig en wanneer het eindig is is random

[Justice]

Tetris is eindig, maar je kan natuurlijk wel 100 jaar door blijven spelen, alleen als je niet 100% van de tijd met dezelfde strategie speelt. Want elke tetris strategie heeft voordelen en nadelen (bijvoorbeeld wachten op een tetris -> stapelen) dus als je van strategie veranderd dan kan je de uitkomst daarmee veranderen, ongeacht de blokjes (als de strategieën elkaar kunnen opheffen). Tenminste dat denk ik

[Anoniem: 9942]

De vraag is: Is het mogelijk een serie blokjes te verzinnen waarmee je niet KUNT winnen? Als dat zo is, is tetris eindig, want aangezien de stroom blokjes random is zal die serie ook optreden. Als er voor elke stroom blokjes in principe een oplossing is, moet een speler theoretisch oneindig lang door kunnen gaan. En als er een (niet oneindig complexe) strategie te vinden is die voor elke willekeurige stroom blokjes "wint", kan een bot oneindig lang door blijven gaan.

[Anoniem: 64162]

Maar zoals ze in de post van tweakers zeiden is het een complex spel. Het zal dus niet lukken of zeer moeilijk zijn om een bot zoiets te leren. Ik heb je code niet bekeken maar je kan tetris alleen blijven spelen als je bot vooruit kan denken en creatief kan zijn. Het zomaar neerzetten omdat er ruimte is voor een blokje is denk ik meer geluk dan wijsheid van de bot

[jvdmeer]

Ik weet niet zeker, maar kan het niet door de computer parallel worden gespeeld op bijvoorbeeld 10000 tetris-borden tegelijkertijd. En na elke vijf stenen evalueren en de slechtste borden weer weggooien en vervangen door de beste borden? En zodoende beter anticiperen op de random stenen?

[Opi]

Probeer eens deze site. http://www.math.tau.ac.il...t_proj/livnat/tetris.html
Dit type lerende systemen is erg veel belovend.

[Anoniem: 29081]

De vraag is: Is het mogelijk een serie blokjes te verzinnen waarmee je niet KUNT winnen? Als dat zo is, is tetris eindig, want aangezien de stroom blokjes random is zal die serie ook optreden. Als er voor elke stroom blokjes in principe een oplossing is, moet een speler theoretisch oneindig lang door kunnen gaan. En als er een (niet oneindig complexe) strategie te vinden is die voor elke willekeurige stroom blokjes "wint", kan een bot oneindig lang door blijven gaan.

Ik denk dat er voor elke serie blokjes een oplossing valt te verzinnen ("oplossing" betekent hier dat je na het verwerken van die blokjes niet af bent, en liefst zo weinig mogelijk rommel in je speelveld over hebt). Echter, een tetris algoritme weet van te voren niet welke serie er komt, en dat is een belangrijke beperking. Want ik denk wél dat er voor elk tetris-algoritme een serie blokjes te verzinnen is waarmee dat algoritme op z'n bek gaat.

Dit zou bewezen moeten worden natuurlijk.. maar intuitief denk ik dat er geen (eindig) algoritme te vinden is dat in alle gevallen feilloos werkt.

[QUILIX]

Download Bricklayer 1.6

http://www.portal5.co.uk/programs/games/brick.zip

Die spel heeft een 'Auto Play'
Je kan kiezen uit 'Quick & Dirty' wat snel eindigd. En 'Deep Thought'. Dit
is dacht ik eindeloos. De computer speelt dan zelf eindeloos tetris.

[ravenger]

uitgaande dat de computer dezelfde mogelijkheden heeft als de mens, dus dat hij 1 blokje van te voren te zien krijgt wat het volgende blokje wordt, en je deelt het speelveld zo in rasters op, doe je er een snifje AI in die bot en dan denk ik dat echt wel kan, omdat de computer dan uit kan rekenen als er een blokje valt waar hij het huidige blokje het beste kan laten vallen om het volgende blokje een mooie plek te geven.
Als je dan de computer niet 100 tetrisborden naastelkaar laten lopen maar vele meerderen, ligt et denk ik voornamelijk aan de kracht van de processor en het geheugen van de computer die het uitvoert, tegenwoordig zijn er zulke grote supercomputers die dat soort dingen aankunnen.
De rede waarom het nog niet gelukt is, is simpelweg dan ook omdat men het nog niet op deze wijze heeft geprobeerd (imo vrij nutteloos )en daarom nog niet een zo complexe algoritme is gevonden die dat kan. Theoretisch is het volgens mij wel degelijk mogelijk dus

[QuestGamer]

Bah dat Bricklayer gaat best lang door...
Maar of het oneindig is weet ik niet.

Tis een raar systeem, het gaat te snel om het te kunnen doorzien helaas.
Maar hij zorgt voor erg veel gaatjes. In tegenstelling tot mijn versie, die had 0 gaten maar ging wel af na een tijdje.

(edit: mooi, na 4000 lijnen ging ie af, en de keer daarna al na 500 lijnen)

Kunnen we nu concluderen dat een perfecte tetrisbot gewoon NIET te maken is?
En is Bricklayer al het beste wat mogelijk is, of kan het nog beter?

[Justice]

gaatjes moet je zien als een bankrekening.. ruimte die je opslaat om later te kunnen gebruiken

[QuestGamer]

RaVeNgEr schreef op 18 November 2002 @ 19:02:Theoretisch is het volgens mij wel degelijk mogelijk dus

Ja, ik denk dus ook nog steeds dat het theoretisch mogelijk is. En wat jij zegt zit wel wat in ja. En dat kost idd flink wat rekenkracht

Maar wat is het best wat we met een huis,tuin en keuken PC (2 Ghz ) kunnen maken?

[Opi]

Op zich lijkt het mij best mogelijk om een tetrisspeler te ontwikkelen die in staat is oneindig lang door te spelen. Er zijn genoeg regeltechnieken bekend die dergelijke problemen kunnen oplossen een simpel voorbeeld hiervan zijn dynamic programming en model predictive control, die alle mogelijke evalueren en kijken wat de beste keus is (statistisch gezien aangezien de stukken random geselecteerd worden). Maar zoals CP al had opgemerkt kan het tegendeel pas bewezen worden indien er een serie wordt bedacht die niet op te lossen valt.

[Anoniem: 9942]

PaulOldenzaal: Dat hoort hier niet. Je bericht is verwijderd.

[Anoniem: 9942]

Ik denk dat er voor elke serie blokjes een oplossing valt te verzinnen ("oplossing" betekent hier dat je na het verwerken van die blokjes niet af bent, en liefst zo weinig mogelijk rommel in je speelveld over hebt). Echter, een tetris algoritme weet van te voren niet welke serie er komt, en dat is een belangrijke beperking. Want ik denk wél dat er voor elk tetris-algoritme een serie blokjes te verzinnen is waarmee dat algoritme op z'n bek gaat.

Dit zou bewezen moeten worden natuurlijk.. maar intuitief denk ik dat er geen (eindig) algoritme te vinden is dat in alle gevallen feilloos werkt.

Is op zich ook mijn intuitie, maar het is niet nodig dat het algorithme feilloos werkt, zolang het maar voldoende is om te voorkomen dat er een accumulatie van blokjes optreedt. Dat is misschien wel haalbaar. Overigens vraag ik me dan af of een mens theoretisch gezien oneindig lang tetris kan spelen (zoalg het niet steeds sneller en sneller gaat). Als dit zo is, zou een computer het in principe ook moeten kunnen.