The Angel Wins PDF Free Download

2y ago

29 Views

1 Downloads

1.77 MB

113 Pages

Report/dmca

Download PDF

Transcription

The Angel winsPéter GácsComputer Science DepartmentBoston UniversityOctober 19, 2007Péter Gács (Boston University)The Angel winsOctober 19, 20071 / 59

The gameThe gameThe board is an infinite “chessboard” (represented by the integer latticeZ2 ), with black and white squares, but initially, all squares are white.The Angel (a star in the picture) is always located on some square. Ineach step, first the Angel moves, then the Devil.In her move, the Angel makes 6 p unit steps, (p is constant, sayp 1000). The steps can be both horizontal and vertical, so we areusing the distanced(hx1 , y1 i, hx2 , y2 i) max( x2 x1 , y2 y1 ).She has to land on a white square.The Devil can turn a square black (eat it). This square stays black fromnow on.Péter Gács (Boston University)The Angel winsOctober 19, 20072 / 59

The gameHere, the Angel can move at most 6 steps (horizontal or vertical).Péter Gács (Boston University)The Angel winsOctober 19, 20073 / 59

The gameProblemCan the Devil always capture the Angel?How could he? For example, by buiding a wall of width p around her.Berlekamp: for p 1 the Devil wins.Of course, with p large, the Angel seems to have a large advantage.Péter Gács (Boston University)The Angel winsOctober 19, 20074 / 59

The gameTheoremFor sufficiently large p, the Angel has a strategy in which she will neverrun out of places to land on.Four independent solutions, in order of increasing merit:I have proved the theorem for large p.Bowditch: p 4.Máthé: p 2 (optimal).Kloster: p 2, with a simple algorithm.Most of the talk is adapted from Kloster’s website (and paper).Péter Gács (Boston University)The Angel winsOctober 19, 20075 / 59

The gameWhy has it been a challenge to prove this theorem? Because it has beenfound difficult to translate the Angel’s advantage into a strategy thatthe Devil cannot outwit. Here is an example:TheoremSuppose that the Angel is not allowed to ever decrease her x coordinate.Then the Devil can capture her.How? Let me show this only for the case when the Angel has to increasethe x coordinate in every step. Then from every position, her futuresteps are confined to a cone of angle with tangent (p 1).Péter Gács (Boston University)The Angel winsOctober 19, 20076 / 59

The gameThe Devil thickens a smaller and smaller segment of a far-away verticalwall. While the Angel is at distance 2n 1 6 d 2n , he increases thethickness of a segment of size M/2n by an additive constant.Péter Gács (Boston University)The Angel winsOctober 19, 20077 / 59

The gameWhy interesting?To most mathematicians, the problem does not need justification: it issufficient that it is simply stated and still nontrivial. But I had two otherreasons to be interested.Péter Gács (Boston University)The Angel winsOctober 19, 20078 / 59

The gameThe Angel seems to need a “multi-level” strategy (my specialty). Shemust be aware of possible threats posed by the Devil on many “scales”:She should not walk into a trap of size 10, 100, 1000, . . . .I indeed gave a hierarchical solution, but everybody else’s solution issimpler, and is not hierarchical.Péter Gács (Boston University)The Angel winsOctober 19, 20079 / 59

The gameAnother reason:The problem fits interestingly into a general project of developing an“approximate topology”. It measures a sort of connectivity of the latticein terms of an adversary’s cutoff abilities.Péter Gács (Boston University)The Angel winsOctober 19, 200710 / 59

Kloster’s solutionThe algorithmKloster’s solutionThe algorithm1234The Angel declares part of the board red. At start, this is the lefthalf-plane, and will always be “homeomorphic” to it. Its perimeter(initially directed upward) is called the path.At all times, the Angel stays next to the red area, next to a segmenton the path called the perch.On the Angel’s turn, she advances two units along the path,keeping the red area on the left.Every time the Devil has eaten a square, the Angel may paintadditional squares red, while satisfying the following conditions.The red area remains connected.The path behind and including the perch is unchanged.The path length increases by no more than two units for each eatensquare that is now painted red.When she can do this, she also must, for the maximal number ofeaten squares.Péter Gács (Boston University)The Angel winsOctober 19, 200711 / 59

