Document Open Access Logo

How Fast Can We Play Tetris Greedily with Rectangular Pieces?

Authors Justin Dallant , John Iacono

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.13.pdf
  • Filesize: 0.87 MB
  • 19 pages

Document Identifiers

Author Details

Justin Dallant
  • Université libre de Bruxelles, Belgium
John Iacono
  • Université libre de Bruxelles, Belgium

Funding

  • Dallant, Justin: Supported by the French Community of Belgium via the funding of a FRIA grant.
  • Iacono, John: Supported by the Fonds de la Recherche Scientifique-FNRS under Grant no MISU F 6001 1.

Acknowledgements

We thank Nemau for involuntarily providing us with the initial inspiration for this work.

Cite As Get BibTex

Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily with Rectangular Pieces?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FUN.2022.13

Abstract

Consider a variant of Tetris played on a board of width w and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of O(n) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Pătraşcu, 2010] that on a board of width w = Θ(n), if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time O(n^{1/2-ε}) simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in O(n^{1/2}log^{3/2}n) time on boards of width n^O(1), matching the lower bound up to an n^o(1) factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Tetris
  • Fine-grained complexity
  • Dynamic data structures
  • Axis-aligned rectangles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477-486. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.58.
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  3. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098-1122, 2018. URL: https://doi.org/10.1137/15M1050987.
  4. Simón Algorta and Özgür Simsek. The game of Tetris in machine learning. CoRR, abs/1905.01652, 2019. URL: http://arxiv.org/abs/1905.01652.
  5. Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. Dynamic parameterized problems and algorithms. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.41.
  6. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 114-125. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_10.
  7. Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap! - online dictionary matching with one gap. Algorithmica, 81(6):2123-2157, 2019. URL: https://doi.org/10.1007/s00453-018-0526-2.
  8. Diana Sofía Lora Ariza. El clustering de jugadores de Tetris. In David Camacho, Marco Antonio Gómez-Martín, and Pedro Antonio González-Calero, editors, Proceedings 2st Congreso de la Sociedad Española para las Ciencias del Videojuego, Barcelona, Spain, June 24, 2015, volume 1394 of CEUR Workshop Proceedings, pages 36-45. CEUR-WS.org, 2015. URL: http://ceur-ws.org/Vol-1394/paper_4.pdf.
  9. Diana Sofía Lora Ariza, Antonio A. Sánchez-Ruiz, and Pedro A. González-Calero. Time series and case-based reasoning for an intelligent Tetris game. In David W. Aha and Jean Lieber, editors, Case-Based Reasoning Research and Development - 25th International Conference, ICCBR 2017, Trondheim, Norway, June 26-28, 2017, Proceedings, volume 10339 of Lecture Notes in Computer Science, pages 185-199. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-61030-6_13.
  10. Diana Sofía Lora Ariza, Antonio A. Sánchez-Ruiz, and Pedro A. González-Calero. Towards finding flow in Tetris. In Kerstin Bach and Cindy Marling, editors, Case-Based Reasoning Research and Development - 27th International Conference, ICCBR 2019, Otzenhausen, Germany, September 8-12, 2019, Proceedings, volume 11680 of Lecture Notes in Computer Science, pages 266-280. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-29249-2_18.
  11. Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal. Tetris is np-hard even with O(1) rows or columns. J. Inf. Process., 28:942-958, 2020. URL: https://doi.org/10.2197/ipsjjip.28.942.
  12. Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal. Tetris is np-hard even with dollaro(1)dollar rows or columns. CoRR, abs/2009.14336, 2020. URL: http://arxiv.org/abs/2009.14336.
  13. Davide Baccherini and Donatella Merlini. Combinatorial analysis of Tetris-like games. Discret. Math., 308(18):4165-4176, 2008. URL: https://doi.org/10.1016/j.disc.2007.08.009.
  14. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3sum. Algorithmica, 50(4):584-596, 2008. URL: https://doi.org/10.1007/s00453-007-9036-3.
  15. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS in undirected graphs: breaking the o(m) barrier. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 730-739. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch52.
  16. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303-318. ACM, 2017. URL: https://doi.org/10.1145/3034786.3034789.
  17. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering UCQs under updates and in the presence of integrity constraints. In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 8:1-8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.8.
  18. Jacquelyn H. Berry and Wayne D. Gray. HOT: higher order Tetris, experts' subgoals and activities. In Ashok K. Goel, Colleen M. Seifert, and Christian Freksa, editors, Proceedings of the 41th Annual Meeting of the Cognitive Science Society, CogSci 2019: Creativity + Cognition + Computation, Montreal, Canada, July 24-27, 2019, page 3409. cognitivesciencesociety.org, 2019. URL: https://mindmodeling.org/cogsci2019/papers/0717/index.html.
  19. Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell. Tetris is hard, even to approximate. Int. J. Comput. Geom. Appl., 14(1-2):41-68, 2004. URL: https://doi.org/10.1142/S0218195904001354.
  20. Karl Bringmann. Fine-grained complexity theory (tutorial). In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 4:1-4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.4.
  21. Timothy M. Chan. Semi-online maintenance of geometric optima and measures. SIAM J. Comput., 32(3):700-716, 2003. URL: https://doi.org/10.1137/S0097539702404389.
  22. Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. Discret. Comput. Geom., 64(4):1235-1252, 2020. URL: https://doi.org/10.1007/s00454-020-00229-5.
  23. Timothy M. Chan. More logarithmic-factor speedups for 3sum, (median, +)-convolution, and some geometric 3sum-hard problems. ACM Trans. Algorithms, 16(1):7:1-7:23, 2020. URL: https://doi.org/10.1145/3363541.
  24. Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. Nearly optimal separation between partially and fully retroactive data structures. In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018, June 18-20, 2018, Malmö, Sweden, volume 101 of LIPIcs, pages 33:1-33:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.33.
  25. Tsung Teng Chen. Chitetris: A Chinese proverb learning game utilizing Tetris game plot. In Gautam Biswas, Diane Carr, Yam San Chee, and Wu-Yuin Hwang, editors, 2010 Third IEEE International Conference on Digital Game and Intelligent Toy Enhanced Learning, DIGITEL 2010, Kaohsiung, Taiwan, April 12-16, 2010, pages 194-197. IEEE, 2010. URL: https://doi.org/10.1109/DIGITEL.2010.34.
  26. Stephen A. Cook. The complexity of theorem-proving procedures. In Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman, editors, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151-158. ACM, 1971. URL: https://doi.org/10.1145/800157.805047.
  27. Stephen J. Cowley and Karl F. MacDorman. What baboons, babies and Tetris players tell us about interaction: a biosocial view of norm-based social learning. Connect. Sci., 18(4):363-378, 2006. URL: https://doi.org/10.1080/09540090600879703.
  28. Antonios N. Dadaliaris, Evangelia Nerantzaki, Maria G. Koziri, Panagiotis Oikonomou, Thanasis Loukopoulos, and Georgios I. Stamoulis. Performance evaluation of Tetris-based legalization heuristics. In Proceedings of the 20th Pan-Hellenic Conference on Informatics, Patras, Greece, November 10-12, 2016, page 60. ACM, 2016. URL: https://doi.org/10.1145/3003733.3003778.
  29. Antonios N. Dadaliaris, Evangelia Nerantzaki, Panagiotis Oikonomou, Yannis Hatzaras, Angeliki-Olympia Troumpoulou, Ioannis Arvanitakis, and Georgios I. Stamoulis. Enhanced Tetris legalization. In Proceedings of the SouthEast European Design Automation, Computer Engineering, Computer Networks and Social Media Conference, SEEDA-CECNSM 2016, Kastoria, Greece, September 25-27, 2016, pages 32-35. ACM, 2016. URL: https://doi.org/10.1145/2984393.2984410.
  30. Antonios N. Dadaliaris, Panagiotis Oikonomou, Maria G. Koziri, Evangelia Nerantzaki, Yannis Hatzaras, Dimitrios Garyfallou, Thanasis Loukopoulos, and Georgios I. Stamoulis. Heuristics to augment the performance of Tetris legalization: Making a fast but inferior method competitive. J. Low Power Electron., 13(2):220-230, 2017. URL: https://doi.org/10.1166/jolpe.2017.1483.
  31. Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 48:1-48:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.48.
  32. Justin Dallant and John Iacono. Conditional lower bounds for dynamic geometric measure problems, 2021. URL: http://arxiv.org/abs/2112.10095.
  33. Guylain Delmas, Ronan Champagnat, and Michel Augeraud. Plot control for emergent narrative: A case study on Tetris. Int. J. Intell. Games Simul., 5(1), 2008. URL: http://www.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/article/view/56.
  34. Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, and Yun William Yu. Total Tetris: Tetris with monominoes, dominoes, trominoes, pentominoes, . J. Inf. Process., 25:515-527, 2017. URL: https://doi.org/10.2197/ipsjjip.25.515.
  35. Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell. Tetris is hard, even to approximate. CoRR, cs.CC/0210020, 2002. URL: https://arxiv.org/abs/cs/0210020.
  36. Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell. Tetris is hard, even to approximate. In Tandy J. Warnow and Binhai Zhu, editors, Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings, volume 2697 of Lecture Notes in Computer Science, pages 351-363. Springer, 2003. URL: https://doi.org/10.1007/3-540-45071-8_36.
  37. Giorgio Fasano. A MIP approach for some practical packing problems: Balancing constraints and tetris-like items. 4OR, 2(2):161-174, 2004. URL: https://doi.org/10.1007/s10288-004-0037-7.
  38. Enrico Formenti and Paolo Massazza. From Tetris to polyominoes generation. Electron. Notes Discret. Math., 59:79-98, 2017. URL: https://doi.org/10.1016/j.endm.2017.05.007.
  39. Anka Gajentaan and Mark H. Overmars. On a class of o(n2) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  40. Jacob E. Goodman and Joseph O'Rourke, editors. Handbook of Discrete and Computational Geometry, Second Edition. Chapman and Hall/CRC, 2004. URL: https://doi.org/10.1201/9781420035315.
  41. Wayne D. Gray, Ray S. Perez, John K. Lindstedt, Anna Skinner, Robin Johnson, Richard E. Mayer, Deanne Adams, and Robert K. Atkinson. Tetris as research paradigm: An approach to studying complex cognitive skills. In Paul Bello, Marcello Guarini, Marjorie McShane, and Brian Scassellati, editors, Proceedings of the 36th Annual Meeting of the Cognitive Science Society, CogSci 2014, Quebec City, Canada, July 23-26, 2014. cognitivesciencesociety.org, 2014. URL: https://mindmodeling.org/cogsci2014/papers/019/.
  42. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 621-630. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.72.
  43. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  44. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional hardness for sensitivity problems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 26:1-26:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.26.
  45. Hendrik Jan Hoogeboom and Walter A. Kosters. How to construct Tetris configurations. Int. J. Intell. Games Simul., 3(2):97-105, 2004. URL: http://www.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/article/view/95.
  46. Hendrik Jan Hoogeboom and Walter A. Kosters. Tetris and decidability. Inf. Process. Lett., 89(6):267-272, 2004. URL: https://doi.org/10.1016/j.ipl.2003.12.006.
  47. Aline Hufschmitt, Stéphane Cardon, and Éric Jacopin. Can musical tempo makes Tetris game harder? In IEEE Conference on Games, CoG 2020, Osaka, Japan, August 24-27, 2020, pages 608-611. IEEE, 2020. URL: https://doi.org/10.1109/CoG47356.2020.9231593.
  48. Aline Hufschmitt, Stéphane Cardon, and Éric Jacopin. Manipulating player performance via music tempo in Tetris. In Pejman Mirza-Babaei, Victoria McArthur, Vero Vanden Abeele, and Max Birk, editors, CHI PLAY '20: The Annual Symposium on Computer-Human Interaction in Play, Virtual Event, Canada, November 2-4, 2020 - Companion Volume / Extended Abstracts, pages 146-152. ACM, 2020. URL: https://doi.org/10.1145/3383668.3419934.
  49. Aline Hufschmitt, Stéphane Cardon, and Éric Jacopin. Dynamic manipulation of player performance with music tempo in Tetris. In Tracy Hammond, Katrien Verbert, Dennis Parra, Bart P. Knijnenburg, John O'Donovan, and Paul Teale, editors, IUI '21: 26th International Conference on Intelligent User Interfaces, College Station, TX, USA, April 13-17, 2021, pages 290-296. ACM, 2021. URL: https://doi.org/10.1145/3397481.3450684.
  50. Peter C. Jentsch and Chrystopher L. Nehaniv. Exploring Tetris as a transformation semigroup. CoRR, abs/2004.09022, 2020. URL: http://arxiv.org/abs/2004.09022.
  51. Patrick Jermann, Marc-Antoine Nüssli, and Weifeng Li. Using dual eye-tracking to unveil coordination and expertise in collaborative Tetris. In Tom McEwan and Lachlan McKinnon, editors, Proceedings of the 2010 British Computer Society Conference on Human-Computer Interaction, BCS-HCI 2010, Dundee, United Kingdom, 6-10 September 2010, pages 36-44. ACM, 2010. URL: http://dl.acm.org/citation.cfm?id=2146309.
  52. Will Jordan. Morphology of the tetromino-stacking game: The design evolution of Tetris [abstract]. In Tanya Krzywinska, Helen W. Kennedy, and Barry Atkins, editors, Proceedings of the 2009 DiGRA International Conference: Breaking New Ground: Innovation in Games, Play, Practice and Theory, DiGRA 2009, London, UK, September 1-4, 2009. Digital Games Research Association, 2009. URL: http://www.digra.org/digital-library/publications/morphology-of-the-tetromino-stacking-game-the-design-evolution-of-tetris-abstract/.
  53. Adam Karczmarz and Jakub Lacki. Fast and simple connectivity in graph timelines. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, volume 9214 of Lecture Notes in Computer Science, pages 458-469. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21840-3_38.
  54. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  55. Stephen A. Keating, Wan-Chen Lee, Travis W. Windleharth, and Lee Jin Ha. The style of Tetris is...possibly Tetris?: Creative professionals' description of video game visual styles. In Tung Bui, editor, 50th Hawaii International Conference on System Sciences, HICSS 2017, Hilton Waikoloa Village, Hawaii, USA, January 4-7, 2017, pages 1-10. ScholarSpace / AIS Electronic Library (AISeL), 2017. URL: http://hdl.handle.net/10125/41402.
  56. Sirisilp Kongsilp, Hathaichanok Chawmungkrung, and Takashi Komuro. Pop-out Tetris: An implementation of a tablet FTVR game. In 15th International Joint Conference on Computer Science and Software Engineering, JCSSE 2018, Nakhonpathom, Thailand, July 11-13, 2018, pages 1-5. IEEE, 2018. URL: https://doi.org/10.1109/JCSSE.2018.8457377.
  57. Tsvi Kopelowitz and Robert Krauthgamer. Color-distance oracles and snippets. In Roberto Grossi and Moshe Lewenstein, editors, 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel, volume 54 of LIPIcs, pages 24:1-24:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CPM.2016.24.
  58. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272-1287. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch89.
  59. Laurens R. Krol, Sarah-Christin Freytag, and Thorsten O. Zander. Meyendtris: a hands-free, multimodal tetris clone using eye tracking and passive BCI for intuitive neuroadaptive gaming. In Edward Lank, Alessandro Vinciarelli, Eve E. Hoggan, Sriram Subramanian, and Stephen A. Brewster, editors, Proceedings of the 19th ACM International Conference on Multimodal Interaction, ICMI 2017, Glasgow, United Kingdom, November 13 - 17, 2017, pages 433-437. ACM, 2017. URL: https://doi.org/10.1145/3136755.3136805.
  60. Ian J. Lewis and Sebastian L. Beswick. Generalisation over details: The unsuitability of supervised backpropagation networks for Tetris. Adv. Artif. Neural Syst., 2015:157983:1-157983:8, 2015. URL: https://doi.org/10.1155/2015/157983.
  61. Weifeng Li, Marc-Antoine Nüssli, and Patrick Jermann. Gaze quality assisted automatic recognition of social contexts in collaborative Tetris. In Wen Gao, Chin-Hui Lee, Jie Yang, Xilin Chen, Maxine Eskénazi, and Zhengyou Zhang, editors, Proceedings of the 12th International Conference on Multimodal Interfaces / 7. International Workshop on Machine Learning for Multimodal Interaction, ICMI-MLMI 2010, Beijing, China, November 8-12, 2010, pages 8:1-8:8. ACM, 2010. URL: https://doi.org/10.1145/1891903.1891914.
  62. Weifeng Li, Marc-Antoine Nüssli, and Patrick Jermann. Exploring personal aspects using eye-tracking modality in Tetris-playing. In IEEE 13th International Workshop on Multimedia Signal Processing (MMSP 2011), Hangzhou, China, October 17-19, 2011, pages 1-4. IEEE, 2011. URL: https://doi.org/10.1109/MMSP.2011.6093841.
  63. John K. Lindstedt and Wayne D. Gray. Extreme expertise: Exploring expert behavior in Tetris. In Markus Knauff, Michael Pauen, Natalie Sebanz, and Ipke Wachsmuth, editors, Proceedings of the 35th Annual Meeting of the Cognitive Science Society, CogSci 2013, Berlin, Germany, July 31 - August 3, 2013. cognitivesciencesociety.org, 2013. URL: https://mindmodeling.org/cogsci2013/papers/0183/index.html.
  64. John K. Lindstedt and Wayne D. Gray. The "cognitive speed-bump": How world champion Tetris players trade milliseconds for seconds. In Stephanie Denison, Michael Mack, Yang Xu, and Blair C. Armstrong, editors, Proceedings of the 42th Annual Meeting of the Cognitive Science Society - Developing a Mind: Learning in Humans, Animals, and Machines, CogSci 2020, virtual, July 29 - August 1, 2020. cognitivesciencesociety.org, 2020. URL: https://cogsci.mindmodeling.org/2020/papers/0020/index.html.
  65. Diana Lora, Antonio A. Sánchez-Ruiz, and Pedro A. González-Calero. Difficulty adjustment in Tetris with time series. In David Camacho, Marco Antonio Gómez-Martín, and Pedro Antonio González-Calero, editors, Proceedings of the 3rd Congreso de la Sociedad Española para las Ciencias del Videojuego, Barcelona, Spain, June 29, 2016, volume 1682 of CEUR Workshop Proceedings, pages 89-100. CEUR-WS.org, 2016. URL: http://ceur-ws.org/Vol-1682/CoSeCiVi16_paper_10.pdf.
  66. Diana Lora, Antonio A. Sánchez-Ruiz, Pedro A. González-Calero, and Marco Antonio Gómez-Martín. Dynamic difficulty adjustment in Tetris. In Zdravko Markov and Ingrid Russell, editors, Proceedings of the Twenty-Ninth International Florida Artificial Intelligence Research Society Conference, FLAIRS 2016, Key Largo, Florida, USA, May 16-18, 2016, pages 335-339. AAAI Press, 2016. URL: http://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS16/paper/view/12824.
  67. Danica Mast and Sanne de Vries. Cooperative Tetris: The influence of social exertion gaming on game experience and social presence. In Ronald Poppe, John-Jules Ch. Meyer, Remco C. Veltkamp, and Mehdi Dastani, editors, Intelligent Technologies for Interactive Entertainment - 8th International Conference, INTETAIN 2016, Utrecht, The Netherlands, June 28-30, 2016, Revised Selected Papers, volume 178 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 115-123. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49616-0_11.
  68. Taishi Oikawa, Chu-Hsuan Hsueh, and Kokolo Ikeda. Improving human players' t-spin skills in Tetris with procedural problem generation. In Tristan Cazenave, H. Jaap van den Herik, Abdallah Saffidine, and I-Chen Wu, editors, Advances in Computer Games - 16th International Conference, ACG 2019, Macao, China, August 11-13, 2019, Revised Selected Papers, volume 12516 of Lecture Notes in Computer Science, pages 41-52. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-65883-0_4.
  69. Panagiotis Oikonomou, Antonios N. Dadaliaris, Thanasis Loukopoulos, Athanasios Kakarountas, and Georgios I. Stamoulis. A Tetris-based legalization heuristic for standard cell placement with obstacles. In 7th International Conference on Modern Circuits and Systems Technologies, MOCAST 2018, Thessaloniki, Greece, May 7-9, 2018, pages 1-4. IEEE, 2018. URL: https://doi.org/10.1109/MOCAST.2018.8376559.
  70. Zhan-He Ou and Ling-Hwei Chen. Hiding data in Tetris. In International Conference on Machine Learning and Cybernetics, ICMLC 2011, Guilin, China, July 10-13, 2011, Proceedings, pages 61-67. IEEE, 2011. URL: https://doi.org/10.1109/ICMLC.2011.6016684.
  71. Zhan-He Ou and Ling-Hwei Chen. A steganographic method based on tetris games. Inf. Sci., 276:343-353, 2014. URL: https://doi.org/10.1016/j.ins.2013.12.024.
  72. Jing Pang, Manuel Pravin, and Robert Tanihaha. Microblaze soft core based FPGA embedded system design of Tetris game. In Hamid R. Arabnia and Ashu M. G. Solo, editors, Proceedings of the 2010 International Conference on Embedded Systems & Applications, ESA 2010, July 12-15, 2010, Las Vegas Nevada, USA, pages 79-85. CSREA Press, 2010. Google Scholar
  73. Nick Parlante. Nifty assignments: tetris on the brain. ACM SIGCSE Bull., 33(4):25-27, 2001. URL: https://doi.org/10.1145/572139.572162.
  74. Georgios Patsis, Hichem Sahli, Werner Verhelst, and Olga De Troyer. Evaluation of attention levels in a Tetris game using a brain computer interface. In Sandra Carberry, Stephan Weibelzahl, Alessandro Micarelli, and Giovanni Semeraro, editors, User Modeling, Adaptation, and Personalization - 21th International Conference, UMAP 2013, Rome, Italy, June 10-14, 2013, Proceedings, volume 7899 of Lecture Notes in Computer Science, pages 127-138. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38844-6_11.
  75. Colin Pinnell. Computer games for learning: An evidence-based approach (author: Richard e. mayer). J. Educ. Technol. Soc., 18(4):523-524, 2015. URL: https://www.j-ets.net/ETS/journals/18_4/40.pdf.
  76. Gabriel Pires, Mario Torres, Nuno Casaleiro, Urbano Nunes, and Miguel Castelo-Branco. Playing Tetris with non-invasive BCI. In 2011 IEEE 1st International Conference on Serious Games and Applications for Health, SeGAH 2011, Braga, Portugal, November 16-18, 2011, pages 1-6. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/SeGAH.2011.6165454.
  77. Maximilian Probst. On the complexity of the (approximate) nearest colored node problem. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 68:1-68:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.68.
  78. Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, pages 603-610, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806772.
  79. Jana Rambusch, Tarja Susi, Stefan Ekman, and Ulf Wilhelmsson. A literary excursion into the hidden (fan) fictional worlds of Tetris, starcraft, and dreamfall. In Tanya Krzywinska, Helen W. Kennedy, and Barry Atkins, editors, Proceedings of the 2009 DiGRA International Conference: Breaking New Ground: Innovation in Games, Play, Practice and Theory, DiGRA 2009, London, UK, September 1-4, 2009. Digital Games Research Association, 2009. URL: http://www.digra.org/digital-library/publications/a-literary-excursion-into-the-hidden-fan-fictional-worlds-of-tetris-starcraft-and-dreamfall/.
  80. Catherine Sibert and Wayne D. Gray. When experts err: Using Tetris models to detect true errors from deliberate sub-optimal choices. In Ashok K. Goel, Colleen M. Seifert, and Christian Freksa, editors, Proceedings of the 41th Annual Meeting of the Cognitive Science Society, CogSci 2019: Creativity + Cognition + Computation, Montreal, Canada, July 24-27, 2019, page 3572. cognitivesciencesociety.org, 2019. URL: https://mindmodeling.org/cogsci2019/papers/0880/index.html.
  81. Catherine Sibert, Wayne D. Gray, and John K. Lindstedt. Tetris-: Exploring human performance via cross entropy reinforcement learning models. In David C. Noelle, Rick Dale, Anne S. Warlaumont, Jeff Yoshimi, Teenie Matlock, Carolyn D. Jennings, and Paul P. Maglio, editors, Proceedings of the 37th Annual Meeting of the Cognitive Science Society, CogSci 2015, Pasadena, California, USA, July 22-25, 2015. cognitivesciencesociety.org, 2015. URL: https://mindmodeling.org/cogsci2015/papers/0377/index.html.
  82. Catherine Sibert, John K. Lindstedt, and Wayne D. Gray. Tetris: Exploring human strategies via cross entropy reinforcement learning models. In Paul Bello, Marcello Guarini, Marjorie McShane, and Brian Scassellati, editors, Proceedings of the 36th Annual Meeting of the Cognitive Science Society, CogSci 2014, Quebec City, Canada, July 23-26, 2014. cognitivesciencesociety.org, 2014. URL: https://mindmodeling.org/cogsci2014/papers/743/.
  83. Özgür Simsek, Simón Algorta, and Amit Kothiyal. Why most decisions are easy in Tetris - and perhaps in other sequential decision problems, as well. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1757-1765. JMLR.org, 2016. URL: http://proceedings.mlr.press/v48/simsek16.html.
  84. Katta Spiel, Sven Bertel, and Fares Kayali. "Not another Z piece!": Adaptive difficulty in TETRIS. In Gloria Mark, Susan R. Fussell, Cliff Lampe, M. C. Schraefel, Juan Pablo Hourcade, Caroline Appert, and Daniel Wigdor, editors, Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems, Denver, CO, USA, pages 5126-5131. ACM, 2017. URL: https://doi.org/10.1145/3025453.3025721.
  85. Katta Spiel, Sven Bertel, and Fares Kayali. Adapting gameplay to eye movements - an exploration with TETRIS. In Joan Arnedo, Lennart E. Nacke, Vero Vanden Abeele, and Z O. Toups, editors, Extended Abstracts of the Annual Symposium on Computer-Human Interaction in Play Companion Extended Abstracts, Barcelona, Spain, October 22-25, 2019, pages 687-695. ACM, 2019. URL: https://doi.org/10.1145/3341215.3356267.
  86. Guo-Dong Su, Chin-Chen Chang, Chia-Chen Lin, and Zhi-Qiang Yao. Secure high capacity tetris-based scheme for data hiding. IET Image Process., 14(17):4633-4645, 2020. URL: https://doi.org/10.1049/iet-ipr.2019.1694.
  87. Guo-Dong Su, Chin-Chen Chang, Chia-Chen Lin, and Zhi-Qiang Yao. Erratum: Secure high capacity tetris-based scheme for data hiding. IET Image Process., 15(12):3020, 2021. URL: https://doi.org/10.1049/ipr2.12291.
  88. Tadao Takaoka. The reverse problem of range query. Electron. Notes Theor. Comput. Sci., 78:281-292, 2003. URL: https://doi.org/10.1016/S1571-0661(04)81018-1.
  89. Oscar Temprano. Complexity of a Tetris variant. CoRR, abs/1506.07204, 2015. URL: http://arxiv.org/abs/1506.07204.
  90. Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 456-480. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00036.
  91. Vladislav Daniel Veksler and Wayne D. Gray. State definition in the Tetris task: Designing a hybrid model of cognition. In Proceedings of the International Conference on Cognitive Modeling, ICCM 2004, Pittsburgh, Pennsylvania, USA, July 30 - August 1, 2004, pages 394-395, 2004. URL: http://www.lrdc.pitt.edu/schunn/ICCM2004/proceedings/abstracts/Vekser.pdf.
  92. Jianping Wang, Jun Chen, and Xiao-Min Li. Design a mobile Tetris game based on J2ME platform. In Chunfeng Liu, Jincai Chang, and Aimin Yang, editors, Information Computing and Applications - Second International Conference, ICICA 2011, Qinhuangdao, China, October 28-31, 2011. Proceedings, Part II, volume 244 of Communications in Computer and Information Science, pages 387-393. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-27452-7_53.
  93. R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965-1985, 2018. URL: https://doi.org/10.1137/15M1024524.
  94. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447-3487. WORLD SCIENTIFIC, 2019. URL: https://doi.org/10.1142/9789813272880_0188.
  95. Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 786-797. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00078.
  96. Jiajun Xu and Sam Huang. Tetris. CoRR, abs/1811.08614, 2018. URL: http://arxiv.org/abs/1811.08614.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact