Gamble — A Multiuser Game with an Embodied Conversational Agent

Real-Time Multiplayer Gaming: Keeping Everyone on the Same PageSean A. PfeiferEmbry-Riddle Aeronautical Universitysarcius@AbstractIn the multiplayer world, whether it is in simulations or games, keeping clients and servers updated with the correct information can be a difficult problem to tackle. In a business where millions of customers rely on your systems to react in a timely fashion, it is important to properly handle latency. One could also take into consideration that even projects such as military simulations must deal with these issues. One of the main issues is dealing with network latency on both the client and server side. Another huge issue should come to mind at the same time: what about people who are attempting to cheat, or misuse the system? In other words, how do we provide a means to deal with the latency issue while preventing these systems from being abused to provide an unfair advantage to certain players? There are a multitude of ways to deal with both issues, with trade offs for each that must be balanced in order to create an acceptable experience.1. IntroductionLatency and cheating issues create major problems when dealing with a multiplayer application that is supposed to be “real-time.” The idea of “real-time” is used in this context to describe applications that have a low tolerance for missed deadlines. In this case, the systems are “soft real-time,” with flexible deadlines focused more on player experience. Many times, fixing one issue can have a negative affect on the other; when clients have more authority and logic, they can operate under high latency, however this usually makes a wide opening for cheaters.In these games, the game environment is usually constantly changing on the server, and thus clients need to be kept properly updated. Many times events occur server-side that require a player to react in a short period of time or face consequences, and in this way the entire system is real-time. Usually, deadlines may be missed and the consequences may only be a slight degradation, however many the response time constraints differ based on the application.It may help to put the problem into perspective if one imagines the applications being described as multiplayer action games, such as the “first-person shooter” or “flight simulation” categories of games. For instance, if a player is defending their base from an enemy scout who is about to open a door to enter, a delay of a fraction of a second for that one player can cause the loss of the game for the whole team. Another good example would be a pilot attempting to land an airplane, and then all of the sudden the controls and instruments stop responding. If these controls and instruments don't respond within a certain period of time, the pilot is very likely to have a harsh landing. When these sorts of things happen, players tend to get very agitated, and if it's a constantly recurring issue, your product sales may suffer. The timing issues also pertain to other games, such as MMORPGs (Massively Multiplayer Online Role-Playing Games), however those applications can arguably be classified as “softer” in regards to latency.2. Latency IssuesOne may argue that the latency problem isn't substantial when taking into account today's high-speed networks. Today's high-speed networks are indeed helpful, however, many people have slow or unreliable broadband connections [1]. Running on a local area network is not feasible for the architecture of the majority of multiplayer games. Because of this, users can expect to experience packet loss, slow connections, and out of order packets, all due to the connections from one end to the other. This may make the problem seem like a simple networking issue, but, as you will see, the issue has a more central role in creating the application itself. On a Local Area Network (LAN), latencies are generally under 10 milliseconds, however, when dealing with the Internet as a whole, latencies can range from 100 milliseconds to 500 milliseconds [2]. Goodconnections are generally around 50 milliseconds [2].As stated before, having latent clients has a different impact on the gameplay of different genres. In general, games that require split-second reaction time, such as combat simulation or first-person shooter games, have smaller tolerance for latency and missed deadlines than others.Figure 2.1: Latency Thresholds per Genre [2]Figure 2.1 is a table that lists the approximate latency thresholds for a few of the major classes of games [2]. This data was collected as part of game latency studies, which illustrated “the effects of latency on performance for player actions with various deadline and precision requirements” [2]. The studies measured performance for certain time-related actions in different game genres, such as accuracy in a shooter game, or time taken to complete a lap in a racing game [2]. The different models presented as part of the figure describe how a player is represented in-game. The “avatar” model describes a game in which a player has a certain character to represent him or her inside of the game. Avatar games may have different perspectives, usually first-person or third-person, which describe whether the camera view is looking from the character's eyes or from outside, looking at the character. The “omnipresent” model is a situation where the player has no visible character, but instead, for instance, an overhead view of the game area and directs other units to certain locations. As you can see, the example genres that you would expect to have high reaction requirements have lower latency thresholds, while those that are a bit slower paced can tolerate more lag-time.Figure 2.2: Latency-Performance Measures in Genres [2]The graph in Figure 2.2 describes the performance in each of the three previously introduced game types [2]. The gray area “is a visual indicator of player tolerances for latency,” and the areas below are generally unacceptable [2]. Of course, these tolerances vary depending on the game and the player, but this graph should give a general idea of the concept [2].Rather than attempting to compensate for this issue by improving the connection – which is out of the hands of the game-developers – we can use techniques to allow “the game to compensate for connection quality” [1]. Two common techniquesare client-side prediction and lag compensation [1]. Each of these techniques has its own drawbacks and “quirks,” but theycan assist in solving the overall problem of unacceptable lag for players. Note that these do not actually reduce the latency ofthe connections, but rather the perceived latency in the game for players.Client-Side PredictionClient-side prediction is a method that attempts to “perform the client's movement locally and just assume, temporarily, thatthe server will accept and acknowledge the client commands directly” [1]. As a game designer, you have to be able to let goof the idea that clients should be “dumb terminals,” and must build more of the actual game logic into the clients [1].However, the client isn't in full control of the simulation – there is still an “authoritative server” running to ensure clients arewithin certain bounds (for example: not instantly teleporting across the map when they have to walk) [1]. With thisauthoritative server, “even if the client simulates different results than the server, the server's results will eventually correctthe client's incorrect simulation” [1]. One potential problem with using this technique is that “this can cause a veryperceptible shift in the player's position due to the fixing up of the prediction error that occurred in the past” [1].To perform this prediction, the client stores a certain number of commands that have been entered by the user, and when thereis lag in the connection, the client uses the last command acknowledged by the server and attempts to simulate using the mostrecent data from the server [1]. In a popular multiplayer game called Half-Life, “minimizing discrepancies between client and server logic is accomplished by sharing the identical movement code” for clients and servers [1]. One issue with thismethod of latency reduction is that clients will likely end up running the same commands repeatedly until they areacknowledged by the server, and deciding when to handle sounds or visual effects based on these commands [1]. This is allfine and nice in attempting to predict one's own movement, but what about predicting the movement of others in the gameworld, so they don't seem to lag about?One of two major methods of determining the location of other objects in the game world is “extrapolation” [1].Extrapolation is performed on the client, and makes an attempt to simulate an object forward in time to predict the nextposition of an object [1]. Using this method, clients can reduce the effect of lag if the extrapolated object has a straight,predictable path. However, in most first-person shooter games, “player movements are not very ballistic, but instead are verynon-deterministic and subject to high jerk” [1]. This possible constant change in player movement makes it unrealistic toapply this method to this circumstance. In order to help fix the large error that can occur in extrapolation, the extrapolationtime can be reduced, effectively reducing how far in the future the object is predicted to be [1]. However, players must stilllead their targets, even with “instant-hit weapons,” because of the latency being experienced [1]. In addition, players mayhave an extremely difficult time hitting opponents that seem to be “'warping' to new spots because of extrapolation errors”[1].The second major method is “interpolation,” which “can be viewed as always moving objects somewhat in the past withrespect to the last valid position received for the object” [1]. In this method, you buffer data in the client, and display the dataafter a certain period of time [1]. This method will help with the visual smoothness of other objects in the game-world,however can make the interaction latency issue worse – the players are not actually being drawn as fast as data is received,but rather drawn, say, 100 milliseconds in the past [1].Lag CompensationAnother common technique for compensating for latent connections is “lag compensation.” Lag compensation can bethought of as “taking a step back in time, on the server, and looking at the state of the world at the exact instant that the userperformed some action” [1]. So, this technique doesn't perform client-side actions, but rather deals with the state of objectson the server. Note that we are completely moving the state of the object back in time, and not simply the location [1]. As aresult, players can run on their own systems without seeming to experience latency [1]. The game design must be modifiedto take this functionality into account; this technique requires servers to store a certain amount of historical data in order toperform the “step back in time”.This may seem like a great remedy for latency, however, like client-side prediction, it has its drawbacks. At times,“inconsistencies that sometimes occur ... are from the points of view of the players being fired upon” [1]. One example ofthese inconsistencies is when a “highly lagged player shoots at a less lagged player and scores a hit, it can appear that thelagged player has somehow 'shot around a corner'” [1]. This sort of issue is not usually as extreme in “normal combatsituations,” however it can still occur at times [1]. In order to attempt to fix this and make it fair, the server should mostlikely only accept commands from a reasonable period of time in the past, otherwise the majority of players could have anunacceptable experience due to a small amount of extremely lagged players.3. CheatingThe previously introduced techniques assist in handling latency-performance issues in multiplayer games, but may interfere with other aspects of the game. The big question here is “How much authority and information do I want to give the clients?” When dealing with “dumb terminals,” clients simply send the server messages for actions they wish to perform, and the server replies with the reaction.If client-side prediction is done, the issue of cheating seems to be removed, as clients have no authority over decisions that are made. However, cheaters could possibly still abuse the system. One such example would be what's known as a “time-cheat,” giving the cheater an unfair advantage by allowing him or her to “see into the future, giving the cheater additional time to react to the other players' moves” [3]. A cheater using this technique may be hard to detect by players of the game, as it may seem that that the player is simply lagging and has good luck [3]. An example would be a cheater who has low latency, and is receiving data on time, but reports that data has been received late. In this circumstance, the cheater is claiming he or she received data late, and may make decisions based on past data. For instance, the cheater could fire a weapon at the previous position of a player, report that he fired in the past, and score a hit. If a player is able to use past data like this, they could potentially perform flawlessly, ruining the fairness of the game!In order to deal with this, one may employ a few different solutions. One solution would be to simply place anti-cheat software on the client's system, and update your software as new cheats are found. This solution can be an annoyance for players, as an extra, intrusive piece of software is generally frowned upon by gamers. In addition, this solution depends on cheats to occur in the wild where they can be analyzed to be fixed, and only after the cheat has become rampant. This method may be effective enough for some applications, however, may be unacceptable for others. Instead, the communication protocol can be modified to prevent certain kinds of time-cheats, using a protocol like the “sliding pipeline protocol” [3]. With this protocol, whose details are described in [3], it is guaranteed that “no cheater sees moves for a frame to which it has not yet committed a move and ... that no cheater may continually decide on a move with more recent information than a fair player had” [3]. In general, the game designer must take into account the fact that there will be players attempting to cheat in this way, and can adjust, on the fly, the amount of time the server will “look into the past” based on the latency of all users [3].As expected, issues can also occur when clients are running their own simulations of the game-world. When clients simulate the world they may be given more information than a client is normally allowed to see. For example, if a wall is in front of a player, that player usually cannot see what is on the other side, and so will not be informed of it. A common cheat would be to abuse this system to enable the player to see the locations of other players or objects – to see through walls. One of the only ways to prevent cheating in this instance is to install anti-cheat programs (such as Valve Anti-Cheat) that attempt to detect known cheats.When running simulations, clients must also be kept in check to prevent impossible or unfair actions. As noted before, there must be an authoritative server that checks on the actions of each client. A simple instance of this would be when a cheating client claims they have raced six laps around a race track, when in reality the race had just started. The client would report this, and the server would have to verify that the client's position had moved a valid amount, or else it should reject the claim made by the client. Without proper checking by the authoritative server, clients can get away with performing impossible feats.All in all, the latency issue must be dealt with while keeping the possibility of cheaters in mind – unless, of course, you don't care about cheaters!4. ConclusionsLatency issues in games are still very real today, even if the majority of players have high-speed connections. The trick in dealing with these issues lies in determining what type of technique to use for a specific system. Each of the techniques presented in this paper have their own quirks and downfalls, and each is very different in implementation. As each technique is deeply rooted in the functionality of the client and/or the server, the team must decide what combination of methods will be used during design. In addition to dealing with the latency issue, the team may or may not decide to take into account how cheaters will attempt to abuse the system – each method of latency reduction may introduce different possibilities for cheating. Again, the idea isn't to reduce the actual lag-time between client and server, but make “users find [the game's] performance acceptable in terms of the perceptual effect of its inevitable inconsistencies” [4]. Ultimately, the goal of the game designers when dealing with latency should be to make the game playable as well as fair.5. References[1]Bernier, Yahn, Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization, Valve,[Cited 2007, October 4], Available HTTP: http://www.resourcecode.de/stuff/clientsideprediction.pdf.[2]Claypool, Mark, Claypool, Kajal, On Latency and Player Actions in Online Games, July 8, 2006, [Cited 2007,October 4], Available HTTP: ftp:///pub/techreports/pdf/06-13.pdf.[3]Cronin, Eric, Filstrup, Burton, Jamin, Sugih, Cheat-Proofing Dead Reckoned Multiplayer Games (ExtendedAbstract), University of Michigan, [Cited 2007, October 4], Available HTTP:/games/papers/adcog03-cheat.pdf.[4]Brun, Jeremy, Safaei, Farzad, Bousted, Paul, Managing Latency and Fairness in Networked Games, [Cited 2007,October 4], Available HTTP: /ft_gateway.cfm?id=1167861&type=pdf.。

Mobile gaming has become an integral part of modern entertainment,offering a wide array of options for players of all ages and interests.Here are some key aspects to consider when discussing mobile games in an English composition:1.Accessibility:Mobile games can be played on a variety of devices,from smartphones to tablets,making them accessible to a broad audience.This accessibility has contributed to the rapid growth of the mobile gaming industry.2.Variety of Genres:The range of genres available in mobile games is vast,including action,adventure,puzzle,strategy,simulation,sports,and more.This diversity caters to different tastes and preferences,ensuring that there is something for everyone.3.Portability:One of the most significant advantages of mobile games is their portability. Players can enjoy games on the go,whether they are commuting,waiting in line,or simply relaxing at home.4.Social Interaction:Many mobile games incorporate social features,allowing players to connect with friends,share achievements,and even compete against one another.This social aspect enhances the gaming experience and fosters a sense of community.5.FreetoPlay Model:A significant number of mobile games are free to download and play,with inapp purchases available for additional content or features.This model has made gaming more accessible to people who may not be willing to pay upfront for a game.6.Monetization:Mobile games often rely on advertising and inapp purchases for revenue. This can sometimes lead to concerns about the balance between gameplay and monetization strategies,with some players feeling that certain games are overly focused on generating income.7.Impact on Mental Health:The addictive nature of some mobile games has raised concerns about their impact on mental health,particularly among younger players.It is important to promote responsible gaming habits and encourage breaks and limits on screen time.8.Technological Advancements:As mobile technology continues to evolve,so too do the capabilities of mobile games.Highquality graphics,complex gameplay mechanics,and immersive storytelling are now possible on mobile devices,rivaling the experiences traditionally found on consoles and PCs.cational Value:Some mobile games are designed with educational content in mind, helping players to learn new skills or information in a fun and interactive way.These games can be a valuable tool for learning outside of traditional educational settings.10.Cultural Impact:Mobile games have also had a significant cultural impact,with some titles becoming global phenomena and influencing popular culture,music,and even fashion.When writing an essay on mobile games,its essential to explore these aspects and consider the broader implications of mobile gaming on society,technology,and individual lives.Whether youre discussing the positive aspects of mobile gaming or addressing the potential downsides,a wellrounded essay will provide a comprehensive view of this dynamic industry.。

Internet Gambling: Preliminary Results of the First U.K. Prevalence StudyMark Griffiths, PhDPsychology Division, Nottingham Trent University, Nottingham, United Kingdom, E-mail: mark.griffiths@Abstract:Technology has always played a role in the development of gambling practices, and new technologies such as Internet gambling may provide many people with their first exposure to the world of gambling. Further to this, Internet gambling could be argued to be more psychologically enticing than previous non-technological incarnations of gambling because of anonymity, accessibility and interactivity. This paper reports on the results of the first U.K. study of Internet gambling; 2098 people were interviewed for their behaviour and attitudes. Results indicated that only 1% of Internet users (n=495) had ever gambled on the Internet and that there was no evidence of problematic gambling behaviour associated with the Internet.Introduction:What seems clear is that the field of gambling is not immune to the technological revolution taking place in other fields. Griffiths (1996a, 1999) has argued that these new technologies (e.g., Internet gambling, telephone wagering, interactive television, etc.) may provide many people with their first exposure to the world of gambling and be more psychologically enticing than previous non-technological incarnations. Further to this, it has been alleged that social pathologies are beginning to surface in cyberspace, i.e. “technological addictions” (e.g., Griffiths, 1995a, 1996b, 1996c). Technological addictions can be viewed as a subset of behavioural addictions (see Marks, 1990) and feature all the core components of addiction (e.g., salience, mood modification, tolerance, withdrawal, conflict and relapse, see Griffiths, 1995a, 1995b, 1996b, 1998). Given these assertions, Internet gambling is an issue of potential social and psychological concern.Internet gambling:No-one is really sure how the Internet will develop over the next five to 10 years, but Internet gambling as a commercial activity has the potential for large financial rewards for its operators. The success of Internet gambling depends on many factors including diversity, accessibility and advertising. Internet gambling is provided by a network of networks that span geographical borders and are not discrete. Internet gambling is therefore global, accessible and available 24 hours a day.The growth of the Internet raises interesting questions. Perhaps one way to think of this growth isto see the Internet as providing a medium for other addictions (e.g., gambling, computer game playing, etc.). It has been argued (Griffiths, 1996a, 1998) that the Internet could easily be a medium for obsessive and/or compulsive behaviours such as gambling. Some observers (e.g., O'Neill, 1998) have argued that Internet gambling provides “a natural fit for compulsive gamblers.” Griffiths (1999) also raises the following issues:•Underage gambling. How can you be sure that adolescents are not accessing Internet gambling by using a parent's credit card?•Problem gambling. How can you stop problem gamblers from gambling?•Gambling while intoxicated. How can you be sure that a person under the influence of alcohol or other drugs does not have access to Internet gambling?•Internet gambling in the workplace. How can you be sure that a person is not wasting time at work gambling on the Internet?•Electronic cash. How can a person with a credit card be prevented from spending more than they intended? It is very likely that the psychological value of electronic cash will be less than “real” cash (and similar to the use of chips or tokens in other gambling situations). This may lead to some kind of “suspension of judgment.”•Hours of operation. How can you prevent a person from playing all day? The Internet never closes, so it is theoretically possible to gamble all day, every day.Internet gambling is a new phenomenon and to date no research on prevalence has been published. This study, therefore, provides the results of the first U.K. survey of Internet gambling, examining both behaviour and attitudes.Method:A total of 2098 people (918 male and 1180 female) were interviewed across 167 different sampling points by MORI, a market research company. (MORI was founded in 1969 and is the largest independent research service agency in the United Kingdom.) People were interviewed face-to-face in their homes, and the interviewers used computer-assisted techniques. The data were weighted in order to represent the entire U.K. population. Of the 2098 participants, 495 (24%) were Internet users.Results S ection:Attitudes toward gambling:Participants were asked a number of questions about their attitudes toward gambling in general. Gambling was defined as “risking money for a future reward on a particular activity,” such as horse race betting, slot machine gambling, etc. Fifty-one per cent thought gambling was generally addictive, 20% described it as an unhealthy activity, 22% said it was a dangerous activity and 56% thought it was a waste of money.Attitudes toward Internet gamblingParticipants were also asked a number of questions about their attitudes toward Internetgambling compared to non-Internet gambling. Eight per cent thought Internet gambling was more addictive, 5% said it was more unhealthy, 9% claimed it was more dangerous, 13% said it was less regulated and 21% claimed it was more likely to attract children.Gambling on the Internet:Participants who were also Internet users (n=495) were asked about their actual Internet gambling behaviour. The results showed that no-one gambled regularly (i.e. once a week or more) on the Internet and that only 1% were occasional Internet gamblers (i.e. less than once a week). Results also showed that a further 4% had never gambled but would like to do so, whereas the remaining 95% had never gambled on the Internet and said they were unlikely to do so.Teenage Internet gambling:Participants who were between 15 and 19 years old (n=119) were also asked if they had ever gambled on the Internet, and if they had, whether they had used a parent's credit card. No-one in the sample had done either, although 4% said they would like to gamble on the 'Net.Female Internet gambling:Female participants (n=1180) were also asked about their attitudes toward gambling online as compared to gambling in a betting shop. Of those surveyed, 73% said they would never gamble on the Internet. However, 2% reported that they would rather gamble on the Internet because it's safer, 9% said it's less intimidating, 9% claimed it's more anonymous, 2% said it's more fun and 13% claimed it was more tempting.Conclusions:The results of this first U.K. survey of Internet gambling behaviour and attitudes are interesting but not that surprising given the relatively low use of the Internet in the U.K. (Traditionally, in the U.K. most people have to pay by the minute for Internet access, which most likely inhibits use.) Interestingly, general attitudes toward gambling were quite negative (i.e. people thought it was addictive, unhealthy, etc.), whereas attitudes toward Internet gambling appeared quite positive. However, this may be due to inexperience and/or ignorance of the issues involved. For instance, only 13% of the sample thought Internet gambling was less regulated than other forms of gambling. This is clearly not the case as there is little legislation in the U.K. concerning Internet gambling.Although there has been speculation that Internet gambling is addictive, there is no evidence from this study. Although a problem gambling screen was not administered, the fact that no-one in the study was a regular gambler suggests that there were few problems (if any) among this particular population. However, as the number of online users in the U.K. increases, the potential for problem gambling will increase. This study should therefore be viewed in the context that it was carried out at a time when Internet use was limited in the U.K. The U.K. has a higher prevalence of Internet use than France or Germany, but its rate is much lower than the U.S. and many Scandinavian countries (Snoddy, 2001).This survey also highlights a small minority of women who think that Internet gambling may be a more positive experience than visiting the male-dominated environment of the bookmaker. These women claimed the Internet was not intimidating, but was safer and more fun. Internet gambling may therefore (in the future) provide a safe forum for women wanting to gamble — at least from a perceived point of view.Since many teenagers now have access to the Internet either at home or at school, there has been a pressing concern that children and adolescents will take up gambling on the Internet. This perception was partly shared by participants; one in five of those surveyed felt that Internet gambling would be more attractive to teenagers. Having said that, no teenagers in this study gambled on the Internet. However, one in 20 teenagers interviewed found the prospect of using their parent's credit card to gamble tempting.Internet gambling is at the cutting edge of future entertainment and is an issue that must be grasped by many people (legislators, social policy analysts, psychologists, sociologists, etc.), as the number of sites and users will rise dramatically over the next decade. Gambling online, which is currently a minor activity, may be tempting because of the anonymity and accessibility of the Internet. It therefore has the potential to become a social problem in the near future, unless guidelines and legislation are introduced. It has also been speculated (Griffiths, 1993, 1995c) that structural characteristics of future software programs might promote addictive tendencies. Structural characteristics (i.e. features which manufacturers design into their products) promote interactivity and to some extent define alternative realities to the user, allowing them feelings of anonymity. These features may be very psychologically rewarding to individuals with these tendencies. There is little doubt that Internet use among the general population will increase over the next few years, and if social pathologies exist, then there is a need for further research.References:Griffiths, M.D. (1993). Fruit machine gambling: The importance of structural characteristics. Journal of Gambling Studies, 9, 133-152.Griffiths, M.D. (1995a). Technological addictions. Clinical Psychology Forum, 76, 14-19. Griffiths, M.D. (1995b). Netties Anonymous. Times Higher Educational Supplement, April 7, p. 18. Griffiths, M.D. (1995c). Adolescent Gambling. London: Routledge.Griffiths, M.D. (1996a). Gambling on the Internet: A brief note. Journal of Gambling Studies, 12, 471-474. [CrossRef]Griffiths, M.D. (1996b). Internet addiction: An issue for clinical psychology? Clinical Psychology Forum, 97, 32-36.Griffiths, M.D. (1996c). Behaviourial addictions: An issue for everybody? Employee Counselling Today, 8(3), 19-25.Griffiths, M.D. (1998). Internet addiction: Does it really exist? In J.Gackenbach (Ed.), Psychology and the Internet: Intrapersonal, Interpersonal and Transpersonal Applications (pp. 61–75). New York: Academic Press.Griffiths, M.D. (1999). Gambling technologies: Prospects for problem gambling. Journal of Gambling Studies, 15, 265-283. [CrossRef]Marks, I. (1990). Non-chemical (behaviourial) addictions. British Journal of Addiction, 85, 1389-1394. [CrossRef]O'Neill, K. (1998, June). Internet gambling. Paper presented at the 13th National Council on Problem Gambling Conference, Las Vegas, USA.。

A hidden Markov model for the detection of pure andmixed strategy play in games∗Jason Shachat†J.Todd Swarthout‡Lijia Wei§July7,2012AbstractWe propose a statistical model to assess whether individuals strategically use mixed strategies in repeated games.We formulate a hidden Markov model in which the latentstate space contains both pure and mixed strategies,and allows switching between thesestates.We apply the model to data from an experiment in which human subjectsrepeatedly play a normal form game against a computer that always follows its part ofthe unique mixed strategy Nash equilibrium profile.Estimated results show significantmixed strategy play and non-stationary dynamics.We also explore the ability of themodel to forecast action choice.JEL classification:C92;C72;C10Keywords:Mixed Strategy;Nash Equilibrium;Experiment;Hidden Markov Model ∗This paper supersedes the previous working paper,“Man versus Nash:An experiment on the self enforcing nature of mixed strategy equilibrium.”†Wang Yanan Institute for Studies in Economics and MOE Key Laboratory in Econometrics,Xiamen University.jason.shachat@‡Department of Economics and Experimental Economics Center,Georgia State University. swarthout@§Wang Yanan Institute for Studies in Economics and MOE Key Laboratory in Econometrics,Xiamen University.ljwie.wise@1IntroductionGame theory and the Nash equilibrium solution concept are a key framework in the social sciences for modeling interactive behavior.The formulation of a normal form game consists of a set of players,a set of possible actions for each player,and a payofffunction for each player that gives a real-valued payofffor any possible joint action profile–a list of actions consisting of one for each player.A Nash equilibrium is a joint action profile such that each player’s assigned action results in at least as high a payoffto the player as any other possible action,assuming all other players choose their respective actions in the Nash equilibrium profile.If players are restricted to deterministically choose an action,then there are many games that don’t have a Nash equilibrium,such as the childhood game of Rock,Scissors, Paper.Confronted with this problem,Von Neumann(1928)generalized a player’s decision from choosing an action to choosing a probability distribution over his possible actions.1This choice of a probability distribution is called a“mixed”strategy,and a degenerate mixed strategy which chooses a particular action with probability one is called a“pure”strategy. The introduction of mixed strategies allows for existence of equilibrium across a broad class of games:from minimax solutions for zero-sum games(Von Neumann,1928;Von Neumann and Morgenstern,1944)to noncooperative equilibria for n-person games(Nash,1951).While the role of mixed strategies in defining logically consistent solution concepts is not in doubt, the positive aspect of individuals actually playing mixed strategies is an open question of considerable interest.Researchers’efforts to answer this question have naturally focused on settings where the use of mixed strategies is most compelling:the repeated play of games which have a unique mixed strategy Nash equilibrium.The value of“being unpredictable”is readily seen in examples such as serves in tennis,“bluffing”in poker,and whether or not a tax authority audits a tax payer.A common approach in this literature is to test whether the players’action choices are consistent with the mixed strategy equilibrium.Some studies using controlled experiments with human subjects have the advantage of knowing the payofffunctions,and test whether choice frequencies agree with the equilibrium strategies and whether players’sequences of actions are serially independent(O’Neill,1987;Binmore,Swierzbinski,and Proulx,2001; Morgan and Sefton,2002;Selten and Chmura,2008).Other studies consider high-level sports competitions,such as soccer(Chiappori,Levitt,and Groseclose,2002;Palacios-Huerta,2003; Bareli,Azar,Ritov,Keidarlevin,and Schein,2007)and tennis(Walker and Wooders,2001), with the advantage of studying highly experienced players competing for high stakes and 1Along with generalizing the set of feasible actions to the set of mixed strategies,a player’s payofffunction is extended by setting its value to the expected payoffgiven a profile of mixed strategies,commonly referred to as the expected utility property.the disadvantage of unknown payofffunctions.2These studies focus on testing the serial independence of action choice and the equilibrium implication of equal payoffs across action choices.Some of the most prominent and recurring results for both types of studies are that aggregated action frequencies across players agree with the equilibrium mixed strategies but individual action frequencies do not,and for many individuals action choices are serially correlated violating the independence prediction.To reconcile these issues of serial correlation and heterogeneity,several studies(Ochs,1995; Bloomfield,1994;Shachat,2002;Noussair and Willinger,2011)conduct laboratory experi-ments using the same type of games but directly elicit mixed strategies by obligating players to select a probability distribution over actions.3Elicited strategies in these experiments ex-hibit various distinct patterns.Some subjects choose pure strategies almost exclusively,some choose strictly mixed strategies almost exclusively,and others use both types of strategies–usually in long sequences.Also,certain mixed strategies are often quite focal,such as choosing equal probability weight on a subset of actions rather than the Nash equilibrium proportions. Naive interpretation of these results suggests a clear distinction between play that is purposely unpredictable and play that is a pure best response to changing forecasts of an opponent’s action(Nyarko and Schotter,2002).A more cautious interpretation is that subjects may es-chew the randomizing device provided by the experimenter and instead internally randomize, or perhaps subjects choose strictly mixed strategies due to the experimenter effect of the novel elicitation method.Clearly a less invasive method to detect mixed strategy play would be valuable.In this study we propose a hidden Markov model(HMM)to detect whether observed action choices are the result of pure or mixed strategies play in repeated two-personfinite action games.4There are three key ideas in our formulation:(1)we treat the strategy a player follows as a latent state and the action played as the observable output from the latent strategy;(2) the set of possible latent states is a discrete subset of all possible mixed strategies containing pure strategies,Nash equilibrium or minimax strategies,and focal mixed strategies;and(3) a player switches the latent strategy he follows according to afirst order Markov process. We then demonstrate the ability of the model by applying it to a new experimental data set we collect.In our experiment,each human subject repeatedly plays a2×2game against a computer player that follows its mixed strategy equilibrium.Some subjects play a zero-2The action sets are typically comprised of simple actions,e.g.,{serve left,serve right}and{defend left, defend right}.The payoffs are assumed to be the probability of winning the task and these probabilities will differ based upon both the comparative skills between players and the relative strengths a player has for each action.3For example,Shachat(2002)adopts a game with four actions,each identified by a different color,for each player.Each player mustfill a box with100cards in any combination of the four colored card types,and then one card is selected at random to determine the action played.4See Rabiner(1989)for a classic introduction to hidden Markov models.sum game and others an unprofitable game.5The estimated HMMs reveal several interesting results,including:(1)significant amounts of both pure and mixed strategy play;(2)the focal equiprobable mixed strategy is played more often than the Nash equilibrium strategy;(3)low transition probabilities between mixed and pure latent strategies;(4)dynamic adjustments in the types of strategies players follow over time;and(5)appreciable rates of both mixed and pure strategy play in the limiting distributions of the HMMs(interpreted as the long run equilibrium of play).We then extend the HMM from a statistical framework for evaluating hypotheses to one for forecasting action choice and assess its predictive accuracy.2A HMM of switching strategiesConsider an experiment in which we observe M pairs of subjects,each playing T periods of the same2×2normal form game.Often games like this are described by a two-by-two table,and for familiarity purposes we denote one subject’s player role as Row and the other as Column. We label each player role’s two possible actions Left(L)and Right(R),and express a subject’s mixed strategy as the probability of playing L.Of particular interest is when the game has a single Nash equilibrium and it is in strictly mixed strategies,although our framework is not restricted to study only such cases.Three factors confounding the analysis data generated by this type of process are the latency of players’mixed strategies,the heterogeneity of strategy adoption across subjects,and variation of adopted latent strategies over the course of repeated play.In this section,we present a model that accommodates and allows estimation of these confounds.Consider the following HMM for afixed player role.The state space S is an n-element subset of the subject i’s possible mixed strategies.Denote s i,t∈S for the strategy used by subject i in period t,S i is the set of all possible T element sequences of mixed strategies for i with typical element s i,and let s be the collection of s i for all M subjects in a given player role.Let y i,t denote subject i’s realized action in period t,y i is the corresponding T element sequence of i’s observable actions,and y is the collection of y i for all M subjects.View{y,s} as the output of the HMM.The probability structure of the HMM has three elements.First,the n-element vector B for which the element B j is the probability a subject chooses action Left,i.e.the mixed strategy,if he is in state j.We will provide two analyses which differ in how we specify B.In one approach we consider B as known a priori,and S and B are redundant ually, in this approach,B contains the two pure strategies,other strategies suggested by theory such 5An unprofitable game is one in which the minimax and Nash equilibrium solutions are distinct but yield the same expected payofffor each player.as Nash equilibrium or minimax,and other focal strategies.In the second approach we treat the elements of B as unknown parameters–the state dependent mixed strategies.The second element of the structure,π,is the initial multinomial probability distribution over S.The third element,P,is the n×n transition probability matrix.The element P jk is the probability a subject adopts strategy k in period t conditional upon having adopted strategy j in period t−1.The likelihood function of(B,π,P)isL(B,π,P|y,s)=Pr(y,s|B,π,P).Rewriting this likelihood in terms of the marginal distributions of y and s gives usL(B,π,P|y,s)=Pr(y|s,B,π,P)·Pr(s|B,π,P).Next,we assume that the marginal distribution of y conditional on s is independent ofπand P.In other words,once the state is realized then the probability of a Left action relies solely on the mixed strategy of the current state.Also,by the specification of the HMM,s is independent of the state dependent mixed strategies B.This allows us to restate the previous likelihood function asL(B,π,P|y,s)=Pr(y|s,B)·Pr(s|π,P).Since the sequence of states for each subject is unobservable,we evaluate the likelihood by integrating over the set of all possible sequencesL(B,π,P|y,s)=M i=1s∈Sπ(s i,1)B I y i,1s i,1(1−B si,1)1−I y i,1Tt=2P si,t−1,s i,tB I y i,ts i,t(1−B si,t)1−I y i,t ,where I y i,t is an indicator function which equals one for the action Left and zero for the action Right.As T grows,the number of calculations needed to evaluate this likelihood quickly becomes computationally impractical.We describe the Bayesian approach we take to estimate the HMM,although one could proceed down a frequentist path of maximizing the expected likelihood function using some variation of the EM(expected maximum likelihood) algorithm.In the Bayesian analysis,wefirst factor the joint posterior distribution of the unknown HMM parameters and unobserved states s into the product of marginal conditional posterior distributions.Then we evaluate these marginal conditional posteriors through an iterative sampling procedure called the Markov Chain Monte Carlo(MCMC)method.MCMC is asimple but powerful procedure in which the empirical distributions of the sampled parameters converge to the true posterior distributions.After convergence,iterative sampling is continued to construct empirical density functions.These are used to make inferences regarding the parameters of the hidden Markov models.Consider the posterior density function on the realized unobserved states and HMM pa-rameters h(s,B,P,π|y).First,express this joint density as the product of the marginal density of HMM parameters conditional on the observed action choices and unobserved states with the marginal density of the states conditional upon action choicesh(s,B,P,π|y)=h(B,P,π|s,y)h(s|y).We have already assumed that the transition matrix P and initial probabilities over statesπare independent of the action choices and state contingent mixed strategies B,which allows us to stateh(s,B,P,π|y)=h(B|s,y)h(P,π|s,y)h(s|y).This product of three conditional posteriors permits a simple Markov Chain procedure of sequentially sampling from these distributions.We start with some initial arbitrary values for the HMM parameters,(B(l),P(l),π(l))where l=0.We create s(0)by simulation using P(0)and π(0)without conditioning on y.From these initial parameter values and the observed action sequences y,we use a Gibbs sampling algorithm to generate an initial sample of state sequences s(1).Then we make a random draw P(1)from the posterior distribution of P conditional on s(1)and y,and proceed similarly to make a random draw ofπ(1).We complete the iteration by making a random draw B(1)from the posterior of B conditional on s(1)and y.The key to the MCMC method is that as l→∞,the joint and marginal distributions of B(l),P(l), andπ(l)converge weakly to the joint and marginal posterior distributions of these parameters (Geman and Geman,1987).We now describe the details of each step in an iteration of the MCMC procedure.Step1:Sampling the state sequences s(l)We begin by describing a Gibbs sampling technique for generating draws from the distribu-tion of s(l)conditional upon y and(B(l−1),P(l−1),π(l−1)).The elements of s i can be drawn sequentially for each t conditioning on the observed action choice y i,t,the realized state in other periods,π,and P.Let s i,=t be the vector obtained by removing s i,t from the sequence s i.Given s i,=t,we express the conditional posterior distribution of s i,t asPr(s(l)i,t |y i,t,B(l−1),P(l−1),s(l)i,=t,s(l−1)i,=t)∝Pr(y i,t|s(l)i,t,B(l−1))·Pr(s(l)i,t|P(l−1),s(l)i,=t,s(l−1)i,=t)Pr(s(l)i,t |P(l−1),s(l)i,=t,s(l−1)i,=t)=Pr(s i,t=k|P(l),s(l)i,t−1,s(l−1)i,t+1).Consequently,the conditional posterior probability of s i,t=k and t>1isPr(s(l)i,t =k|·)=Pr(y i,t|s i,t=k,B(l−1)k)·Pr(s i,t=k|P(l−1),s(l)i,t−1,s(l−1)i,t+1) nj=1Pr(y i,t|s i,t=j,B(l−1)j)·Pr(s i,t=j|P(l−1),s(l)i,t−1,s(l−1)i,t+1),and for t=1Pr(s(l)i,1=k|·)=Pr(y i,1|s i,1=k,B(l−1)k)·Pr(s i,1=k|π(l−1),s(l−1)i,2) nj=1Pr(y i,1|s i,1=j,B(l−1)j)·Pr(s i,1=j|π(l−1),s(l−1)i,2).The state s(l)i,tis determined by making a random draw from the uniform distribution on theunit interval,and comparing this draw to the calculated conditional probability of s(l)i,t. Step2:Sampling the transition matrix P(l)andπ(l)The posterior distributions of P jk andπdepend only upon s(l)and the priors.We specify the prior ofπas a Dirichlet distribution h(π;α1,...,αn)whereαj=1,for1≤j≤n.Similarly, we specify the prior of the j th row of P as a Dirichlet distribution h(p j1,...,p jn|ηj1,...,ηjn). In an experiment,we record the data from the true start of the HMM process,so we assume that the joint posterior is simply the product of these two marginal posteriors.The respective posteriors ofπ(l)and P(l)areh(π|s)∝Pr(s|π)h(π;α1,...,αn),andh(P j1,...,P jn|s)∝Pr(s|P j1,...,P jn)h(P j1,...,P jn;ηj1,...,ηjn).Ifν0j is the number incidences of s(l)i,1=j in s(l),andνjk is the count of transitions from state j to k in s(l),then the conditional probabilities in the two posterior calculations are multinomial distributionsh(π|s)∝πν011...πν0n−1n−1·1−n−1k=1πkν0nh(π;α1,...,αn)h(P j1,...,P jn|s)∝Pνj1j1...Pνjn−1jn−1·1−n−1k=1P jkνjnh(P j1,...,P jn;η1,...,ηn).Since the Dirichlet distribution is the conjugate prior for the multinomial distribution,these posterior distributions are also Dirichlet distributions for which each shape parameter is the sum of its prior value and the respective counth(π|s)=h(π;α1+ν01,...,αn+ν0n)andh(P j1,...,P jn|s)=h(P j1,...,P jn;η1+νj1,...,ηn+νjn).Hence,we selectπ(l)and P(l)be taking random draws from these distributions.Step3:Sampling the state dependent mixed strategies BFor our initial approach to modeling the state dependent mixed strategies,we assume B corresponds to a known subset of S.In our Bayesian analysis this is equivalent to assuming a point prior on these strategies,and therefore there is no updating.So in our Gibbs sampling procedure we skip this step,and proceed to next iteration of the Gibbs sampler.Of course this is a rather strong prior to assume,and we should evaluate whether it is appropriate. Accordingly,we conduct an auxiliary analysis in which we assume a uniform prior of the set of all mixed strategies.In the auxiliary analysis we proceed as follows.The priors of state dependent mixed strate-gies B1,...,B n are assumed independent of each other and of the Markov process governing the states.Given these assumptions,we can think of each B j as a Bernoulli probability, and each Left(Right)action as a success(failure)when occurring in state j.The likelihood function is calculated as a binomial trial.Since it is the conjugate prior of the binomial,we assume the prior is a Beta distribution,denotedβ(B j;ζj;γj).We want a uniform prior as well,and that corresponds to setting the shape parametersζj andγj to one.The posterior distribution is simplyh(B j|y,s(l))=β(B j;ζj+κL,j,γj+κR,j),whereκL,j andκR,j are the number of times the actions Left and Right,respectively,are chosen when in state j according to s(l).The state conditional mixed strategies B(l)j,j=1,...,n, are randomly drawn from these Beta posterior distributions,completing an iteration of theGibbs sampler.The Gibbs sampler is run for a large number of iterations until the empirical distribution of all the parameters has converged(Geweke,1991).Then the sampling procedure is allowed to continue to run for another number of iterations to build up an empirical distribution that corresponds to the posterior distribution of the HMM parameters.It is from this empirical distribution that we conduct statistical inferences.3The experimentWe apply our HMM framework to a new experimental data set that provides a likely setting for mixed strategies,and particulary Nash equilibrium strategies,to be adopted.Additionally, our procedures allow us to estimate for one player role without the need to also simultaneously model the opposing role,because each human subject repeatedly plays against a computer player that follows its mixed strategy equilibrium.Each subject is informed that his opponent is a computer but is given no information regarding the computer’s strategy.We adopt two different games in our experimental design,with each subject playing only one of the two games.One game is zero-sum and the other game is unprofitable.3.1The gamesOurfirst game is a zero-sum asymmetric matching pennies game introduced by Rosenthal, Shachat,and Walker(2003).The normal form representation of this game is presented on the left side of Figure1.The game is called Pursue-Evade because the Row player“captures”points from the Column player when the actions of the two players match,and the Column player“evades”a loss when the players’actions differ.In the game each player can move either Left or Right,and the game has a unique Nash equilibrium in which each player chooses Left with probability two-thirds.In equilibrium,Row’s expected payoffis two-thirds, and correspondingly Column’s expected payoffis negative two-thirds.Our second game is an unprofitable game introduced by Shachat and Swarthout(2004) called Gamble-Safe.Each player has a Gamble action(Left for each player)which yields a payoffof either two or zero,and a Safe action(Right for each player)which guarantees a payoffof one.The normal form representation of this game is presented on the right side of Figure1.The Gamble-Safe game has a unique Nash equilibrium in which each player chooses the Left action with probability one-half,and each player earns an expected equilibrium payoffof one.Right is the minimax strategy for both players with a guaranteed payoffof one.Aumann(1985)argues that the Nash equilibrium prediction is not plausible in such an unprofitable game because its adoption assumes unnecessary risk to achieve the correspondingPursue-Evade Game Gamble-Safe Game Column Player Left RightR o w P l a y e r Left 1 , -1 0 , 0 Right 0 , 0 2 , -2Column PlayerLeft Right R o w P l a y e r Left 2 , 0 0 , 1Right 1 , 2 1 , 1 Figure 1:The experimental gamesNash equilibrium payoff.For example,imagine Row has Nash equilibrium beliefs and best responds by playing the Nash strategy.Row’s expected payoffis one.However,suppose Column instead adopts his minimax strategy Right.This reduces Row’s expected payoffto one-half.Row could avoid this risk by simply playing the minimax strategy.This aspect makes the Gamble-Safe game a more challenging test for the hypothesis of mixed strategy play than the zero-sum Pursue-Evade game.3.2Subject recruitment and experiment protocolWe conducted six experiment sessions in the Finance and Economics Experimental Laboratory (FEEL)at Xiamen University during December 2011.A total of 110undergraduate and masters students participated in the experiment,with each session containing between 12and 22subjects.54subjects were assigned to the Persue-Evade game treatment,and 56subjects were assigned to the Gamble-Safe game treatment.Subjects were evenly divided into Row and Column player roles within each treatment.FEEL uses the ORSEE online recruitment system for subject recruitment (Greiner,2004),and at the time of the experiment approximately 1400students were in the subject pool.A subset of students from the subject pool were invited to attend each specific session,and these students were informed that they would receive a 10Yuan show-up payment and have the opportunity to earn more money during the experiment.Further,the invitation stated that the session would last no more than two hours.Upon arrival at the laboratory,each subject was seated at a computer workstation such that no subject could observe another subject’s screen.Subjects first read instructions de-tailing how to enter decisions and how earnings were determined.6Then,200repetitions of the game were played.For the Pursue-Evade game,Column subjects were initially endowed with a balance of 260tokens each,and Row subjects none.Each token was worth one-third6The instructions are available at /swarthout/HMM/of a Yuan.Each subject’s total earnings consisted of the10Yuan show-up payment plus the monetary value of his token balance after the200th repetition.While a mathematical possibility,no Column subjects in the Pursue-Evade game went bankrupt.The experiment was conducted with a Java software application created at the Georgia State University Experimental Economics Center(E x CEN)that allows humans to play normal form games against computerized algorithms.At the beginning of each repetition,each subject saw a graphical representation of the game on the screen.Each Column subject’s game display was transformed so that he appeared to be a Row player.Thus,each subject selected an action by clicking on a row,and then confirmed his choice.After the repetition was complete,each subject saw the outcome highlighted on the game display,as well as a text message stating both players’actions and his own earnings for that repetition.Finally,each subject’s current token balance and a history of past play were displayed at all times.The history consisted of an ordered list with each row displaying the repetition number,the actions selected by both players,and the subject’s payofffrom the specific repetition.3.3Data summaryWe begin the summary of the experimental data by providing views of the joint distribution of the proportion of Left play for each subject-computer pair,while conditioning on whether the data are from thefirst100or last100repetitions.Figures2and3present these views for the Pursue-Evade and Gamble-Safe treatments,respectively.In each of thesefigures,the x-axis is the proportion of Left play for the Column player and the y-axis is the proportion of Left play for the Row player.Each arrow in thefigures represents the play of a single human-computer pair,with the arrow tail representing the joint frequency of Left play in the first100repetitions and the arrow head representing the joint frequency of Left play in the final100repetitions.These arrows show the adjustments subjects make from thefirst half to the second half of play.We see that many arrows suggest substantial change in the human player frequency,but the changes do not trend in any one direction or uniformly towards the Nash equilibrium.Human play also displays greater dispersion and displacement from the Nash equilibrium than the computer opponents,suggesting nonconformity with the Nash equilibrium predictions.Table1presents the means and standard deviations of subjects’frequencies of Left play by treatment and role.Recall that we have2700observations for the each role in the Pursue-Evade treatment and2800observations for each role in the Gamble-Safe treatment.Although the Row player mean is close to the Nash equilibrium proportion in both game treatments,the Nash equilibrium proportion is rejected for all four cases at any reasonable level of significance. In each of the four cases,subjects’proportions of Left play display too much variance to haveHuman Row vs.NE ColumnNE Row vs.Human ColumnComputer Column Proportion LeftH u m a n R o w P r o p o r t i o n L e f t0.00.20.40.60.81.00.00.20.40.60.81.0C o m p u t e r R o w P r o p o r t i o n L e f t0.00.20.40.60.81.00.00.20.40.60.81.0Computer Column Proportion LeftH u m a n R o w P r o p o r t i o n L e f t0.00.20.40.60.81.00.00.20.40.60.81.0C o m p u t e r R o w P r o p o r t i o n L e f t0.00.20.40.60.81.00.00.20.40.60.81.0。

The information in this document is subject to change without notice and does not represent a commitment on the part of Native Instruments GmbH. The software described by this docu-ment is subject to a License Agreement and may not be copied to other media. No part of this publication may be copied, reproduced or otherwise transmitted or recorded, for any purpose, without prior written permission by Native Instruments GmbH, hereinafter referred to as Native Instruments.“Native Instruments”, “NI” and associated logos are (registered) trademarks of Native Instru-ments GmbH.ASIO, VST, HALion and Cubase are registered trademarks of Steinberg Media Technologies GmbH.All other product and company names are trademarks™ or registered® trademarks of their re-spective holders. Use of them does not imply any affiliation with or endorsement by them.Document authored by: David Gover and Nico Sidi.Software version: 2.8 (02/2019)Hardware version: MASCHINE MIKRO MK3Special thanks to the Beta Test Team, who were invaluable not just in tracking down bugs, but in making this a better product.NATIVE INSTRUMENTS GmbH Schlesische Str. 29-30D-10997 Berlin Germanywww.native-instruments.de NATIVE INSTRUMENTS North America, Inc. 6725 Sunset Boulevard5th FloorLos Angeles, CA 90028USANATIVE INSTRUMENTS K.K.YO Building 3FJingumae 6-7-15, Shibuya-ku, Tokyo 150-0001Japanwww.native-instruments.co.jp NATIVE INSTRUMENTS UK Limited 18 Phipp StreetLondon EC2A 4NUUKNATIVE INSTRUMENTS FRANCE SARL 113 Rue Saint-Maur75011 ParisFrance SHENZHEN NATIVE INSTRUMENTS COMPANY Limited 5F, Shenzhen Zimao Center111 Taizi Road, Nanshan District, Shenzhen, GuangdongChina© NATIVE INSTRUMENTS GmbH, 2019. All rights reserved.Table of Contents1Welcome to MASCHINE (23)1.1MASCHINE Documentation (24)1.2Document Conventions (25)1.3New Features in MASCHINE 2.8 (26)1.4New Features in MASCHINE 2.7.10 (28)1.5New Features in MASCHINE 2.7.8 (29)1.6New Features in MASCHINE 2.7.7 (29)1.7New Features in MASCHINE 2.7.4 (31)1.8New Features in MASCHINE 2.7.3 (33)2Quick Reference (35)2.1MASCHINE Project Overview (35)2.1.1Sound Content (35)2.1.2Arrangement (37)2.2MASCHINE Hardware Overview (40)2.2.1MASCHINE MIKRO Hardware Overview (40)2.2.1.1Browser Section (41)2.2.1.2Edit Section (42)2.2.1.3Performance Section (43)2.2.1.4Transport Section (45)2.2.1.5Pad Section (46)2.2.1.6Rear Panel (50)2.3MASCHINE Software Overview (51)2.3.1Header (52)2.3.2Browser (54)2.3.3Arranger (56)2.3.4Control Area (59)2.3.5Pattern Editor (60)3Basic Concepts (62)3.1Important Names and Concepts (62)3.2Adjusting the MASCHINE User Interface (65)3.2.1Adjusting the Size of the Interface (65)3.2.2Switching between Ideas View and Song View (66)3.2.3Showing/Hiding the Browser (67)3.2.4Showing/Hiding the Control Lane (67)3.3Common Operations (68)3.3.1Adjusting Volume, Swing, and Tempo (68)3.3.2Undo/Redo (71)3.3.3Focusing on a Group or a Sound (73)3.3.4Switching Between the Master, Group, and Sound Level (77)3.3.5Navigating Channel Properties, Plug-ins, and Parameter Pages in the Control Area.773.3.6Navigating the Software Using the Controller (82)3.3.7Using Two or More Hardware Controllers (82)3.3.8Loading a Recent Project from the Controller (84)3.4Native Kontrol Standard (85)3.5Stand-Alone and Plug-in Mode (86)3.5.1Differences between Stand-Alone and Plug-in Mode (86)3.5.2Switching Instances (88)3.6Preferences (88)3.6.1Preferences – General Page (89)3.6.2Preferences – Audio Page (93)3.6.3Preferences – MIDI Page (95)3.6.4Preferences – Default Page (97)3.6.5Preferences – Library Page (101)3.6.6Preferences – Plug-ins Page (109)3.6.7Preferences – Hardware Page (114)3.6.8Preferences – Colors Page (114)3.7Integrating MASCHINE into a MIDI Setup (117)3.7.1Connecting External MIDI Equipment (117)3.7.2Sync to External MIDI Clock (117)3.7.3Send MIDI Clock (118)3.7.4Using MIDI Mode (119)3.8Syncing MASCHINE using Ableton Link (120)3.8.1Connecting to a Network (121)3.8.2Joining and Leaving a Link Session (121)4Browser (123)4.1Browser Basics (123)4.1.1The MASCHINE Library (123)4.1.2Browsing the Library vs. Browsing Your Hard Disks (124)4.2Searching and Loading Files from the Library (125)4.2.1Overview of the Library Pane (125)4.2.2Selecting or Loading a Product and Selecting a Bank from the Browser (128)4.2.3Selecting a Product Category, a Product, a Bank, and a Sub-Bank (133)4.2.3.1Selecting a Product Category, a Product, a Bank, and a Sub-Bank on theController (137)4.2.4Selecting a File Type (137)4.2.5Choosing Between Factory and User Content (138)4.2.6Selecting Type and Character Tags (138)4.2.7Performing a Text Search (142)4.2.8Loading a File from the Result List (143)4.3Additional Browsing Tools (148)4.3.1Loading the Selected Files Automatically (148)4.3.2Auditioning Instrument Presets (149)4.3.3Auditioning Samples (150)4.3.4Loading Groups with Patterns (150)4.3.5Loading Groups with Routing (151)4.3.6Displaying File Information (151)4.4Using Favorites in the Browser (152)4.5Editing the Files’ Tags and Properties (155)4.5.1Attribute Editor Basics (155)4.5.2The Bank Page (157)4.5.3The Types and Characters Pages (157)4.5.4The Properties Page (160)4.6Loading and Importing Files from Your File System (161)4.6.1Overview of the FILES Pane (161)4.6.2Using Favorites (163)4.6.3Using the Location Bar (164)4.6.4Navigating to Recent Locations (165)4.6.5Using the Result List (166)4.6.6Importing Files to the MASCHINE Library (169)4.7Locating Missing Samples (171)4.8Using Quick Browse (173)5Managing Sounds, Groups, and Your Project (175)5.1Overview of the Sounds, Groups, and Master (175)5.1.1The Sound, Group, and Master Channels (176)5.1.2Similarities and Differences in Handling Sounds and Groups (177)5.1.3Selecting Multiple Sounds or Groups (178)5.2Managing Sounds (181)5.2.1Loading Sounds (183)5.2.2Pre-listening to Sounds (184)5.2.3Renaming Sound Slots (185)5.2.4Changing the Sound’s Color (186)5.2.5Saving Sounds (187)5.2.6Copying and Pasting Sounds (189)5.2.7Moving Sounds (192)5.2.8Resetting Sound Slots (193)5.3Managing Groups (194)5.3.1Creating Groups (196)5.3.2Loading Groups (197)5.3.3Renaming Groups (198)5.3.4Changing the Group’s Color (199)5.3.5Saving Groups (200)5.3.6Copying and Pasting Groups (202)5.3.7Reordering Groups (206)5.3.8Deleting Groups (207)5.4Exporting MASCHINE Objects and Audio (208)5.4.1Saving a Group with its Samples (208)5.4.2Saving a Project with its Samples (210)5.4.3Exporting Audio (212)5.5Importing Third-Party File Formats (218)5.5.1Loading REX Files into Sound Slots (218)5.5.2Importing MPC Programs to Groups (219)6Playing on the Controller (223)6.1Adjusting the Pads (223)6.1.1The Pad View in the Software (223)6.1.2Choosing a Pad Input Mode (225)6.1.3Adjusting the Base Key (226)6.2Adjusting the Key, Choke, and Link Parameters for Multiple Sounds (227)6.3Playing Tools (229)6.3.1Mute and Solo (229)6.3.2Choke All Notes (233)6.3.3Groove (233)6.3.4Level, Tempo, Tune, and Groove Shortcuts on Your Controller (235)6.3.5Tap Tempo (235)6.4Performance Features (236)6.4.1Overview of the Perform Features (236)6.4.2Selecting a Scale and Creating Chords (239)6.4.3Scale and Chord Parameters (240)6.4.4Creating Arpeggios and Repeated Notes (253)6.4.5Swing on Note Repeat / Arp Output (257)6.5Using Lock Snapshots (257)6.5.1Creating a Lock Snapshot (257)7Working with Plug-ins (259)7.1Plug-in Overview (259)7.1.1Plug-in Basics (259)7.1.2First Plug-in Slot of Sounds: Choosing the Sound’s Role (263)7.1.3Loading, Removing, and Replacing a Plug-in (264)7.1.4Adjusting the Plug-in Parameters (270)7.1.5Bypassing Plug-in Slots (270)7.1.6Using Side-Chain (272)7.1.7Moving Plug-ins (272)7.1.8Alternative: the Plug-in Strip (273)7.1.9Saving and Recalling Plug-in Presets (273)7.1.9.1Saving Plug-in Presets (274)7.1.9.2Recalling Plug-in Presets (275)7.1.9.3Removing a Default Plug-in Preset (276)7.2The Sampler Plug-in (277)7.2.1Page 1: Voice Settings / Engine (279)7.2.2Page 2: Pitch / Envelope (281)7.2.3Page 3: FX / Filter (283)7.2.4Page 4: Modulation (285)7.2.5Page 5: LFO (286)7.2.6Page 6: Velocity / Modwheel (288)7.3Using Native Instruments and External Plug-ins (289)7.3.1Opening/Closing Plug-in Windows (289)7.3.2Using the VST/AU Plug-in Parameters (292)7.3.3Setting Up Your Own Parameter Pages (293)7.3.4Using VST/AU Plug-in Presets (298)7.3.5Multiple-Output Plug-ins and Multitimbral Plug-ins (300)8Using the Audio Plug-in (302)8.1Loading a Loop into the Audio Plug-in (306)8.2Editing Audio in the Audio Plug-in (307)8.3Using Loop Mode (308)8.4Using Gate Mode (310)9Using the Drumsynths (312)9.1Drumsynths – General Handling (313)9.1.1Engines: Many Different Drums per Drumsynth (313)9.1.2Common Parameter Organization (313)9.1.3Shared Parameters (316)9.1.4Various Velocity Responses (316)9.1.5Pitch Range, Tuning, and MIDI Notes (316)9.2The Kicks (317)9.2.1Kick – Sub (319)9.2.2Kick – Tronic (321)9.2.3Kick – Dusty (324)9.2.4Kick – Grit (325)9.2.5Kick – Rasper (328)9.2.6Kick – Snappy (329)9.2.7Kick – Bold (331)9.2.8Kick – Maple (333)9.2.9Kick – Push (334)9.3The Snares (336)9.3.1Snare – Volt (338)9.3.2Snare – Bit (340)9.3.3Snare – Pow (342)9.3.4Snare – Sharp (343)9.3.5Snare – Airy (345)9.3.6Snare – Vintage (347)9.3.7Snare – Chrome (349)9.3.8Snare – Iron (351)9.3.9Snare – Clap (353)9.3.10Snare – Breaker (355)9.4The Hi-hats (357)9.4.1Hi-hat – Silver (358)9.4.2Hi-hat – Circuit (360)9.4.3Hi-hat – Memory (362)9.4.4Hi-hat – Hybrid (364)9.4.5Creating a Pattern with Closed and Open Hi-hats (366)9.5The Toms (367)9.5.1Tom – Tronic (369)9.5.2Tom – Fractal (371)9.5.3Tom – Floor (375)9.5.4Tom – High (377)9.6The Percussions (378)9.6.1Percussion – Fractal (380)9.6.2Percussion – Kettle (383)9.6.3Percussion – Shaker (385)9.7The Cymbals (389)9.7.1Cymbal – Crash (391)9.7.2Cymbal – Ride (393)10Using the Bass Synth (396)10.1Bass Synth – General Handling (397)10.1.1Parameter Organization (397)10.1.2Bass Synth Parameters (399)11Working with Patterns (401)11.1Pattern Basics (401)11.1.1Pattern Editor Overview (402)11.1.2Navigating the Event Area (404)11.1.3Following the Playback Position in the Pattern (406)11.1.4Jumping to Another Playback Position in the Pattern (407)11.1.5Group View and Keyboard View (408)11.1.6Adjusting the Arrange Grid and the Pattern Length (410)11.1.7Adjusting the Step Grid and the Nudge Grid (413)11.2Recording Patterns in Real Time (416)11.2.1Recording Your Patterns Live (417)11.2.2Using the Metronome (419)11.2.3Recording with Count-in (420)11.3Recording Patterns with the Step Sequencer (422)11.3.1Step Mode Basics (422)11.3.2Editing Events in Step Mode (424)11.4Editing Events (425)11.4.1Editing Events with the Mouse: an Overview (425)11.4.2Creating Events/Notes (428)11.4.3Selecting Events/Notes (429)11.4.4Editing Selected Events/Notes (431)11.4.5Deleting Events/Notes (434)11.4.6Cut, Copy, and Paste Events/Notes (436)11.4.7Quantizing Events/Notes (439)11.4.8Quantization While Playing (441)11.4.9Doubling a Pattern (442)11.4.10Adding Variation to Patterns (442)11.5Recording and Editing Modulation (443)11.5.1Which Parameters Are Modulatable? (444)11.5.2Recording Modulation (446)11.5.3Creating and Editing Modulation in the Control Lane (447)11.6Creating MIDI Tracks from Scratch in MASCHINE (452)11.7Managing Patterns (454)11.7.1The Pattern Manager and Pattern Mode (455)11.7.2Selecting Patterns and Pattern Banks (456)11.7.3Creating Patterns (459)11.7.4Deleting Patterns (460)11.7.5Creating and Deleting Pattern Banks (461)11.7.6Naming Patterns (463)11.7.7Changing the Pattern’s Color (465)11.7.8Duplicating, Copying, and Pasting Patterns (466)11.7.9Moving Patterns (469)11.8Importing/Exporting Audio and MIDI to/from Patterns (470)11.8.1Exporting Audio from Patterns (470)11.8.2Exporting MIDI from Patterns (472)11.8.3Importing MIDI to Patterns (474)12Audio Routing, Remote Control, and Macro Controls (483)12.1Audio Routing in MASCHINE (484)12.1.1Sending External Audio to Sounds (485)12.1.2Configuring the Main Output of Sounds and Groups (489)12.1.3Setting Up Auxiliary Outputs for Sounds and Groups (494)12.1.4Configuring the Master and Cue Outputs of MASCHINE (497)12.1.5Mono Audio Inputs (502)12.1.5.1Configuring External Inputs for Sounds in Mix View (503)12.2Using MIDI Control and Host Automation (506)12.2.1Triggering Sounds via MIDI Notes (507)12.2.2Triggering Scenes via MIDI (513)12.2.3Controlling Parameters via MIDI and Host Automation (514)12.2.4Selecting VST/AU Plug-in Presets via MIDI Program Change (522)12.2.5Sending MIDI from Sounds (523)12.3Creating Custom Sets of Parameters with the Macro Controls (527)12.3.1Macro Control Overview (527)12.3.2Assigning Macro Controls Using the Software (528)13Controlling Your Mix (535)13.1Mix View Basics (535)13.1.1Switching between Arrange View and Mix View (535)13.1.2Mix View Elements (536)13.2The Mixer (537)13.2.1Displaying Groups vs. Displaying Sounds (539)13.2.2Adjusting the Mixer Layout (541)13.2.3Selecting Channel Strips (542)13.2.4Managing Your Channels in the Mixer (543)13.2.5Adjusting Settings in the Channel Strips (545)13.2.6Using the Cue Bus (549)13.3The Plug-in Chain (551)13.4The Plug-in Strip (552)13.4.1The Plug-in Header (554)13.4.2Panels for Drumsynths and Internal Effects (556)13.4.3Panel for the Sampler (557)13.4.4Custom Panels for Native Instruments Plug-ins (560)13.4.5Undocking a Plug-in Panel (Native Instruments and External Plug-ins Only) (564)14Using Effects (567)14.1Applying Effects to a Sound, a Group or the Master (567)14.1.1Adding an Effect (567)14.1.2Other Operations on Effects (574)14.1.3Using the Side-Chain Input (575)14.2Applying Effects to External Audio (578)14.2.1Step 1: Configure MASCHINE Audio Inputs (578)14.2.2Step 2: Set up a Sound to Receive the External Input (579)14.2.3Step 3: Load an Effect to Process an Input (579)14.3Creating a Send Effect (580)14.3.1Step 1: Set Up a Sound or Group as Send Effect (581)14.3.2Step 2: Route Audio to the Send Effect (583)14.3.3 A Few Notes on Send Effects (583)14.4Creating Multi-Effects (584)15Effect Reference (587)15.1Dynamics (588)15.1.1Compressor (588)15.1.2Gate (591)15.1.3Transient Master (594)15.1.4Limiter (596)15.1.5Maximizer (600)15.2Filtering Effects (603)15.2.1EQ (603)15.2.2Filter (605)15.2.3Cabinet (609)15.3Modulation Effects (611)15.3.1Chorus (611)15.3.2Flanger (612)15.3.3FM (613)15.3.4Freq Shifter (615)15.3.5Phaser (616)15.4Spatial and Reverb Effects (617)15.4.1Ice (617)15.4.2Metaverb (619)15.4.3Reflex (620)15.4.4Reverb (Legacy) (621)15.4.5Reverb (623)15.4.5.1Reverb Room (623)15.4.5.2Reverb Hall (626)15.4.5.3Plate Reverb (629)15.5Delays (630)15.5.1Beat Delay (630)15.5.2Grain Delay (632)15.5.3Grain Stretch (634)15.5.4Resochord (636)15.6Distortion Effects (638)15.6.1Distortion (638)15.6.2Lofi (640)15.6.3Saturator (641)15.7Perform FX (645)15.7.1Filter (646)15.7.2Flanger (648)15.7.3Burst Echo (650)15.7.4Reso Echo (653)15.7.5Ring (656)15.7.6Stutter (658)15.7.7Tremolo (661)15.7.8Scratcher (664)16Working with the Arranger (667)16.1Arranger Basics (667)16.1.1Navigating Song View (670)16.1.2Following the Playback Position in Your Project (672)16.1.3Performing with Scenes and Sections using the Pads (673)16.2Using Ideas View (677)16.2.1Scene Overview (677)16.2.2Creating Scenes (679)16.2.3Assigning and Removing Patterns (679)16.2.4Selecting Scenes (682)16.2.5Deleting Scenes (684)16.2.6Creating and Deleting Scene Banks (685)16.2.7Clearing Scenes (685)16.2.8Duplicating Scenes (685)16.2.9Reordering Scenes (687)16.2.10Making Scenes Unique (688)16.2.11Appending Scenes to Arrangement (689)16.2.12Naming Scenes (689)16.2.13Changing the Color of a Scene (690)16.3Using Song View (692)16.3.1Section Management Overview (692)16.3.2Creating Sections (694)16.3.3Assigning a Scene to a Section (695)16.3.4Selecting Sections and Section Banks (696)16.3.5Reorganizing Sections (700)16.3.6Adjusting the Length of a Section (702)16.3.6.1Adjusting the Length of a Section Using the Software (703)16.3.6.2Adjusting the Length of a Section Using the Controller (705)16.3.7Clearing a Pattern in Song View (705)16.3.8Duplicating Sections (705)16.3.8.1Making Sections Unique (707)16.3.9Removing Sections (707)16.3.10Renaming Scenes (708)16.3.11Clearing Sections (710)16.3.12Creating and Deleting Section Banks (710)16.3.13Working with Patterns in Song view (710)16.3.13.1Creating a Pattern in Song View (711)16.3.13.2Selecting a Pattern in Song View (711)16.3.13.3Clearing a Pattern in Song View (711)16.3.13.4Renaming a Pattern in Song View (711)16.3.13.5Coloring a Pattern in Song View (712)16.3.13.6Removing a Pattern in Song View (712)16.3.13.7Duplicating a Pattern in Song View (712)16.3.14Enabling Auto Length (713)16.3.15Looping (714)16.3.15.1Setting the Loop Range in the Software (714)16.3.15.2Activating or Deactivating a Loop Using the Controller (715)16.4Playing with Sections (715)16.4.1Jumping to another Playback Position in Your Project (716)16.5Triggering Sections or Scenes via MIDI (717)16.6The Arrange Grid (719)16.7Quick Grid (720)17Sampling and Sample Mapping (722)17.1Opening the Sample Editor (722)17.2Recording Audio (724)17.2.1Opening the Record Page (724)17.2.2Selecting the Source and the Recording Mode (725)17.2.3Arming, Starting, and Stopping the Recording (729)17.2.5Checking Your Recordings (731)17.2.6Location and Name of Your Recorded Samples (734)17.3Editing a Sample (735)17.3.1Using the Edit Page (735)17.3.2Audio Editing Functions (739)17.4Slicing a Sample (743)17.4.1Opening the Slice Page (743)17.4.2Adjusting the Slicing Settings (744)17.4.3Manually Adjusting Your Slices (746)17.4.4Applying the Slicing (750)17.5Mapping Samples to Zones (754)17.5.1Opening the Zone Page (754)17.5.2Zone Page Overview (755)17.5.3Selecting and Managing Zones in the Zone List (756)17.5.4Selecting and Editing Zones in the Map View (761)17.5.5Editing Zones in the Sample View (765)17.5.6Adjusting the Zone Settings (767)17.5.7Adding Samples to the Sample Map (770)18Appendix: Tips for Playing Live (772)18.1Preparations (772)18.1.1Focus on the Hardware (772)18.1.2Customize the Pads of the Hardware (772)18.1.3Check Your CPU Power Before Playing (772)18.1.4Name and Color Your Groups, Patterns, Sounds and Scenes (773)18.1.5Consider Using a Limiter on Your Master (773)18.1.6Hook Up Your Other Gear and Sync It with MIDI Clock (773)18.1.7Improvise (773)18.2Basic Techniques (773)18.2.1Use Mute and Solo (773)18.2.2Create Variations of Your Drum Patterns in the Step Sequencer (774)18.2.3Use Note Repeat (774)18.2.4Set Up Your Own Multi-effect Groups and Automate Them (774)18.3Special Tricks (774)18.3.1Changing Pattern Length for Variation (774)18.3.2Using Loops to Cycle Through Samples (775)18.3.3Load Long Audio Files and Play with the Start Point (775)19Troubleshooting (776)19.1Knowledge Base (776)19.2Technical Support (776)19.3Registration Support (777)19.4User Forum (777)20Glossary (778)Index (786)1Welcome to MASCHINEThank you for buying MASCHINE!MASCHINE is a groove production studio that implements the familiar working style of classi-cal groove boxes along with the advantages of a computer based system. MASCHINE is ideal for making music live, as well as in the studio. It’s the hands-on aspect of a dedicated instru-ment, the MASCHINE hardware controller, united with the advanced editing features of the MASCHINE software.Creating beats is often not very intuitive with a computer, but using the MASCHINE hardware controller to do it makes it easy and fun. You can tap in freely with the pads or use Note Re-peat to jam along. Alternatively, build your beats using the step sequencer just as in classic drum machines.Patterns can be intuitively combined and rearranged on the fly to form larger ideas. You can try out several different versions of a song without ever having to stop the music.Since you can integrate it into any sequencer that supports VST, AU, or AAX plug-ins, you can reap the benefits in almost any software setup, or use it as a stand-alone application. You can sample your own material, slice loops and rearrange them easily.However, MASCHINE is a lot more than an ordinary groovebox or sampler: it comes with an inspiring 7-gigabyte library, and a sophisticated, yet easy to use tag-based Browser to give you instant access to the sounds you are looking for.What’s more, MASCHINE provides lots of options for manipulating your sounds via internal ef-fects and other sound-shaping possibilities. You can also control external MIDI hardware and 3rd-party software with the MASCHINE hardware controller, while customizing the functions of the pads, knobs and buttons according to your needs utilizing the included Controller Editor application. We hope you enjoy this fantastic instrument as much as we do. Now let’s get go-ing!—The MASCHINE team at Native Instruments.MASCHINE Documentation1.1MASCHINE DocumentationNative Instruments provide many information sources regarding MASCHINE. The main docu-ments should be read in the following sequence:1.MASCHINE MIKRO Quick Start Guide: This animated online guide provides a practical ap-proach to help you learn the basic of MASCHINE MIKRO. The guide is available from theNative Instruments website: https:///maschine-mikro-quick-start/2.MASCHINE Manual (this document): The MASCHINE Manual provides you with a compre-hensive description of all MASCHINE software and hardware features.Additional documentation sources provide you with details on more specific topics:►Online Support Videos: You can find a number of support videos on The Official Native In-struments Support Channel under the following URL: https:///NIsupport-EN. We recommend that you follow along with these instructions while the respective ap-plication is running on your computer.Other Online Resources:If you are experiencing problems related to your Native Instruments product that the supplied documentation does not cover, there are several ways of getting help:▪Knowledge Base▪User Forum▪Technical Support▪Registration SupportYou will find more information on these subjects in the chapter Troubleshooting.Document Conventions1.2Document ConventionsThis section introduces you to the signage and text highlighting used in this manual. This man-ual uses particular formatting to point out special facts and to warn you of potential issues.The icons introducing these notes let you see what kind of information is to be expected:This document uses particular formatting to point out special facts and to warn you of poten-tial issues. The icons introducing the following notes let you see what kind of information canbe expected:Furthermore, the following formatting is used:▪Text appearing in (drop-down) menus (such as Open…, Save as… etc.) in the software andpaths to locations on your hard disk or other storage devices is printed in italics.▪Text appearing elsewhere (labels of buttons, controls, text next to checkboxes etc.) in thesoftware is printed in blue. Whenever you see this formatting applied, you will find thesame text appearing somewhere on the screen.▪Text appearing on the displays of the controller is printed in light grey. Whenever you seethis formatting applied, you will find the same text on a controller display.▪Text appearing on labels of the hardware controller is printed in orange. Whenever you seethis formatting applied, you will find the same text on the controller.▪Important names and concepts are printed in bold.▪References to keys on your computer’s keyboard you’ll find put in square brackets (e.g.,“Press [Shift] + [Enter]”).►Single instructions are introduced by this play button type arrow.→Results of actions are introduced by this smaller arrow.Naming ConventionThroughout the documentation we will refer to MASCHINE controller (or just controller) as the hardware controller and MASCHINE software as the software installed on your computer.The term “effect” will sometimes be abbreviated as “FX” when referring to elements in the MA-SCHINE software and hardware. These terms have the same meaning.Button Combinations and Shortcuts on Your ControllerMost instructions will use the “+” sign to indicate buttons (or buttons and pads) that must be pressed simultaneously, starting with the button indicated first. E.g., an instruction such as:“Press SHIFT + PLAY”means:1.Press and hold SHIFT.2.While holding SHIFT, press PLAY and release it.3.Release SHIFT.1.3New Features in MASCHINE2.8The following new features have been added to MASCHINE: Integration▪Browse on , create your own collections of loops and one-shots and send them directly to the MASCHINE browser.Improvements to the Browser▪Samples are now cataloged in separate Loops and One-shots tabs in the Browser.▪Previews of loops selected in the Browser will be played in sync with the current project.When a loop is selected with Prehear turned on, it will begin playing immediately in-sync with the project if transport is running. If a loop preview starts part-way through the loop, the loop will play once more for its full length to ensure you get to hear the entire loop once in context with your project.▪Filters and product selections will be remembered when switching between content types and Factory/User Libraries in the Browser.▪Browser content synchronization between multiple running instances. When running multi-ple instances of MASCHINE, either as Standalone and/or as a plug-in, updates to the Li-brary will be synced across the instances. For example, if you delete a sample from your User Library in one instance, the sample will no longer be present in the other instances.Similarly, if you save a preset in one instance, that preset will then be available in the oth-er instances, too.▪Edits made to samples in the Factory Libraries will be saved to the Standard User Directo-ry.For more information on these new features, refer to the following chapter ↑4, Browser. Improvements to the MASCHINE MIKRO MK3 Controller▪You can now set sample Start and End points using the controller. For more information refer to ↑17.3.1, Using the Edit Page.Improved Support for A-Series Keyboards▪When Browsing with A-Series keyboards, you can now jump quickly to the results list by holding SHIFT and pushing right on the 4D Encoder.▪When Browsing with A-Series keyboards, you can fast scroll through the Browser results list by holding SHIFT and twisting the 4D Encoder.▪Mute and Solo Sounds and Groups from A-Series keyboards. Sounds are muted in TRACK mode while Groups are muted in IDEAS.。

Porting Bullet Physics Library to Cell BEwith libspe2Minh Cuong TranComputer Science DepartmentUniversity of StuttgartEmail:cuong.tran(AT)October8,2007AbstractThe gaming market for Massive Multiplayer Online Game(MMOG) is a high potential,innovative and emerging market[1].MMOGs need a lot of I/O,transactions and also a massive power of computing physics or artificial intelligent.To deal with these requirements we do need a special hybrid platform so-called Gameframe with System Z and Cell BE.Our work focuses porting the Bullet Physics Library to Cell BE as a proof-of-concept for showing the feasibility of the Gameframe.1Contents1Introduction31.1MMOG (3)1.2Hoplon (3)1.3Gameframe (3)1.4Cell BE (4)2Bullet Physics Library42.1Collision Detection (5)2.1.1Broadphase (5)2.1.2Narrowphase (5)2.1.3Heapsort (6)3Broadphase63.1Lines (6)3.2Blocks (8)3.3Double Buffer (8)3.4Intrinsics (9)3.5Optimization with compiler options (10)4Performance measurements10 5Results11 6Further works1221IntroductionIn this section we introduce the architecture of the Gameframe and show you the architecture of our Brazilian customer Hoplon with the Massive Multi Player Game Taikodom.In section two we will have a closer look at the Bullet Physics Library with Collision Detection and Dynamics.The approach in section three is my part where I try to optimize the Broadphase of the collision detection. Afterwards we measure and compare the performance of our approach.1.1MMOGNowadays MMOG can scale to about thousand players on a virtual world.If there are more players,we need a new server with the same configuration.The disadvantage of this setting is operating a huge of servers.The principle of MMOG can also not kept–the players in virtual world A can never meet and interact with the players in virtual world B.The goal of the Gameframe is to bring all the players together in one virtual world.1.2HoplonHoplon Infotainment is a Brazilian start-up software development company[2] with itsfirst MMOG Taikodom and a business partner of IBM.As you can seeFigure1:Taikodom Gamein thefigure1,Taikodom is a game with a scene in outer space.The social interaction like trading,chatting or fulfilling together a mission make Taikdom so special and it is thefirst social MMOG.1.3GameframeGameframe is a made-up word of the IBM System Z also referred to as Main-frame for the gaming market.First of all the Mainframe is a primer I/O machine for using high-transaction-rate with security and reliability.The requirement of gaming is also huge computing power.Therefore we need a second part like Cell BE in Blade Servers as special processors for the Gameframe.3Infigure2you can see a possible architecture of the Gameframe–in this case the architecture is in the context of Taikodom.On the left side you can see the clients.They are connecting via internet with the game logic on the Mainframe. The Mainframe is responsible for the main part of the game where transactions between the gamers are made.On the right side you can see the Cell Blades –we offload the physics to the Cell Blades for cost-efficient scalability.We believe that this hybrid architecture is forward looking and will revolutionize the MMOG market.We are confident that it is possible to get up to hundred thousand clients on the Gameframe or even more.Figure2:Architecture of the Taikodom Game1.4Cell BEThe Cell Broadband Engine is a microprocessor architecture jointly developed by Sony,Toshiba and IBM,an alliance known as STI.Cell combines a general-purpose Power Architecture core of modest performance with streamlined co-processing elements which greatly accelerate multimedia and vector processing applications,as well as many other forms of dedicated computation.As you can see infigure3the Cell configuration normally has one Power Processing El-ement(PPE)with eight physical Synergistic Processing Elements(SPE).The Element Interconnect Bus(EIB)is a communication bus internal to the Cell processor which connects the various on-chip system elements:the PPE proces-sor,the memory controller(MIC),the eight SPE coprocessors,and two off-chip I/O interfaces,for a total of12participants[3]2Bullet Physics LibraryThe Bullet Physics Library is an open source software,the maintainer is Erwin Coumans[4].Bullet can be divide into two parts:Collision Detection and Dynamics.The collision part answers the question whether twoflying space ships will be collide or not.We are interested in contact points and the reaction on the collision after detecting them–this is responsible by the Dynamics.As you can see on the pie chart atfigure4we analysed a typical demo for Bullet.4Figure3:Architecture of CellThe chart shows the processor load of the Collision Detection(Broadphase andNarrowphase)33%and the Dynamics67%.Figure4:Test case2.1Collision DetectionThe Collision Detection consists of two parts the Broadphase and Narrowphase.2.1.1BroadphaseThe algorithms for calculating the actual Collision Detection are elaborate anduse huge of processor power.To minimize this,the Broadphasefilters the po-tential pairs of candidates out and let the Narrowphase review the pairs again.2.1.2NarrowphaseThe Narrowphase puts the pairs of candidates in a cache.Sorting by heap-sort the Narrowphasefilters the duplicated pairs out and applies the actual5algorithms on remaining pairs.One algorithm is for example Gilbert-Johnson-Keerthi (GJK),which uses Minkowski difference.This and further algorithms we do not focus and explain in this work.2.1.3HeapsortThe objects like space ships in the Taikodom game move forward,so the Col-lision Detection are used by the game logic all along.For not computing the collisions so often the Narrowphase keeps the cache of pairs and applies the heapsort after every time step to detect duplicated pairs.Figure 5:Taikodom and Bullet3BroadphaseAs show in figure 5every complex objects get a axis-aligned-bounding-box (AABB or so-called Proxy in Bullet)around them.Now it is really simple and fast to verify if pairs are potential candidates for the Narrowphase.Every Proxy has a maximum and a minimum point building a box around it.The algorithm 1shows how the Broadphase works on the PPU.The complexity ofthe Broadphase is in O (12n 2).It is readily identifiable that the computation in the double loop is dataflow independent and we can parallelise the work on the SPUs.3.1LinesThe first approach for investigation is line-wise.As you can imagine the re-sult of the procedure calculateOverlappingP airs is a matrix reflecting whether proxies [i ]overlaps proxies [j ]or not.The main idea is to delegate the work to the SPUs by transferring all proxies to each SPUs.Every SPU computes several lines of the matrix.The result is copied back to the PPU while the PPU is waiting.PPU is waiting:6Algorithm1SimpleBroadphase on PPU1:function aabbOverlap(Proxy a,Proxy b)2:return3: a.min[0]≤b.max[0]∧b.min[0]≤a.max[0]∧4: a.min[1]≤b.max[1]∧b.min[1]≤a.max[1]∧5: a.min[2]≤b.max[2]∧b.min[2]≤a.max[2]6:end function7:procedure calculateOverlappingPairs(Proxy[numProxies]proxies) 8:for i=0...numP roxies−1do9:for j=i...numP roxies−1do10:if aabbOverlap(proxies[i],proxies[j])then11:if notInCache(proxies[i],proxies[j])then12:addP airT oCache(proxies[i],proxies[j]);13:end if14:end if15:end for16:end for17:end procedurep0*******0011100111-10110112--1001013---111014----00015-----0116------107-------1SPU0is working on line0and1:p0*******0011100111-1011011SPU1is working on line2and3:p0*******2--1001013---11101SPU2is working on line4and5:p0*******4----00015-----011SPU3is working on line6and7:7p0*******6------107-------13.2BlocksThe next approach is block-wise.Thefigure6illustrates how the matrix is divided into blocks.Every SPU gets some proxies in the x-and the y-axis, calculates the block and copies the result back and calculates the next block and so on.Figure6:Broadphase3.3Double BufferThe bottle-neck of the block-wise version is the waiting time for transferring the proxies and the result.So the next idea in algorithm2is using double buffer.While waiting for the DMA(Direct Memory Access)transfer,the SPU calculates the block in the buffer.Algorithm2Double buffer algorithm on one SPU1:get(0);2:waitGet(0);3:for i=0...n−2do4:get(1−(i&1));5:calc(0+(i&1)); while waiting for1we calculate0 6:put(0+(i&1));7:waitGet(1−(i&1)); finishing get1 8:waitP ut(0+(i&1)); finishing put0 9:calcNextBlock;10:end for11:calc(1−(n&1));12:put(1−(n&1));13:waitP ut(1−(n&1));83.4IntrinsicsThe benefit of using Cell BE is having SIMD(Single Instruction,Multiple Data). To improve the performance you have to put the data to one vector for calcu-lating in one instruction.The snippet code in algorithm3shows the changing of the data structure to make SIMD available.Algorithm3Data structures for SIMD1:typedef union{2:unsigned int v[4];3:vector unsigned int V ec;4:}uintV ec;5:typedef struct{6:union{7:float v[4];8:vector float V ec;9:}min;10:union{11:float v[4];12:vector float V ec;13:}max;14:}P roxySP U;Algorithm4shows the new version of aabbOverlap for the SPU with the new data structures.Algorithm4aabbOverlap with Intrinsics on SPU1:uintV ec cmp0;2:uintV ec cmp1;3:uintV ec resultAabbOverlapSP U;4:function aabbOverlapSPU(ProxySPU a,ProxySPU b)5: piece-wise greater than 6:cmp0.V ec=spu cmpgt(b.max.V ec,a.min.V ec);7:cmp1.V ec=spu cmpgt(a.max.V ec,b.min.V ec);8: piece-wise and,the fourth element is not used 9:resultAabbOverlapSP U.V ec=spu and(cmp0.V ec,cmp1.V ec);10:return11:resultAabbOverlapSP U.v[0]∧12:resultAabbOverlapSP U.v[1]∧13:resultAabbOverlapSP U.v[2];14:end function93.5Optimization with compiler optionsUsing gcc4.1.1[5]to get the optimum runtime wefind out that for our case it is the best to use the compiler option-O3for the PPU and-O3-funroll-all-loops for the SPUs.4Performance measurementsFor optimization and performance measurements oprofile[6]and gprof[7]are two tools to show us which functions and statements use a lot of processor power and where we can optimize.Furthermore,the Cell graphical systemsim from the IBM CellSDK2.1[3]shows us more details what happen on the SPUs.Here you can see in details the measurements of one SPU,the CPI(Cycle Per Instruction)is2.40.##########################################################SPU DD3.0***Total Cycle count12224359Total Instruction count643Total CPI19011.44***Performance Cycle count12224359Performance Instruction count5094013(4780021)Performance CPI 2.40(2.56)Branch instructions238946Branch taken146348Branch not taken92598Hint instructions109611Hint hit89571Contention at LS between Load/Store and Prefetch42493Single cycle3742841(30.6%)Dual cycle518590( 4.2%)Nop cycle204313( 1.7%)Stall due to branch miss1577822(12.9%)Stall due to prefetch miss0(0.0%)Stall due to dependency1389253(11.4%)Stall due to fp resource conflict0(0.0%)Stall due to waiting for hint target58843(0.5%)Issue stalls due to pipe hazards6(0.0%)Channel stall cycle4732682(38.7%)SPU Initialization cycle9(0.0%)---------------------------------------------------------Total cycle12224359(100.0%)10Stall cycles due to dependency on each pipelinesFX2479779(34.5%of all dependency stalls)SHUF 282674(20.3%of all dependency stalls)FX386359( 6.2%of all dependency stalls)LS 441726(31.8%of all dependency stalls)BR 0(0.0%of all dependency stalls)SPR 21(0.0%of all dependency stalls)LNOP 0(0.0%of all dependency stalls)NOP 0(0.0%of all dependency stalls)FXB 0(0.0%of all dependency stalls)FP60(0.0%of all dependency stalls)FP798688(7.1%of all dependency stalls)FPD 6(0.0%of all dependency stalls)The number of used registers are 128,the used ratio is100.00dumped pipeline stats##########################################################5ResultsIn this section we present the result of our approach as you can see in figure 7.The chart shows measurements of the block-wise approach.The x-axis is the number of the Proxies,from 32till 1024,the y-axis displays the using of PPU,1,4and 8SPUs,the z-axis is the time we measured in seconds.The block size is 4x4.Our improvement for the Broadphase with 1024Proxies is about 2.8times faster than the PPU-only version.Figure 7:The result of optimizing BroadphaseThe next table shows the result of PPU-only;PPU,8SPUs and line-wise approach;PPU,8SPUs and block-wise approach.In general the block-wiseapproach might be better for algorithms within O (12n 2)(just wait once fortransferring the data to the SPU and back),but consider the 256KB memory constraint of the SPUs.The advantage of the block-wise approach is not having a limit of the number of the Proxies.Generally the two approaches can be used for algorithms in O (n 2)as well.11PPU-only8SPUs line-wise8SPUs block-wiseTime0.034s0.010s0.012sThefigure4shows our testcase for the Collision Detection.A lot of objects move step-by-step to the point of origin causing a lot of collisions.The chart infigure8is the result of our team.With8SPUs we are6.5times faster than with PPU.We have four team members.Martina H¨u llmann optimized Heapsort for the SPUs,Benjamin H¨o ferlin had a closer look at the Narrowphase and Frederick Roth was responsible for the performance measurements.For more information about their works please inquire their report,paper and Assistenten-Arbeit.Figure8:Result of Collision DetectionWith our work and further work on physics more complex physics,more realistic physics will be possible and the players have more fun.Beyond gaming there may be severalfields of application for the Gameframe,application where massive computing power meets extreme I/O.6Further worksIn the future interesting things like artificial intelligence or compression algo-rithms could be offload to the Cellblades.Other efforts like creating a standard platform for gaming on Mainframe are the basis for discussion and further works.12References[1]Voig Inc. New York2007[2]Hoplon Infotainment,,2007[3]IBM,Cell Broadband Engine Programming Tutorial,p.17,Version2.1,IBM,March2007[4]Erwin Coumans,Bullet Physics Library,Version2.56,[5]GCC,GNU Compiler Collection,Version4.1.1,[6]OProfile,A System Profiler for Linux,Version0.92,http://oprofi[7]Jay Fenlason and Richard Stallman,gprof–The GNU Profiler,Version2.15.92.0.2,/software/binutils13。

Sequences of Games:A Tool for Taming Complexity in Security Proofs∗Victor Shoup†January18,2006AbstractThis paper is brief tutorial on a technique for structuring security proofs as sequences games.1IntroductionSecurity proofs in cryptography may sometimes be organized as sequences of games.In certain circumstances,this can be a useful tool in taming the complexity of security proofs that might otherwise become so messy,complicated,and subtle as to be nearly impossible to verify.This technique appears in the literature in various styles,and with various degrees of rigor and formality.This paper is meant to serve as a brief tutorial on one particular“style”of employing this technique,which seems to achieve a reasonable level of mathematical rigor and clarity,while not getting bogged down with too much formalism or overly restrictive rules.We do not make any particular claims of originality—it is simply hoped that others might profit from some of the ideas discussed here in reasoning about security.At the outset,it should be noted that this technique is certainly not applicable to all security proofs.Moreover,even when this technique is applicable,it is only a tool for organizing a proof—the actual ideas for a cryptographic construction and security analysis must come from elsewhere.1.1The Basic IdeaSecurity for cryptograptic primitives is typically defined as an attack game played between an adversary and some benign entity,which we call the challenger.Both adversary and challenger are probabilstic processes that communicate with each other,and so we can model the game as a probability space.Typically,the definition of security is tied to some particular event S.Security means that for every“efficient”adversary,the probability that event S occurs is“very close to”some specified“target probabilty”:typically,either0, 1/2,or the probability of some event T in some other game in which the same adversary is interacting with a different challenger.∗First public version:Nov.30,2004†Computer Science Dept.NYU.shoup@In the formal definitions,there is a security parameter:an integer tending to infinity,and in the previous paragraph,“efficient”means time bounded by a polynomial in the security parameter,and“very close to”means the difference is smaller than the inverse of any polynomial in the security parameter,for sufficiently large values of the security parameter. The term of art is negligibly close to,and a quantity that is negliglibly close to zero is just called negligible.For simplicity,we shall for the most part avoid any further discussion of the security parameter,and it shall be assumed that all algorithms,adversaries,etc.,take this value as an implicit input.Now,to prove security using the sequence-of-games approach,one prodceeds as follows. One constructs a sequence of games,Game0,Game1,...,Game n,where Game0is the original attack game with respect to a given adversary and cryptographic primitive.Let S0 be the event S,and for i=1,...,n,the construction defines an event S i in Game i,usually in a way naturally related to the definition of S.The proof shows that Pr[S i]is negligibly close to Pr[S i+1]for i=0,...,n−1,and that Pr[S n]is equal(or negligibly close)to the “target probability.”From this,and the fact that n is a constant,it follows that Pr[S]is negligibly close to the“target probability,”and security is proved.That is the general framework of such a proof.However,in constructing such proofs, it is desirable that the changes between succesive games are very small,so that analyzing the change is as simple as possible.From experience,it seems that transitions between successive games can be restricted to one of three types:Transitions based on indistinguishability.In such a transition,a small change is made that,if detected by the adversary,would imply an efficient method of distinguishing be-tween two distributions that are indistinguishable(either statistically or computationally). For example,suppose P1and P2are assumed to be computationally indistinguishable dis-tributions.To prove that|Pr[S i]−Pr[S i+1]|is negligible,one argues that there exists a distinguishing algorithm D that“interpolates”between Game i and Game i+1,so that when given an element drawn from distribution P1as input,D outputs1with probability Pr[S i], and when given an element drawn from distribution P2as input,D outputs1with prob-abilty Pr[S i+1].The indistinguishability assumption then implies that|Pr[S i]−Pr[S i+1]| is ually,the construction of D is obvious,provided the changes made in the transition are minimal.Typically,one designs the two games so that they could easily be rewritten as a single“hybrid”game that takes an auxilliary input—if the auxiallary input is drawn from P1,you get Game i,and if drawn from P2,you get Game i+1.The distinguisher then simply runs this single hybrid game with its input,and outputs1if the appropriate event occurs.Transitions based on failure events.In such a transition,one argues that Games i and i+1proceed identically unless a certain“failure event”F occurs.To make this type of argument as cleanly as possible,it is best if the two games are defined on the same underlying probability space—the only differences between the two games are the rules for computing certain random variables.When done this way,saying that the two games proceed identically unless F occurs is equivalent to saying thatS i∧¬F⇐⇒S i+1∧¬F,that is,the events S i∧¬F and S i+1∧¬F are the same.If this is true,then we can use thefollowing fact,which is completely trivial,yet is so often used in these types of proofs that it deserves a name:Lemma1(Difference Lemma).Let A,B,F be events defined in some probability dis-tribution,and suppose that A∧¬F⇐⇒B∧¬F.Then|Pr[A]−Pr[B]|≤Pr[F]. Proof.This is a simple calculation.We have|Pr[A]−Pr[B]|=|Pr[A∧F]+Pr[A∧¬F]−Pr[B∧F]−Pr[B∧¬F]|=|Pr[A∧F]−Pr[B∧F]|≤Pr[F].The second equality follows from the assumption that A∧¬F⇐⇒B∧¬F,and so in particular,Pr[A∧¬F]=Pr[B∧¬F].Thefinal inequality follows from the fact that both Pr[A∧F]and Pr[B∧F]are numbers between0and Pr[F].2So to prove that Pr[S i]is negligibly close to Pr[S i+1],it suffices to prove that Pr[F]is negligible.Sometimes,this is done using a security assumption(i.e.,when F occurs,the adversary has found a collision in a hash function,or forged a MAC),while at other times, it can be done using a purely information-theoretic argument.Usually,the event F is defined and analyzed in terms of the random variables of one of the two adjacent games.The choice is arbitrary,but typically,one of the games will be more suitable than the other in terms of allowing a clear proof.In some particularly challenging circumstances,it may be difficult to analyze the event F in either game.In fact,the analysis of F may require its own sequence of games sprouting offin a different direction,or the sequence of games for F may coincide with the sequence of games for S,so that Pr[F]finally gets pinned down in Game j for j>i+1.This technique is sometimes crucial in side-stepping potential circularities.Bridging steps.The third type of transition introduces a bridging step,which is typically a way of restating how certain quantities can be computed in a completely equivalent way. The change is purely conceptual,and Pr[S i]=Pr[S i+1].The reason for doing this is to prepare the ground for a transition of one of the above two types.While in principle,such a bridging step may seem unnecessary,without it,the proof would be much harder to follow.As mentioned above,in a transition based on a failure event,it is best if the two successive games are understood to be defined on the same underlying probability space. This is an important point,which we repeat here for emphasis—it seems that proofs are easiest to understand if one does not need to compare“corresponding”events across distinct and(by design)quite different probability spaces.Actually,it is good practice to simply have all the games in the sequence defined on the same underlying probability space.However,the Difference Lemma generalizes in the obvious way as follows:if A, B,F1and F2are events such that Pr[A∧¬F1]=Pr[B∧¬F2]and Pr[F1]=Pr[F2],then |Pr[A]−Pr[B]|≤Pr[F1].With this generalized version,one may(if one wishes)analyze transitions based on failure events when the underlying probability spaces are not the same.1.2Some Historical Remarks“Hybrid arguments”have been used extensively in cryptography for many years.Such an argument is essentially a sequence of transitions based on indistinguishability.An early example that clearly illustrates this technique is Goldreich,Goldwasser,and Micali’s paper [GGM86]on constructing pseudo-random functions(although this is by no means the ear-liest application of a hybrid argument).Note that in some applications,such as[GGM86], one in fact makes a non-constant number of transitions,which requires an additional,prob-abilistic argument.Although some might use the term“hybrid argument”to include proofs that use transi-tions based on both indistinguishability and failure events,that seems to be somewhat of a stretch of terminology.An early example of a proof that is clearly structured as a sequence of games that involves transitions based on both indistinguishability and failure events is Bellare and Goldwasser’s paper[BG89].Kilian and Rogaway’s paper[KR96]on DESX initiates a somewhat more formal ap-proach to sequences of games.That paper essentially uses the Difference Lemma,specialized to their particular setting.Subsequently,Rogaway has refined and applied this technique in numerous works with several co-authors.We refer the reader to the paper[BR04]by Bellare and Rogaway that gives a detailed introduction to the methodology,as well as references to papers where it has been used.However,we comment briefly on some of the differences between the technique discussed in this paper,and that advocated in[BR04]:•In Bellare and Rogaway’s approach,games are programs and are treated as purely syntactic objects subject to formal manipulation.In contrast,we view games as probability spaces and random variables defined over them,and do not insist on any particular syntactic formalism beyond that convenient to make a rigorous mathemat-ical argument.•In Bellare and Rogaway’s approach,transitions based on failure events are restricted to events in which an executing program explicitly sets a particular boolean variable to true.In contrast,we do not suggest that events need to be explicitly“announced.”•In Bellare and Rogaway’s approach,when the execution behaviors of two games are compared,two distinct probability spaces are involved,and probabilities of“corre-sponding”events across probability spaces must be compared.In contrast,we sug-gest that games should be defined on a common probability space,so that when discussing,say,a particular failure event F,there is literally just one event,not a pair of corresponding events in two different probability spaces.In the end,we think that the choice between the style advocated in[BR04]and that suggested here is mainly a matter of taste and convenience.The author has used proofs organized as sequences of games extensively in his own work [Sho00,SS00,Sho01,Sho02,CS02,CS03b,CS03a,GS04]and has found them to be an indispensable tool—while some of the proofs in these papers could be structured differently, it is hard to imagine how most of them could be done in a more clear and convincing way without sequences of games(note that all but thefirst two papers above adhere to the rule suggested here of defining games to operate on the same probability space).Other authorshave also been using very similar proof styles recently[AFP04,BK04,BCP02a,BCP02b, BCP03,CPP04,DF03,DFKY03,DFJW04,Den03,FOPS04,GaPMV03,KD04,PP03, SWP04].Also,Pointcheval[Poi04]has a very nice introductory manuscript on public-key cryptography that illustrates this proof style on a number of particular examples.The author has also been using the sequence-of-games technique extensively in teaching courses in cryptography.Many“classical”results in cryptography can be fruitfully analyzed using this technique.Generally speaking,it seems that the students enjoy this approach, and easily learn to use and apply it themselves.Also,by using a consistent framework for analysis,as an instructor,one can more easily focus on the ideas that are unique to any specific application.1.3Outline of the Rest of the PaperAfter recalling some fairly standard notation in the next section,the following sections illustrate the use of the sequence-of-games technique in the analysis of a number of classical cryptographic pared to many of the more technically involved examples in the literature of this technique(mentioned above),the applications below are really just “toy”examples.Nevertheless,they serve to illustrate the technique in a concrete way,and moreover,we believe that the proofs of these results are at least as easy to follow as any other proof,if not more so.All of the examples,except the last two(in§§7-8),are presented at an extreme level of detail;indeed,for these examples,we give complete,detailed descriptions of each and every game.More typically,to produce a more compact proof,one might simply describe the differences between games,rather than describing each game in its entirety(as is done in§§7-8).These examples are based mainly on lectures in courses on cryptography taught by the author.2NotationWe make use of fairly standard notation in what follows.In describing probabilistic processes,we writex c|←Xto denote the action of assigning to the variable x a value sampled according to the dis-tribution X.If S is afinite set,we simply write s c|←S to denote assignment to s of an element sampled from the uniform distribution on S.If A is a probabilistic algorithm and x an input,then A(x)denotes the output distribution of A on input x.Thus,we write y c|←A(x)to denote the action of running algorithm A on input x and assigning the output to the variable y.We shall writePr[x1c|←X1,x2c|←X2(x1),...,x n c|←X n(x1,...,x n−1):φ(x1,...,x n)]to denote the probability that when x1is drawn from a certain distribution X1,and x2is drawn from a certain distribution X2(x1),possibly depending on the particular choice ofx1,and so on,all the way to x n,the predicateφ(x1,...,x n)is true.We allow the predicate φto involve the execution of probabilistic algorithms.If X is a probability distribution on a sample space X,then[X]denotes the subset of elements of X that occur with non-zero probability.3ElGamal Encryption3.1Basic DefinitionsWefirst recall the basic definition of a public-key encryption scheme,and the notion of semantic security.A public-key encryption scheme is a triple of probabilistic algorithms(KeyGen,E,D). The key generation algorithm KeyGen takes no input(other than an implied security pa-rameter,and perhaps other system parameters),and outputs a public-key/secret-key pair (pk,sk).The encryption algorithm E takes as input a public key pk and a message m, selected from a message space M,and outputs a ciphertextψ.The decryption algorithm takes as input a secret key sk and ciphertextψ,and outputs a message m.The basic correctness requirement is that decryption“undoes”encryption.That is,for all m∈M,all(pk,sk)∈[KeyGen()],allψ∈[E(pk,m)],and all m ∈[D(sk,ψ)],we have m=m .This definition can be relaxed in a number of ways;for example,we may only insist that it is computationally infeasible tofind a message for which decryption does not “undo”its encryption.The notion of semantic security intuitively says that an adversary cannot effectively dis-tinguish between the encryption of two messages of his choosing(this definition comes from [GM84],where is called polynomial indistinguishability,and semantic security is actually the name of a syntactically different,but equivalent,characterization).This is formally defined via a game between an adversary and a challenger.•The challenger computes(pk,sk)c|←KeyGen(),and gives pk to the adversary.•The adversary chooses two messages m0,m1∈M,and gives these to the challenger.•The challenger computesb c|←{0,1},ψc|←E(pk,m b)and gives the“target ciphertext”ψto the adversary.•The adversary outputsˆb∈{0,1}.We define the SS-advantage of the adversary to be|Pr[b=ˆb]−1/2|.Semantic security means that any efficient adversary’s SS-advantage is negligible.3.2The ElGamal Encryption SchemeWe next recall ElGamal encryption.Let G be a group of prime order q,and letγ∈G be a generator(we view the descriptions of G andγ,including the value q,to be part of a set of implied system parameters).The key generation algorithm computes(pk,sk)as follows:x c|←Z q,α←γx,pk←α,sk←x.The message space for the algorithm is G.To encrypt a message m∈G,the encryption algorithm computes a ciphertextψas follows:y c|←Z q,β←γy,δ←αy,ζ←δ·m,ψ←(β,ζ).The decryption algorithm takes as input a ciphertext(β,ζ),and computes m as follows:m←ζ/βx.It is clear that decryption“undoes”encryption.Indeed,ifβ=γy andζ=αy·m,then ζ/βx=αy m/βx=(γx)y m/(γy)x=γxy m/γxy=m.3.3Security AnalysisElGamal encryption is semantically secure under the Decisional Diffie-Hellman(DDH) assumption.This is the assumption that it is hard to distinguish triples of the form (γx,γy,γxy)from triples of the form(γx,γy,γz),where x,y,and z are random elements of Z q.The DDH assumption is more precisely formulated as follows.Let D be an algorithm that takes as input triples of group elements,and outputs a bit.We define the DDH-advantage of D to be|Pr[x,y c|←Z q:D(γx,γy,γxy)=1]−Pr[x,y,z c|←Z q:D(γx,γy,γz)=1]|.The DDH assumption(for G)is the assumption that any efficient algorithm’s DDH-advantage is negligible.We now give a proof of the semantic security of ElGamal encryption under the DDH assumption,using a sequence of games.Game0.Fix an efficient adversary A.Let us define Game0to be the attack game against A in the definition of semantic security.To make things more precise and more concrete, we may describe the attack game algorithmically as follows:x c|←Z q,α←γxr c|←R,(m0,m1)←A(r,α)b c|←{0,1},y c|←Z q,β←γy,δ←αy,ζ←δ·m bˆb←A(r,α,β,ζ)In the above,we have modeled the adversary A is a deterministic algorithm that takes as input“random coins”r sampled uniformly from some set R.It should be evident that this algorithm faithfully represents the attack game.If we define S0to be the event that b=ˆb,then the adversary’s SS-advantage is|Pr[S0]−1/2|.Game1.[This is a transition based on indistinguishability.]We now make one small change to the above ly,instead of computingδasαy,we compute it asγz for randomly chosen z∈Z q.We can describe the resulting game algorithmically as follows: x c|←Z q,α←γxr c|←R,(m0,m1)←A(r,α)b c|←{0,1},y c|←Z q,β←γy,z c|←Z q,δ←γz,ζ←δ·m bˆb←A(r,α,β,ζ)Let S1be the event that b=ˆb in Game1.Claim1.Pr[S1]=1/2.This follows from the fact that in Game2,δis effectively a one-time pad,and as such,the adversary’s outputˆb is independent of the hidden bit b.To prove this more rigorously,it will suffice to show that b,r,α,β,ζare mutually independent, since from this,it follows that b andˆb=A(r,α,β,ζ)are independent.First observe that by construction,b,r,α,β,δare mutually independent.It will suffice to show that conditioned on anyfixed values of b,r,α,β,the conditional distribution ofζis the uniform distribution over G.Now,if b,r,α,βarefixed,then so are m0,m1,since they are determined by r,α; moreover,by independence,the conditional distribution ofδis the uniform distribution on G,and hence from this,one sees that the conditional distribution ofζ=δ·m b is the uniform distribution on G.Claim2.|Pr[S0]−Pr[S1]|= ddh,where ddh is the DDH-advantage of some efficient algorithm(and hence negligible under the DDH assumption).The proof of this is essentially the observation that in Game0,the triple(α,β,δ)is of the form(γx,γy,γxy),while in Game1,it is of the form(γx,γy,γz),and so the adversary should not notice the difference,under the DDH assumption.To be more precise,our distinguishing algorithm D works as follows:Algorithm D(α,β,δ)r c|←R,(m0,m1)←A(r,α)b c|←{0,1},ζ←δ·m bˆb←A(r,α,β,ζ)if b=ˆbthen output1else output0Algorithm D effectively“interpolates”between Games0and1.If the input to D is of the form(γx,γy,γxy),then computation proceeds just as in Game0,and thereforePr[x,y c|←Z q:D(γx,γy,γxy)=1]=Pr[S0].If the input to D is of the form(γx,γy,γz),then computation proceeds just as in Game1, and thereforePr[x,y,z c|←Z q:D(γx,γy,γz)=1]=Pr[S1].From this,it follows that the DDH-advantage of D is equal to|Pr[S0]−Pr[S1]|.That completes the proof of Claim2.Combining Claim1and Claim2,we see that|Pr[S0]−1/2|= ddh,and this is negligible.That completes the proof of security of ElGamal encryption.3.4Hashed ElGamalFor a number of reasons,it is convenient to work with messages that are bit strings,say,of length ,rather than group elements.Because of this,one may choose to use a“hashed”version of the ElGamal encryption scheme.This scheme makes use of a family of keyed“hash”functions H:={H k}k∈K,where each H k is a function mapping G to{0,1} .The key generation algorithm computes(pk,sk)as follows:x c|←Z q,k c|←K,α←γx,pk←(α,k),sk←(x,k).To encrypt a message m∈{0,1} ,the encryption algorithm computes a ciphertextψas follows:y c|←Z q,β←γy,δ←αy,h←H k(δ),v←h⊕m,ψ←(β,v).The decryption algorithm takes as input a ciphertext(β,v),and computes m as follows:m←H k(βx)⊕v.The reader may easily verify that decryption“undoes”encryption.As for semantic security,this can be proven under the DDH assumption and the as-sumption that the family of hash functions H is“entropy smoothing.”Loosely speaking, this means that it is hard to distinguish(k,H k(δ))from(k,h),where k is a random element of K,δis a random element of G,and h is a random element of{0,1} .More formally, let D be an algorithm that takes as input an element of K and an element of{0,1} ,and outputs a bit.We define the ES-advantage of D to be|Pr[k c|←K,δc|←G:D(k,H k(δ))=1]−Pr[k c|←K,h c|←{0,1} :D(k,h)=1]|.We say H is entropy smoothing if every efficient algorithm’s ES-advantage is negligible.It is in fact possible to construct entropy smoothing hash function families without ad-ditional hypothesis(the Leftover Hash Lemma may be used for this[IZ89]).However,these may be somewhat less practical than ad hoc hash function families for which the entropy smoothing property is only a(perfectly reasonable)conjecture;moreover,our definition also allows entropy smoothers that use pseudo-random bit generation techniques as well.We now sketch the proof of semantic security of hashed ElGamal encryption,under the DDH assumption and the assumption that H is entropy smoothing.Game0.This is the original attack game,which we can state algorithmically as follows:x c|←Z q,k c|←K,α←γxr c|←R,(m0,m1)←A(r,α,k)b c|←{0,1},y c|←Z q,β←γy,δ←αy,h←H k(δ),v←h⊕m bˆb←A(r,α,k,β,v)We define S0to be the event that b=ˆb in Game0.Game1.[This is a transition based on indistinguishability.]Now we transform Game0 into Game1,computingδasγz for random z∈Z q.We can state Game1algorithmically as follows:x c|←Z q,k c|←K,α←γxr c|←R,(m0,m1)←A(r,α,k)b c|←{0,1},y c|←Z q,β←γy,z c|←Z q,δ←γz,h←H k(δ),v←h⊕m bˆb←A(r,α,k,β,v)Let S1be the event that b=ˆb in Game1.We claim that|Pr[S0]−Pr[S1]|= ddh,(1) where ddh is the DDH-advantage of some efficient algorithm(which is negligible under the DDH assumption).The proof of this is almost identical to the proof of the corresponding claim for“plain”ElGamal.Indeed,the following algorithm D“interpolates”between Game0and Game1, and so has DDH-advantage equal to|Pr[S0]−Pr[S1]|:Algorithm D(α,β,δ)k c|←Kr c|←R,(m0,m1)←A(r,α,k)b c|←{0,1},h←H k(δ),v←h⊕m bˆb←A(r,α,k,β,v)if b=ˆbthen output1else output0Game 2.[This is also a transition based on indistinguishability.]We now transform Game1into Game2,computing h by simply choosing it at random,rather than as a hash. Algorithmically,Game2looks like this:x c|←Z q,k c|←K,α←γxr c|←R,(m0,m1)←A(r,α,k)b c|←{0,1},y c|←Z q,β←γy,z c|←Z q,δ←γz,h c|←{0,1} ,v←h⊕m bˆb←A(r,α,k,β,v)Observe thatδplays no role in Game2.Let S2be the event that b=ˆb in Game2.We claim that|Pr[S1]−Pr[S2]|= es,(2) where es the ES-advantage of some efficient algorithm(which is negligible assuming H is entropy smoothing).This is proved using the same idea as before:any difference between Pr[S1]and Pr[S2] can be parlayed into a corresponding ES-advantage.Indeed,it is easy to see that the fol-lowing algorithm D “interpolates”between Game1and Game2,and so has ES-advantage equal to|Pr[S1]−Pr[S2]|:Algorithm D (k,h)x c|←Z q,α←γxr c|←R,(m0,m1)←A(r,α,k)b c|←{0,1},y c|←Z q,β←γy,v←h⊕m bˆb←A(r,α,k,β,v)if b=ˆbthen output1else output0Finally,as h acts like a one-time pad in Game2,it is evident thatPr[S2]=1/2.(3) Combining(1),(2),and(3),we obtain|Pr[S0]−1/2|≤ ddh+ es,which is negligible,since both ddh and es are negligible.This proof illustrates how one can utilize more than one intractability assumption in a proof of security in a clean and simple way.4Pseudo-Random Functions4.1Basic DefinitionsLet 1and 2be positive integers(which are actually polynomially bounded functions in a security parameter).Let F:={F s}s∈S be a family of keyed functions,where each functionF s maps{0,1} 1to{0,1} 2.LetΓ1, 2denote the set of all functions from{0,1} 1to{0,1} 2.Informally,we say that F is pseudo-random if it is hard to distinguish a random functiondrawn from F from a random function drawn fromΓ1, 2,given black box access to such afunction(this notion was introduced in[GGM86]).More formally,consider an adversary A that has oracle access to a function inΓ1, 2,and suppose that A always outputs a bit.Define the PRF-advantage of A to be|Pr[s c|←S:A F s()=1]−Pr[f c|←Γ1, 2:A f()]=1|.We say that F is pseudo-random if any efficient adversary’s PRF-advantage is negligible.4.2Extending the Input Length with a Universal Hash FunctionWe now present one construction that allows one to stretch the input length of a pseudo-random family of functions.Let be a positive integer with > 1.Let H:={H k}k∈K be a family of keyed hash functions,where each H k maps{0,1} to{0,1} 1.Let us assume that H is an uh-universal family of hash functions,where uh is negligible.This means that for all w,w ∈{0,1} with w=w ,we havePr[k c|←K:H k(w)=H k(w )]≤ uh.There are many ways to construct such families of hash functions.Now define the family of functionsF :={F k,s}(k,s)∈K×S,where each Fk,s is the function from{0,1} into{0,1} 2that sends w∈{0,1} to F s(H k(w)).We shall now prove that if F is pseudo-random,then F is pseudo-random.Game0.This game represents the computation of an adversary given oracle access to a function drawn at random from F .Without loss of generality,we may assume that the adversary makes exactly q queries to its oracle,and never repeats any queries(regardless of the oracle responses).We may present this computation algorithmically as follows: k c|←K,s c|←Sr c|←Rfor i←1...q dow i←A(r,y1,...,y i−1)∈{0,1}x i←H k(w i)∈{0,1} 1y i←F s(x i)∈{0,1} 2b←A(r,y1,...,y q)∈{0,1}output bThe idea behind our notation is that the adversary is modeled as a deterministic al-gorithm A,and we supply its random coins r∈R as input,and in loop iteration i,the adversary computes its next query w i as a function of its coins and the results y1,...,y i−1 of its previous queries w1,...,w i−1.We are assuming that A operates in such a way that the values w1,...,w q are always distinct.Let S0be the event that the output b=1in Game0.Our goal is to transform this game into a game that is equivalent to the computation of the adversary given oracle access to a random element ofΓ ,2,so that the probability that b=1in the latter game is negligibly close to Pr[S0].Game1.[This is a transition based on indistinguishability.]We now modify Game0so that we use a truly random function from 1bits to 2bits,in place of F s.Intuitively, the pseudo-randomness property of F should guarantee that this modification has only a negligible effect on the behavior of the adversary.Algorithmically,Game1looks like this:。