Kloster’s solutionThe algorithmWalking along the path.Péter Gács (Boston University)The Angel winsOctober 19, 200712 / 59

Kloster’s solutionThe algorithmSo, whenever the Devil eats a threatening amount of squares too closeto the Angel’s path, the Angel will paint the area red and walk aroundinstead. Examples:update update Péter Gács (Boston University)The Angel winsOctober 19, 200713 / 59

Kloster’s solutionThe algorithmThe Devil can also eat the square the Angel is standing on, and thismight result in a—slightly—degenerate path:updatemove Péter Gács (Boston University) The Angel winsOctober 19, 200714 / 59

Kloster’s solutionThe algorithmA situation that would capture the Angel but will never occur:move Péter Gács (Boston University)The Angel winsOctober 19, 200715 / 59

Kloster’s solutionProofProof that it worksEasy case: the Angel never steps on an eaten cell that is not red.update Péter Gács (Boston University)The Angel winsOctober 19, 200716 / 59

Kloster’s solutionProofHarder case: the forbidden area will never surround the Angel in a waythat she cannot get out.In this example, the Devil can start building the vertical wall of the traponly in places where he is below the Angel. This gives her enough timeto escape. (demo on surround-history)Péter Gács (Boston University)The Angel winsOctober 19, 200717 / 59

Kloster’s solutionProofFor a path λ, let λ be its length increase from the initial one (afterignoring the identical infinite parts).λt path before step t.rt (λ) number of eaten squares painted red by time t for λ.Lemma (Potential) λt 2rt (λt ) is nondecreasing in t.This is easy to check.Péter Gács (Boston University)The Angel winsOctober 19, 200718 / 59

Kloster’s solutionProofAssume that λj (black looped curve here) is the first curve for whichboth sides of some segment get red (stripes here). It is easy to see thatthis can happen only with the Angel being in the loop.s the first such segment.κ the green curve outside ofλj , after cutting out the loopincluding s.i the first time the Angel getspast s.Péter Gács (Boston University)pipi-1The Angel winsspj-1κOctober 19, 200719 / 59

Kloster’s solutionProof λj κ 2(j i)because the Angel moves two segmentsper turn 2(rj (κ) ri (κ))because the Devil cannot eat more 2(rj (λj ) ri (κ))pisince κ surrounds more than λj , hence λj 2rj (λj ) κ 2ri (κ) λi 2ri (λi )by optimality of λipi-1spj-1κ λj 2rj (λj )by the Potential Lemma.Hence equality throughout, showing λj κ j i, so pj 1 isimmediately before s, and the Angel will jump out.Péter Gács (Boston University)The Angel winsOctober 19, 200720 / 59

Kloster’s solutionComplexityComplexityRecall the Angel’s algorithm:Every time the Devil has eaten a square, the Angel may paintadditional squares red, while satisfying the following conditions.The red area remains connected.The path behind and including the perch is unchanged.The path length increases by no more than two units foreach eaten square that is now painted red.When she can do this, she also must, for the maximal number ofeaten squares.This is an optimization problem for a path, by its form it could have acomplexity exponential in the (relevant) length.Péter Gács (Boston University)The Angel winsOctober 19, 200721 / 59

Kloster’s solutionComplexityIn practice, the Angel never needs to do anything this complex. She canalways keep the future part of the path in the following simple form:This spiral has a logarithmic number of sides. After the Devil eats asquare, unfortunately you may still have to modify all of the sides, sothe search may still be of the order of nlog n . The possiblity of apolynomial algorithm still seems open.Péter Gács (Boston University)The Angel winsOctober 19, 200722 / 59

Kloster’s solutionComplexityAmusingly, the past part can be quite complicated (in a fractal way,maybe not with the proportions shown).Péter Gács (Boston University)The Angel winsOctober 19, 200723 / 59

