**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Game complexity

Summary

Combinatorial game theory measures game complexity in several ways:
#State-space complexity (the number of legal game positions from the initial position),
#Game tree size (total number of possible games),
#Decision complexity (number of leaf nodes in the smallest decision tree for initial position),
#Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position),
#Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).
These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios.
Measures of game complexity
State-space complexity
The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game.
When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can ne

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

No results

Related publications (12)

Related people

No results

Loading

Loading

Loading

Related concepts (11)

Game theory

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer

Computer chess

Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponent

Combinatorial game theory

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player

Related courses (7)

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

MGT-454: Principles of microeconomics

The course allows students to get familiarized with the basic tools and concepts of modern microeconomic analysis. Based on graphical reasoning and analytical calculus, it constantly links to real economic issues.

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented.

Related lectures (9)

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem (Wagner, 2002) allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 252 Bits of memory and about 29 times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 243 in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" (Howgrave-Graham, 2007) to attack NTRU by combinatorial attacks. Further, our attack is about 27 times faster than the space-reduced variant from (Howgrave-Graham, 2007) employing the same amount of memory.

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 2(52) Bits of memory and about 2(9) times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 2(43) in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" [3] to attack NTRU by combinatorial attacks. Further, our attack is about 2(7) times faster than the space-reduced variant from [3] employing the same amount of memory.

Volkan Cevher, Ya-Ping Hsieh, Yu-Chun Kao, Rabeeh Karimi Mahabadi, Anastasios Kyrillidis

We study convex optimization problems that feature low-rank matrix solutions. In such scenarios, non-convex methods offer significant advantages over convex methods due to their lower space complexity as well as faster convergence speed. Moreover, many of these methods feature rigorous approximation guarantees. Non-convex algorithms are simple to analyze and implement as they perform Euclidean gradient descent on matrix factors. In contrast, this paper derives non-Euclidean optimization frame- work in the non-convex setting that takes nonlinear gradient steps on the factors. We prove convergence rates to the global minimum under appropriate assumptions. We provide numerical evidence with Fourier Ptychography and FastText applications using real data that shows our approach can significantly enhance solution quality

2018