Browsing by Organization "Datavetenskap, Institutionen för"

Sort by: Order: Results:

Now showing items 1-8 of 8
  • Saukonoja, Teemu; Pasanen, Tomi (2008)
    Artificial intelligence research in Texas Hold’em poker has recently mainly focused on heads-up fixed limit game. Game theoretic methods used in the poker agents capable of playing at the very best level are not easily generalized to other forms of Texas Hold’em poker. In this paper we present a general approach to build a poker agent, where the betting strategy is defined by estimating the expected values of the actions. This approach suites well larger number of players and it is also easily modified to suite no limit games. We focus on defining of the evaluation function. It has a very crucial part at the overall level of the poker agent in this kind of solution.
  • Yu, Huizhen; Rousu, Juho (2008)
    We consider structured prediction problems with a parametrized linear prediction function, and the associated parameter optimization problems in large margin type of discriminative training. We propose a dual optimization approach which uses the restricted simplicial decomposition method to optimize a reparametrized dual problem. Our reparametrization reduces the dimension of the space of the dual function to one that is linear in the number of parameters and training examples, and hence independent of the dimensionality of the prediction outputs. This in conjunction with simplicial decomposition makes our approach efficient. We discuss the connections of our approach with related earlier works, and we show its advantages.
  • Hinkkanen, Tero; Kurhila, Jaakko; Pasanen, Tomi A. (2008)
    We present a framework for evaluating believability of characters in first-person shooter (FPS) games and look into the development of non-player character’s user-perceived believability. The used framework is composed of two aspects: firstly, character movement and animation, secondly, behavior. Examination of three different FPS games yields that the newer the game was, the better the believability of characters in the game. Moreover, the results from both the aspects of the framework were mutually balanced through all games examined.
  • Yu, Huizhen; Bertsekas, Dimitri P. (2008)
    We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markov decision processes (MDP), one of our bounds is always sharper than the standard contraction-based bounds, and another one is often sharper. The former bound is also tight in a worst-case sense. Our bounds also apply to the non-contraction case, including policy evaluation in MDP with nonstandard projections that enhance exploration. There are no error bounds currently available for this case to our knowledge.
  • Pasanen, Tomi (2008)
    We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This introduces an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees.
  • Mäkinen, Veli; Navarro, Gonzalo; Sirén, Jouni; Välimäki, Niko (2008)
    A repetitive sequence collection is one where portions of a base sequence of length n are repeated many times with small variations, forming a collection of total length N. Examples of such collections are version control data and genome sequences of individuals, where the differences can be expressed by lists of basic edit operations. Flexible and efficient data analysis on a such typically huge collection is plausible using suffix trees. However, suffix tree occupies O(N logN) bits, which very soon inhibits in-memory analyses. Recent advances in full-text indexing reduce the space of suffix tree to NHk + o(N log σ) bits at the cost of running times of its operations increasing by polylog(N) factor. Here Hk is the k-th order entropy of the collection and σ is the alphabet size. Notice that for r identical copies of an incompressible base sequence, the bound simplifies to N log σ(1 + o(1)) bits. We develop new static/dynamic full-text self-indexes based on the run-length encoding whose space-requirements are much less dependent on N. For example, we obtain an index occupying Rlog σ(1+o(1))+R log N R (1+o(1))+r log n+O((s+r) log(s+r)) bits, where s is the total number of basic edit operations to convert the r repeats into substrings of the base sequence, and R ≤ min(n, nHk)+O((s+r) logσ N), where the O() term holds in the expected case. The new indexes can be plugged into a recent dynamic fully-compressed suffix tree using an additional O((N/δ) log N) bits of space for any δ = polylog(N), and retaining the polylog(N) time slowdown on operations.
  • Mäkinen, Veli; Sirén, Jouni; Välimäki, Niko (2008)
    In the near future, biomolecular engineering techniques will reach a state where the sequencing of individual genomes becomes feasible. This progress will create huge expectations for the data analysis domain to reveal new knowledge on the ”secrets of life”. Quite rudimentary reasons may inhibit such breakthroughs; it may not be feasible to store all the data in a form that would enable anything but most basic data analysis routines to be executed. This paper is devoted into studying ways to store massive sets of complete individual genomes in space-efficient manner so that retrieval of the content as well as queries on the content of the sequences can be provided time-efficiently. We show that although the state-of-the-art full-text self-indexes do not yet provide satisfactory space bounds for this specific task, after carefully engineering those structures it is possible to achieve very attractive results; the new structures are fully able to exploit the fact that the individual genomes are highly similar. We confirm the theoretical findings by experiments on large DNA sequences, and also on version control data, that forms another application domain for our methods.
  • Koski, Marja-Ilona; Kurhila, Jaakko; Pasanen, Tomi A. (2008)
    To help students understand subjects such as theoretical aspects of computation, algorithmic reasoning and intelligence of machines, a number of publications report experiments to teach these topics with the help of Lego Mindstorms robots. In the publications, the researchers report how they have created various ways to approach the issues either in Computer Science or in Artificial Intelligence. The reported results of the experiments are based on the learning outcomes, the feedback from the students, and the perceived informal observations (i.e. “feelings”) of the instructors. But can anyone else benefit from the reportedly positive outcomes of the experiments? To give an answer to that question, this paper analyses the reported results through two support theories. The two theories chosen for this, andragogy and minimalism, are concerned with adult learning and how teaching adults should be approached. When reflecting the results of the four teaching experiments to the suggestions drawn from the theories, a more comprehensive answer to why the experiments have been successful can be given. The four teaching experiments analysed here were in many ways similar to each other. A connection to the chosen support theories was straightforward to make. Besides describing the artefacts of teaching with the robots, a deeper discussion on this teaching approach is provided. For an instructor, all these observations offer more concrete evidence about beneficial factors of teaching with robots.