Máthé’s solutionThe Nice DevilMáthé’s solutionThe Nice DevilAn interesting observation:Theorem (Conway)If the Angel has a winning strategy then she also has a winning strategy inwhich she will never go to a site that she has visited, nor to any site thatshe could have passed to in an earlier move but did not.(The figure gives a very rough idea of the proof.)Péter Gács (Boston University)The Angel winsOctober 19, 200724 / 59

Máthé’s solutionThe Nice DevilMáthé found an important recasting of this theorem.DefinitionA Nice Devil is a Devil that never blocks a square on which the Angelhas visited, nor to any site that she could have passed to in an earliermove but did not.Theorem (Nice Devil)If the Devil catches the Angel then the Nice Devil can entrap her in somefinite domain.This theorem almost solves the problem. It frees the Angel fromworrying about walking into most kinds of trap: she can walk back out,the Devil cannot stop her!Péter Gács (Boston University)The Angel winsOctober 19, 200725 / 59

Máthé’s solutionThe Nice DevilProof of the Nice Devil theoremTo each journey v hv0 , . . . , vn i of Angel, reduced journeyρ(v) u hu0 , . . . , uk i.For this,1Draw an arrow from each vi to the earliest vj within distance p.2Take the path formed by these backward arrows starting from v0 ,and number it forward as hu0 , . . . , uk i.v3v2v5v1u1v0u0Péter Gács (Boston University)u3u4v8u5The Angel winsOctober 19, 200726 / 59

Máthé’s solutionThe Nice DevilLet Φ(v) Φ(v0 , . . . , vn ) be the position where the Devil would putsomething after seeing journey v (he has also the option of doingnothing). We define the Nice Devil’s strategy Ψ as follows.Ψ(v) Φ(ρ(v)) Φ(u)if this move is permitted to the Nice Devil, and nothing otherwise.Suppose Φ captures u hu0 , . . . , uk i, we will show that Ψ capturesv hv0 , . . . , vn i.There are s t with ut Φ(u0 , . . . , us ). Let s0 minvi us i, similarly fort0 . It is easy to seehu0 , . . . , us i ρ(v0 , . . . , vs0 ).Péter Gács (Boston University)The Angel winsOctober 19, 200727 / 59

Máthé’s solutionThe Nice Devilv3vl v2v5v1u1v0u0u3 usu4v8u5 utWe have Ψ(v0 , . . . , vs0 ) Φ(u0 , . . . , us ) ut vt0 or nothing. If it is vt0then the Nice Devil captures v.Let us show that it cannot be nothing. Indeed, this could only be if theNice Devil could not eat vt0 , which assumes an l s0 with distanced(vl , vt0 ) 6 p. But then the construction of the backward pathut , ut 1 , . . . , would have bypassed the node us vs0 .Péter Gács (Boston University)The Angel winsOctober 19, 200728 / 59

Máthé’s solutionConstructivityConstructivityFormally, the transformation done for the Nice Devil makes Máthé’ssolution non-constructive. Bowdich’s solution uses almost the sametransformation. It is claimed that the proof of Conway’s theorem turnsthem constructive.A non-constructive solution would be quite interesting if nothing else(at least nothing else so simple) was available. But Kloster’s solution issimple, constructive and even efficient (as shown here).Example (Game with only non-constructive solution)It is known that there is a finite set of square tiles (with various markson their edges) such that the plane can be tiled with copies of them(touching edges must have matching marks), but only in anon-recursive way. So let our game be: in each step, the Angel putsdown a tile, adjacent to the others, in a circular order. The Devil doesnothing, but still wins if the Angel cannot continue.Péter Gács (Boston University)The Angel winsOctober 19, 200729 / 59

My solutionReformulationMy solutionReformulation1The Angel can make only one (horizontal or vertical) step at attime.2The Devil manages a weight distribution µ. At time t, the weight atsite x isµt (x).3The Angel cannot land on a site x with weight µ(x) 1.PThe weight of a set S of sites is µt (S) x S µt (x). There is asmall constant σ 0 bounding the total weight increase per step:µt 1 (Z2 ) µt (Z2 ) 6 σ.Péter Gács (Boston University)The Angel winsOctober 19, 200730 / 59

My solutionReformulationNow the theorem says that the Angel wins for small enough σ.Péter Gács (Boston University)The Angel winsOctober 19, 200731 / 59

My solutionMulti-level terminologyMulti-level terminologyFix a (large) integer constant Q 1. A k-colony is a square whosecorners have coordinates that are multiples of Qk .When looking only at level k and (k 1), the (k 1)-colony is called acolony, the k-colony is called a cell.colonycellPéter Gács (Boston University)The Angel winsOctober 19, 200732 / 59

My solutionMulti-level terminologyThe side length of a square U is denoted U . A square U is bad (for thecurrent measure µ), ifµ(U) U .Otherwise it is good. Note that U becomes bad as soon as its weight isas large as its side length. The Devil need not “fill” a colony to spoil it,it is sufficient (for example) to “draw a line” through it.Péter Gács (Boston University)The Angel winsOctober 19, 200733 / 59

My solutionMulti-level terminologybadstill goodPéter Gács (Boston University)The Angel winsOctober 19, 200734 / 59

My solutionMulti-level terminologyFailure of planningSuppose we want to pass a colony. We cannot plan our path all inadvance based on what we see at our start, even on two levels.Péter Gács (Boston University)The Angel winsOctober 19, 200735 / 59

My solutionTime boundTime boundToo many digressionsPéter Gács (Boston University)The Angel winsOctober 19, 200736 / 59

My solutionTime boundTime boundHowever: the Devil must “pay” for every “digression” we are forcedinto. This is formally expressed using a time upper boundUstartendτgc (U) ρµ(U).Here τgc (U) is the geometric cost of moving from the start to the end ofregion U: it is just the sum of the lengths of straight runs making up theregion.The part exceeding the geometric cost is charged to the Devil via ρµ(U).Péter Gács (Boston University)The Angel winsOctober 19, 200737 / 59

My solutionTime boundScaling the time boundThe lower-scale time bound will imply asimilar higher-scale time bound:U DUτgc (U) ρµ(U)6 τgc (U ) ρµ(D) ρµ(U)6 τgc (U ) ρµ(U ).The geometric cost of U is its length. Thegeometric cost of U is larger by the horizontal“digression”, but this will be estimated via thecharge ρµ(D), where D is the bad area outsideU causing the digression.Péter Gács (Boston University)The Angel winsOctober 19, 200738 / 59

My solutionThe simple casesThe simple casesLet us set up a structure helping us to pass through areas that are nottoo beleagered by the Devil.A (horizontal or vertical) union of adjacent colonies is a run.We will have constantsδ 0,1/2 ξ 1 δ,where δ is appropriately small. A run U whose squares have width B is1-good (for µ) if µ(U) (1 δ)B. It is safe if µ(U) ξB.Péter Gács (Boston University)The Angel winsOctober 19, 200739 / 59

My solutionThe simple casesObservationWith sufficiently large Q, the following holds:If a run (row or column) is good then at most one of its cells is unsafe(we used ξ 1/2).If a colony is safe then at least 4 of its columns (and its rows) are1-good.The colony of largest weight in a run will be called its obstacle. In agood run, (hopefully) we can move around rather freely, except forjumping somehow over the obstacle. Let us postpone the problem of theobstacle.Péter Gács (Boston University)The Angel winsOctober 19, 200740 / 59

My solutionU DUPéter Gács (Boston University)The simple casesIn this safe pair of colonies, there will be severalgood columns along which we can pass from thebottom to the top. There are also good rows.Assuming we start from a good row, we can passto the column, and in the column we can pass to agood row in the destination colony, running abovethe “scapegoat” area (see earlier).If we move fast, then the situation does notchange too much while we execute all this.The Angel winsOctober 19, 200741 / 59

My solutionAttackAn attackHow to pass an obstacle? Note that here µ(U) U but we cannot planin advance, where to pass through square U.Péter Gács (Boston University)The Angel winsOctober 19, 200742 / 59

My solutionAttackWe cannot avoid U. Indeed,if we avoid all squares Uwith µ(U) λ U whereλ 1 then on level k theDevil will scare us even witha square U havingµ(U) λk U !Moral: attempt to pass, allowing for possible failure. (You cannot win awar “from the air”, avoiding all dangerous situations.)Péter Gács (Boston University)The Angel winsOctober 19, 200743 / 59

My solutionAttackIf there is a colum without obstacle, passin it. Otherwise each column contains atmost one obstacle.Péter Gács (Boston University)The Angel winsOctober 19, 200744 / 59

My solutionAttackIf obstacles in neigboring columns are notclose, pass between them.The case remains (marginal case) when the obstacles form a “chain”.Péter Gács (Boston University)The Angel winsOctober 19, 200745 / 59

My solutionPéter Gács (Boston University)AttackThe Angel winsOctober 19, 200746 / 59

My solutionAttackPreparing to attack in column 1.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionAttackAttack in column 1 and itscontinuation in column 2 failed.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionPéter Gács (Boston University)AttackThe Angel winsOctober 19, 200746 / 59

My solutionAttackAttack in columns 3, 4 failed, too.Columns 5,6 are not good, we willnot even attack: but we have toevade them.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionPéter Gács (Boston University)AttackThe Angel winsOctober 19, 200746 / 59

My solutionAttackAttack in column 7 fails again.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionAttackEvading in column 8.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionAttackEscape after successful attack incolumn 9.Péter Gács (Boston University)The Angel winsOctober 19, 200746 / 59

My solutionPaying for an attack seriesPaying for an attack seriesNew problemsThe path shown here intersectsitself (even if only slightly, inthe retreats). But the timebound τgc (U) ρτ (U) onlyworks for simple(self-nonintersecting) paths.Who pays for the initialdigression?Péter Gács (Boston University)The Angel winsOctober 19, 200747 / 59

Paying for an attack seriesMy solutionSolution for the retreats: many types of move. The body of an attackmove will (essentially) include the possible retreat.SJEAn( 1)An( 2)An( 3)An( 4)TAc(1)Ac(0)Ac( 1)Ac( 2)Ac( 3)F(1)F(5).Péter Gács (Boston University)The Angel winsOctober 19, 200748 / 59

My solutionPaying for an attack seriesA continuing attack move.Péter Gács (Boston University)The Angel winsOctober 19, 200749 / 59

My solutionPaying for an attack seriesJump. Step. Turn.Péter Gács (Boston University)The Angel winsOctober 19, 200750 / 59

My solutionPaying for an attack seriesNew attack. Continuing. Continuing.Péter Gács (Boston University)The Angel winsOctober 19, 200751 / 59

My solutionPaying for an attack seriesContinue. Finish. Step.Péter Gács (Boston University)The Angel winsOctober 19, 200752 / 59

My solutionPaying for an attack seriesColumns of dark squares: noattack.First column and columns afterthe dark squares: new attacks.All other columns: continuingattacks, all failed but the lastone. They need no retreat.Each dark square pays for thedigression around it.Problem: The body of a failedattack includes its obstacle:who will pay?Péter Gács (Boston University)The Angel winsOctober 19, 200753 / 59

My solutionPaying for an attack seriesSolution: we define the problemaway (push it into recursion). Leteach failed continuing attack pay foritself (even bring profit).New time bound:τgc U ρ1 µ(U) nρ2 B,where B is the cell size and n thenumber of failed continuing attacksin the path.Péter Gács (Boston University)The Angel winsOctober 19, 200754 / 59

My solutionScale-upScale-upOK, so what is the strategy?Essentially, it is an implementation of each big move by a series of smallmoves (in case of attacks, contingent on what the Devil does).(Of course, this is done recursively. On every sufficiently high level weare just trying to translate a big horizontal step.)Let us recall some of the earlier examples.Péter Gács (Boston University)The Angel winsOctober 19, 200755 / 59

My solutionScale-upU DUPéter Gács (Boston University)Now we understand how to pass the little greysquares: the jump moves (which are like attackswith a little more weight guarantee) will justjump over them.The Angel winsOctober 19, 200756 / 59

the Devil cannot outwit. Here is an example: Theorem Suppose that the Angel is not allowed to ever decrease her x coordinate. Then the Devil can capture her. How? Let me show this only for the case when the Angel has to increase the x coordinate in every step. Then from every position,